Notices
Results 1 to 8 of 8

Thread: Help needed for algorithm

  1. #1 Help needed for algorithm 
    New Member
    Join Date
    May 2010
    Posts
    4
    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!


    Reply With Quote  
     

  2.  
     

  3. #2  
    Forum Masters Degree Twit of wit's Avatar
    Join Date
    Jan 2010
    Posts
    553
    The question is not complete. You can't just put all actors directly on their target?


    Reply With Quote  
     

  4. #3  
    New Member
    Join Date
    May 2010
    Posts
    4
    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.
    Reply With Quote  
     

  5. #4  
    Forum Professor jrmonroe's Avatar
    Join Date
    Mar 2010
    Posts
    1,444
    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.
    Grief is the price we pay for love. (CM Parkes) Our postillion has been struck by lightning. (Unknown) War is always the choice of the chosen who will not have to fight. (Bono) The years tell much what the days never knew. (RW Emerson) Reality is not always probable, or likely. (JL Borges)
    Reply With Quote  
     

  6. #5  
    New Member
    Join Date
    May 2010
    Posts
    4
    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...?
    Reply With Quote  
     

  7. #6  
    Forum Masters Degree Twit of wit's Avatar
    Join Date
    Jan 2010
    Posts
    553
    It seems to be an NP-hard problem.
    Reply With Quote  
     

  8. #7  
    New Member
    Join Date
    May 2010
    Posts
    4
    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?
    Reply With Quote  
     

  9. #8  
    Forum Freshman
    Join Date
    Feb 2010
    Posts
    84
    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.
    Reply With Quote  
     

Bookmarks
Bookmarks
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •