背景
这张图片说明了问题：
我可以控制红色圆圈。目标是蓝色三角形。黑色箭头表示目标将移动的方向。
我想用最少的步骤收集所有目标。
每次转弯，我必须向左/右/上或下移动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困难的，因此寻求其最优解是不合理的。