最佳答案
我如何找到100个移动目标之间的最短路径? (包括现场演示。)
背景资料
这幅图说明了这个问题:
我可以控制红圈。目标是蓝色三角形。黑色箭头表示目标移动的方向。
我要在最短的步骤内收集所有目标。
每转一圈，我必须向左/向右/向上或向下移动一步。
每回合目标也将移动1步，根据显示在板上的指示。
演示
我已经发布了一个问题 谷歌应用程序引擎的可播放演示。
我会非常感兴趣，如果有人可以打破目标分数，因为这将表明，我目前的算法是次优的。(如果您做到了这一点，应该打印一条祝贺信息!)
问题
我现在的算法根据目标的数量很难进行调整。时间成指数增长，对于16条鱼来说已经是几秒钟了。
我想计算的答案，董事会大小的32 * 32和100个移动目标。
提问
什么是有效的算法(最好是用 Javascript)来计算收集所有目标的最小步骤数？
我已经尽力了
我目前的方法是基于记忆，但它是非常缓慢的，我不知道它是否总是会产生最好的解决方案。
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?".
通过检查以前访问过的目标的每个选项，递归地解决子问题。 我假设尽可能快地收集前面的目标子集，然后尽可能快地从最终的位置移动到当前的目标，这总是最佳的(尽管我不知道这是否是一个有效的假设)。
这导致要计算的 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 难的，因此寻找最优解是不合理的。
