# Help needed for algorithm

Printable View

• September 11th, 2010, 02:42 PM
krainert
Help needed for algorithm
Greetings,

I'm not sure this is the place to ask, but here goes.

I have a number of actors, presumably up to 14, and a number of targets, up to 5. I need my actors to distribute evenly among the targets (so that the lowest number of actors heading towards a target is actors/targets and the highest is actors/targets+1). Furthermore, actors and targets are located in a two-dimensional space. The distribution has to be done so the sum of distances between each actor and its target becomes as small as possible. I've tried various approaches, but none seem to always satisfy this property.

Any suggestions? I figure there might be a number of algorithms addressing this problem already.

Thanks!
• September 11th, 2010, 03:46 PM
Twit of wit
The question is not complete. You can't just put all actors directly on their target?
• September 12th, 2010, 02:43 AM
krainert
Quote:

Originally Posted by Twit of wit
The question is not complete. You can't just put all actors directly on their target?

Actually, I'm fairly sure the question is complete. I can't relocate my actors, I can only determine which targets they're assigned to. Who said anything about moving? ;)

EDIT: I may have been a bit unclear about the "heading" of each actor; I need to decide on a target for each, but actually reaching the target is beyond the algorithm, and I have no means of employing any movement whatsoever.
• September 12th, 2010, 07:18 AM
jrmonroe
I'm visualizing the five targets located at the tips of a five-pointed star with 10 actors forming a circle outside the star and 4 actors forming a cluster inside the star. Each target associates with 2 outer actors, and 4 of 5 targets associates with an inner actor.
• September 12th, 2010, 08:09 AM
krainert
Thanks.
Quote:

Originally Posted by jrmonroe
I'm visualizing the five targets located at the tips of a five-pointed star with 10 actors forming a circle outside the star and 4 actors forming a cluster inside the star. Each target associates with 2 outer actors, and 4 of 5 targets associates with an inner actor.

I'm sorry if I'm not understanding you correctly, but are you suggesting that I need more info on the location of actors and targets (both random, unknown) or a solution I don't think I'm following...?
• September 12th, 2010, 09:21 AM
Twit of wit
It seems to be an NP-hard problem.
• September 12th, 2010, 09:53 AM
krainert
Quote:

Originally Posted by Twit of wit
It seems to be an NP-hard problem.

Which means I'll have to brute-force my way out?
• September 12th, 2010, 12:09 PM
schip666
Try this for a start:
http://scholar.google.com/scholar?q=...=1&oi=scholart

I think this is a traveling-salesman type problem which still seems to be NP-complete. If you have a central control element then you can do an exhaustive search. Or you can try various distributed multi-agent -- e.g., ants -- solutions. Achieving a continuous and even distribution of agents to targets is probably not possible w/o central control, except in the limit of very large numbers of both.