我如何才能找到100移动目标之间的最短路径？ （现场演示包括在内。）最短、路径、演示、目标
背景
本图片说明了这个问题：
我可以控制的红圈。这些目标是蓝色的三角形。黑色箭头指示的方向，该目标将移动。
我要收集所有目标的步骤的最小数量。
每个转向我必须向前1步或左/右/向上或向下。
每个转向按在板上显示的方向上的目标，也将移动1步。
演示
我已经提出了这个问题的可玩演示在这里对谷歌应用程序引擎。
我会非常有兴趣，如果任何人都可以击败的目标分数，因为这将表明，我目前的算法是最理想的。 （应打印的祝贺消息，如果你管理这个！）
问题
我目前的算法尺度实在太差了与目标数量。时间上升指数和16鱼类已经是几秒钟。
我想计算为32 * 32电路板尺寸和100移动目标的答案。
问题
什么是一个有效的算法（最好是在JavaScript）的计算步骤的最小数量，收集所有的目标？
我已经试过
我目前的做法是基于memoisation但它是非常缓慢的，我不知道它是否会一直产生最佳的解决方案。
予解决的子问题是什么的步骤，收集一组给定的目标，并最终在一个特定的目标？的最小数目
的子问题是通过检查每一个选择为previous目标参观了递归解决。 我认为，它始终是最佳的，以尽可能快地收集目标previous子集，然后从你最后的当前目标尽快的位置移动（虽然我不知道这是否是一个有效的假设）。
这导致在N * 2 ^ n个状态来计算其迅速增长。
目前的code如下所示：
变种DX = [1,0，1,0]。
变种DY = [0,1,0，-1];
//返回给定的鱼的位置在时间t
功能getPt（鱼，T）{
变种我;
变种X = PTS [鱼] [0];
变种Y = PTS [鱼] [1];
对于（i = 0; I＆LT;吨;我++）{
变种B =板[X] [Y]
X + = DX并[b];
Y + = DY [B]。
}
返回[X，Y];
}
//返回的步数来跟踪给定的鱼
//通过遍历并选择第一次在曼哈顿距离比赛的时间工作
功能fastest_route（鹏，DEST）{
VAR MYX =鹏[0];
VAR MYY =鹏[1];
变种X =目标寄存器[0];
变种Y =目标寄存器[1];
变种T = 0;
而（（Math.abs（X-MYX）+ Math.abs（Y-MYY））！= T）{
变种B =板[X] [Y]
X + = DX并[b];
Y + = DY [B]。
T + = 1;
}
返回吨;
}
//尝试来计算最短路径到达每个鱼和其他的某个子集
//关键是目前的鱼其次是位掩码的N位
//值为最短的时间
功能computeTarget（start_x，start_y）{
缓存= {};
//计算已经参观了位掩码所有鱼类最短的步骤
//并与上次访问是鱼与指数等于持续
功能Go（位掩码，最后）{
变种我;
VAR最好=亿;
VAR键=（最后的＆LT;＆LT; num_fish）+位掩码;
如果（键缓存）{
返回高速缓存[重点]
}
//考虑所有previous位置
掩码 - = 1＆LT;＆LT;最后，
如果（位掩码== 0）{
最好= fastest_route（[start_x，start_y] PTS [最后]）;
} 其他 {
对于（i = 0; I＆LT; pts.length;我++）{
VAR位= 1＆LT;＆LT;我;
如果（位掩码和放大器;位）{
VAR S =去（位掩码，I）; //最少的费用，如果我们的previous鱼是我
S + = fastest_route（getPt（I，S），getPt（最近，S））;
如果（S＆LT;最好的）最好= S;
}
}
}
缓存[关键] =最好;
最好回报;
}
VAR T =亿;
对于（VAR I = 0; I＆LT; pts.length;我++）{
T = Math.min（T，去（（1＆LT;＆LT; pts.length）-1，I））;
}
返回吨;
}
我已经考虑
这是我一直想知道的一些选项有：
的中间结果缓存。距离计算重复很多模拟和中间结果可以被缓存。 但是，我不认为有指数的复杂性，这将阻止它。
这是A *搜索算法虽然现在我也不清楚什么是适当的容许的启发是，如何有效的，这将是在实践中。
调查好算法旅行商问题，看看它们是否适用于这个问题。
试图证明这个问题是NP难的，因此不合理的是寻求一个最佳答案吧。
解决方案你有没有通过文献检索？我发现这些论文似乎来分析你的问题：
跟踪移动目标和非固定旅行商 问题：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940
的移动目标旅行商问题：http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403
更新1：
以上两篇文章似乎集中于直线运动的欧氏度量。
Background
This picture illustrates the problem:
I can control the red circle. The targets are the blue triangles. The black arrows indicate the direction that the targets will move.
I want to collect all targets in the minimum number of steps.
Each turn I must move 1 step either left/right/up or down.
Each turn the targets will also move 1 step according to the directions shown on the board.
Demo
I've put up a playable demo of the problem here on Google appengine.
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!)
Problem
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.
I would like to compute the answer for board sizes of 32*32 and with 100 moving targets.
Question
What is an efficient algorithm (ideally in Javascript) for computing the minimum number of steps to collect all targets?
What I've tried
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.
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?".
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).
This results in n*2^n states to be computed which grows very rapidly.
The current code is shown below:
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<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<<num_fish)+bitmask;
if (key in cache) {
return cache[key];
}
// Consider all previous positions
bitmask -= 1<<last;
if (bitmask==0) {
best = fastest_route([start_x,start_y],pts[last]);
} else {
for(i=0;i<pts.length;i++) {
var bit = 1<<i;
if (bitmask&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<best) best=s;
}
}
}
cache[key]=best;
return best;
}
var t = 100000000;
for(var i=0;i<pts.length;i++) {
t = Math.min(t,go((1<<pts.length)-1,i));
}
return t;
}
What I've considered
Some options that I've wondered about are:
Caching of intermediate results. The distance calculation repeats a lot of simulation and intermediate results could be cached. However, I don't think this would stop it having exponential complexity.
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.
Investigating good algorithms for the travelling salesman problem and see if they apply to this problem.
Trying to prove that the problem is NP-hard and hence unreasonable to be seeking an optimal answer for it.
解决方案
Have you searched the literature? I found these papers which seems to analyse your problem:
"Tracking moving targets and the non- stationary traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940
"The moving-target traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403
UPDATE 1:
The above two papers seems to concentrate on linear movement for the euclidian metric.
