Databases
StackOverflow2013
Postsdbo
POHow can I find the shortest path between 100 moving targets? (Live demo included.)
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
    primarykey
    data
    text
    <h2>Background</h2> <p>This picture illustrates the problem: <img src="https://i.stack.imgur.com/dNVaO.png" alt="square_grid_with_arrows_giving_directions"></p> <p>I can control the red circle. The targets are the blue triangles. The black arrows indicate the direction that the targets will move.</p> <p>I want to collect all targets in the minimum number of steps.</p> <p>Each turn I must move 1 step either left/right/up or down.</p> <p>Each turn the targets will also move 1 step according to the directions shown on the board.</p> <h2>Demo</h2> <p>I've put up a playable demo of the problem <a href="http://penguinspuzzle.appspot.com/a_fishy_problem.html" rel="nofollow noreferrer">here on Google appengine</a>.</p> <p>I would be very interested if anyone can beat the target score as this would show that my current algorithm is suboptimal. (A congratulations message should be printed if you manage this!)</p> <h2>Problem</h2> <p>My current algorithm scales really badly with the number of targets. The time goes up exponentially and for 16 fish it is already several seconds. </p> <p>I would like to compute the answer for board sizes of 32*32 and with 100 moving targets.</p> <h2>Question</h2> <p>What is an efficient algorithm (ideally in Javascript) for computing the minimum number of steps to collect all targets?</p> <h2>What I've tried</h2> <p>My current approach is based on memoisation but it is very slow and I don't know whether it will always generate the best solution.</p> <p>I solve the subproblem of "what is the minimum number of steps to collect a given set of targets and end up at a particular target?".</p> <p>The subproblem is solved recursively by examining each choice for the previous target to have visited. I assume that it is always optimal to collect the previous subset of targets as quickly as possible and then move from the position you ended up to the current target as quickly as possible (although I don't know whether this is a valid assumption).</p> <p>This results in n*2^n states to be computed which grows very rapidly.</p> <p>The current code is shown below:</p> <pre><code>var DX=[1,0,-1,0]; var DY=[0,1,0,-1]; // Return the location of the given fish at time t function getPt(fish,t) { var i; var x=pts[fish][0]; var y=pts[fish][1]; for(i=0;i&lt;t;i++) { var b=board[x][y]; x+=DX[b]; y+=DY[b]; } return [x,y]; } // Return the number of steps to track down the given fish // Work by iterating and selecting first time when Manhattan distance matches time function fastest_route(peng,dest) { var myx=peng[0]; var myy=peng[1]; var x=dest[0]; var y=dest[1]; var t=0; while ((Math.abs(x-myx)+Math.abs(y-myy))!=t) { var b=board[x][y]; x+=DX[b]; y+=DY[b]; t+=1; } return t; } // Try to compute the shortest path to reach each fish and a certain subset of the others // key is current fish followed by N bits of bitmask // value is shortest time function computeTarget(start_x,start_y) { cache={}; // Compute the shortest steps to have visited all fish in bitmask // and with the last visit being to the fish with index equal to last function go(bitmask,last) { var i; var best=100000000; var key=(last&lt;&lt;num_fish)+bitmask; if (key in cache) { return cache[key]; } // Consider all previous positions bitmask -= 1&lt;&lt;last; if (bitmask==0) { best = fastest_route([start_x,start_y],pts[last]); } else { for(i=0;i&lt;pts.length;i++) { var bit = 1&lt;&lt;i; if (bitmask&amp;bit) { var s = go(bitmask,i); // least cost if our previous fish was i s+=fastest_route(getPt(i,s),getPt(last,s)); if (s&lt;best) best=s; } } } cache[key]=best; return best; } var t = 100000000; for(var i=0;i&lt;pts.length;i++) { t = Math.min(t,go((1&lt;&lt;pts.length)-1,i)); } return t; } </code></pre> <h2>What I've considered</h2> <p>Some options that I've wondered about are:</p> <ol> <li><p>Caching of intermediate results. The distance calculation repeats a lot of simulation and intermediate results could be cached.<br> However, I don't think this would stop it having exponential complexity.</p></li> <li><p>An A* search algorithm although it is not clear to me what an appropriate admissible heuristic would be and how effective this would be in practice.</p></li> <li><p>Investigating good algorithms for the travelling salesman problem and see if they apply to this problem.</p></li> <li><p>Trying to prove that the problem is NP-hard and hence unreasonable to be seeking an optimal answer for it.</p></li> </ol>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. This table or related slice is empty.
    1. USPeter de Rivaz
    plurals
    1. This table or related slice is empty.
    1. PL
      singulars
      1. LTLinked
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    3. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. This table or related slice is empty.
      1. VTUpMod
    1. COI would go for #4 and subsequently #3: With large enough boards, it mimics the TSP quite well.
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. USJohn Dvorak
    2. COIs TSP known to be NP-hard on a square grid?
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. USPeter de Rivaz
    3. COAs far as I know, TSP is NP-hard with the euclidean metric as well as the manhattan metric (square grid).
      singulars
      1. POHow can I find the shortest path between 100 moving targets? (Live demo included.)
      1. USJohn Dvorak
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload