我如何find100个移动目标之间的最短path？ （包括现场演示）

背景

这幅图解释了这个问题：

我可以控制红圈。 目标是蓝色的三angular形。 黑色箭头表示目标移动的方向。

我想以最less的步骤收集所有目标。

每回合，我必须向左/向右/向上或向下移动1步。

每转一圈，目标也会按照棋盘上显示的方向移动一步。

演示

我已经在Google Appengine上展示了这个问题的可玩演示。

如果任何人都可以击败目标分数，我会非常感兴趣，因为这将显示我目前的algorithm是不理想的。 （如果你pipe理这个，你应该打印一个祝贺信息！）

问题

我目前的algorithm与目标的数量非常不好。 时间成倍增长，16条鱼已经有几秒钟了。

我想计算32 * 32的电路板尺寸和100个移动目标的答案。

题

什么是一个有效的algorithm（最好在Javascript中）计算收集所有目标的最小步数？

我试过了

我目前的方法是基于memoisation，但它是非常缓慢的，我不知道它是否总是会产生最好的解决scheme。

我解决了“收集一组既定目标的最小步数是多less，最终达到一个特定目标”的子问题。

子问题是通过检查前一个目标所访问的每个选项recursion地解决的。 我认为尽可能快地收集前一个目标子集，然后尽快从最终目标位置移动到当前目标（尽pipe我不知道这是否是一个有效的假设）总是最佳的。

这导致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; } 

我所考虑的

我想知道的一些选项是：

1. caching中间结果。 距离计算重复大量的模拟，中间结果可以被caching。
   但是，我不认为这会阻止它具有指数级的复杂性。

2. 一个A *searchalgorithm，虽然我不清楚什么是适当的可接受的启发式会是多么有效，这将是在实践中。

3. 研究旅行商问题的好algorithm，看看它们是否适用于这个问题。

4. 试图certificate这个问题是NP难的，因此无法为其寻求最佳答案。

Answer 1

你有没有search文献？ 我发现这些文件似乎分析你的问题：

• “跟踪移动目标和非固定旅行商问题”： 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：

以上两篇论文似乎都集中在欧几里德度量的线性运动上。

Answer 2

贪婪的方法

评论中提出的一种方法是首先到最近的目标。

我已经提出了一个演示版本，其中包括通过这个贪婪的方法在这里计算的成本。

代码是：

 function greedyMethod(start_x,start_y) { var still_to_visit = (1<<pts.length)-1; var pt=[start_x,start_y]; var s=0; while (still_to_visit) { var besti=-1; var bestc=0; for(i=0;i<pts.length;i++) { var bit = 1<<i; if (still_to_visit&bit) { c = fastest_route(pt,getPt(i,s)); if (besti<0 || c<bestc) { besti = i; bestc = c; } } } s+=c; still_to_visit -= 1<<besti; pt=getPt(besti,s); } return s; } 

对于10个目标，它是最佳距离的两倍左右，但有时甚至更多（如* 4），偶尔甚至达到最佳。

这种方法是非常有效的，所以我可以负担一些周期来改善答案。

接下来我正在考虑使用蚁群方法来看看他们是否可以有效地探索解决scheme空间。

蚁群法

对于这个问题， 蚁群方法似乎工作得非常好。 现在在这个答案中的链接比较使用贪婪和蚁群法时的结果。

这个想法是，ant根据当前的信息素水平概率地select他们的路线。 每进行一次试验，我们就会沿着他们发现的最短线索存放额外的信息素。

 function antMethod(start_x,start_y) { // First establish a baseline based on greedy var L = greedyMethod(start_x,start_y); var n = pts.length; var m = 10; // number of ants var numrepeats = 100; var alpha = 0.1; var q = 0.9; var t0 = 1/(n*L); pheromone=new Array(n+1); // entry n used for starting position for(i=0;i<=n;i++) { pheromone[i] = new Array(n); for(j=0;j<n;j++) pheromone[i][j] = t0; } h = new Array(n); overallBest=10000000; for(repeat=0;repeat<numrepeats;repeat++) { for(ant=0;ant<m;ant++) { route = new Array(n); var still_to_visit = (1<<n)-1; var pt=[start_x,start_y]; var s=0; var last=n; var step=0; while (still_to_visit) { var besti=-1; var bestc=0; var totalh=0; for(i=0;i<pts.length;i++) { var bit = 1<<i; if (still_to_visit&bit) { c = pheromone[last][i]/(1+fastest_route(pt,getPt(i,s))); h[i] = c; totalh += h[i]; if (besti<0 || c>bestc) { besti = i; bestc = c; } } } if (Math.random()>0.9) { thresh = totalh*Math.random(); for(i=0;i<pts.length;i++) { var bit = 1<<i; if (still_to_visit&bit) { thresh -= h[i]; if (thresh<0) { besti=i; break; } } } } s += fastest_route(pt,getPt(besti,s)); still_to_visit -= 1<<besti; pt=getPt(besti,s); route[step]=besti; step++; pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*t0; last = besti; } if (ant==0 || s<bestantscore) { bestroute=route; bestantscore = s; } } last = n; var d = 1/(1+bestantscore); for(i=0;i<n;i++) { var besti = bestroute[i]; pheromone[last][besti] = (1-alpha) * pheromone[last][besti] + alpha*d; last = besti; } overallBest = Math.min(overallBest,bestantscore); } return overallBest; } 

结果

这种使用100个重复的10个ant的蚁群方法仍然非常快（对于16个目标为37ms，而对于穷尽search则为3700ms），并且看起来非常准确。

下表显示了使用16个目标的10个试验的结果：

  Greedy Ant Optimal 46 29 29 91 38 37 103 30 30 86 29 29 75 26 22 182 38 36 120 31 28 106 38 30 93 30 30 129 39 38 

ant的方法似乎比贪婪更好，而且通常非常接近最优。

Answer 3

这个问题可以用广义旅行推销员问题来表示，然后转换成传统的旅行推销员问题。 这是一个深入研究的问题。 OP的问题的最有效的解决scheme可能并不比TSP的解决scheme更有效率，但绝不是肯定的（我可能没有充分利用OP的问题结构的某些方面，这将允许更快的解决scheme如周期性）。 无论哪种方式，这是一个很好的起点。

来自C.Non＆J.Bean， 广义旅行推销员问题的有效转换 ：

广义旅行推销员问题 （GTSP）是涉及select和顺序决策问题的有用模型。 问题的不对称版本定义在有节点N的有向图上，连接弧A和相应弧成本c的向量。 节点被预先分成m个相互排斥和穷举的节点集。 连接弧仅在属于不同组的节点之间定义，即不存在组内弧。 每个定义的弧具有相应的非负成本。 GTSP可以说是find一个最小代价m弧周期的问题，其中包括每个节点组恰好有一个节点 。

对于OP的问题：

• N每个成员在特定时间是特定鱼的位置。 表示为(x, y, t) ，其中(x, y)是网格坐标， t是鱼在该坐标上的时间。 对于OP中最左边的鱼，当鱼向右移动时，前几个（1为基础）是： (3, 9, 1), (4, 9, 2), (5, 9, 3) 。
• 对于任何N的成员，让fish(n_i)返回由该节点表示的鱼的ID。 对于N的任意两个成员，我们可以计算两个节点之间曼哈顿距离的曼哈顿time(n_i, n_j ）和节点之间时间偏移的time(n_i, n_j ）。
• 不相交的子集数m等于鱼的数量。 不相交的子集S_i将仅由fish(n) == i的节点组成。
• 如果对于两个节点i和j fish(n_i) != fish(n_j)那么i和j之间就有一个弧。
• 节点i和节点j之间的成本是time(n_i, n_j) ，或者如果time(n_i, n_j) < distance(n_i, n_j) （即，在鱼到达之前无法达到该位置，可能是因为它时间倒退）。 后一种types的弧可以被移除。
• 需要添加一个额外的节点来代表玩家的弧线位置和成本。

解决这个问题然后将导致以最小的代价（即，获得所有鱼的最短时间）对每个节点子集（即，每条鱼获得一次）进行单次访问。

本文继续描述如何将上述公式转化为传统的旅行推销员问题，并随后用现有技术解决或近似。 我还没有详细阅读，但是另外一篇这样做的文章是以这种方式来宣称是有效的。

复杂性有明显的问题。 特别是节点空间是无限的！ 这可以通过仅在一定的时间范围内生成节点来缓解。 如果t是生成节点的时间步数，而f是鱼的数量，那么节点空间的大小将是t * f 。 在时间点j的节点最多有(f - 1) * (t - j)输出弧（因为它不能及时回到自己的子集）。 弧的总数将按t^2 * f^2弧的顺序排列。 大概可以整理弧形结构，以利用鱼path最终是周期性的事实。 鱼的周期长度每一个最低公分母都会重复一次，所以也许可以使用这个事实。

我不太了解TSP说这是否可行，我不认为这意味着所发布的问题必然是NP难题……但这是寻求最佳或有限解决scheme的一种方法。

Answer 4

我认为另一个进展是：

• 计算目标的path – 预测。
• 比使用Voronoi图

引用维基百科：

在math中，Voronoi图是将空间分割成若干区域的一种方式。 预先指定一组点（称为种子，地点或发电机），并且对于每个种子将存在由与该种子相比更接近该种子的所有点组成的对应区域。

所以，你select一个目标，按照它的path进行一些步骤，并在那里设置一个种子点。 与所有其他目标一样，你得到一个voroni图。 根据你在哪个区域，你移动到它的种子点。 维奥拉，你有第一条鱼 现在重复这个步骤，直到你把所有的东西都连上。