背景
这张图说明了问题：
我可以控制红色圆圈。目标是蓝色三角形。黑色箭头表示目标将移动的方向。
我想以最少的步骤收集所有目标。
每转一圈，我必须向左/向右/向上或向下移动 1 步。
每转一圈，目标也将根据板上显示的方向移动 1 步。
演示
我在 Google appengine 上放了一个可播放的问题演示。
如果有人能超过目标分数，我会非常感兴趣，因为这表明我当前的算法不是最优的。（如果你能做到这一点，应该打印一条祝贺信息！）
问题
我当前的算法与目标数量的关系非常糟糕。时间呈指数增长，对于 16 条鱼来说已经是几秒钟了。
我想计算 32*32 板尺寸和 100 个移动目标的答案。
问题
什么是计算收集所有目标的最小步骤数的有效算法（最好是 Javascript）？
我试过的
我目前的方法是基于记忆，但它非常慢，我不知道它是否总是会产生最好的解决方案。
我解决了“收集给定目标集并最终达到特定目标的最小步骤数是多少？”的子问题。
通过检查前一个目标访问过的每个选择，递归地解决子问题。我假设尽可能快地收集先前的目标子集总是最佳的，然后尽快从最终到达的位置移动到当前目标（尽管我不知道这是否是一个有效的假设）。
这导致要计算的 n*2^n 个状态增长得非常快。
当前代码如下所示：
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;
}
我考虑过的
我想知道的一些选项是：
缓存中间结果。距离计算重复了很多模拟，中间结果可以被缓存。
但是，我认为这不会阻止它具有指数复杂性。一个 A* 搜索算法，尽管我不清楚什么是适当的可接受启发式算法以及这在实践中的有效性。
研究旅行商问题的好算法，看看它们是否适用于这个问题。
试图证明这个问题是 NP 难的，因此为它寻求最佳答案是不合理的。