我如何才能找到100个移动目标之间的最短路径？ （包括现场演示。）(How can I find

背景

这张照片说明了这个问题：

我可以控制的红圈。 这些目标是蓝色的三角形。 黑色箭头指示目标将移动的方向。

我想收集所有目标在最少的步骤数。

每回合我必须向前1步是左/右/向上或向下。

每转一圈目标也将根据在板中示出的方向上移动1步。

演示

我已经忍了这个问题的可玩演示在这里谷歌AppEngine上 。

我会非常有兴趣，如果任何人都可以击败目标分数，因为这将表明，我目前的算法是次优的。 （如果你管理这应该打印的祝贺留言！）

问题

我现在的算法扩展实在太差了与目标数。 时间上升呈指数和16种鱼类已经是几秒钟。

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

题

什么是计算最少的步骤数，收集所有目标的高效算法（最好是在JavaScript）的？

我已经试过

我目前的做法是基于memoisation但它是非常缓慢的，我不知道是否会一直产生最佳的解决方案。

我解决的子问题“是什么步骤，收集一组给定的目标和特定的目标最终的最低数量？”。

子问题是通过检查每个选择。到过先前的目标递归解决。 我认为，它始终是最佳的，以尽可能快地收集目标之前的子集，然后从你以最快的速度结束了当前目标尽可能的位置移动（虽然我不知道这是否是一个有效的假设）。

这导致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. 的中间结果缓存。 距离计算重复很多模拟和中间结果可以被高速缓存。
   不过，我不认为这将有指数复杂停止。

2. 一个A *搜索算法虽然不是很清楚，我适当的启发的会是什么，以及如何有效的，这将是在实践中。

3. 调查针对旅行商问题很好的算法，看看它们是否适用于这个问题。

4. 试图证明该问题是NP难的，因此不合理拟出售它的最佳答案。

Answer 1:

您搜索的文学？ 我发现这些文件似乎来分析你的问题：

• “跟踪移动目标和非平稳旅行商问题”： 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），有时甚至打最佳。

这种方法是非常有效的，所以我可以提供一些周期，提高了答案。

接下来，我用蚁群方法，看看他们是否能有效地探索解空间的考虑。

蚁群方法

一个蚁群方法似乎运作良好显着这个问题。 在这个答案的链接现在同时使用贪婪和蚁群方法时的结果进行了比较。

这个想法是，蚂蚁选择自己的路线概率基于信息素的当前水平。 每10次试验后，我们沿着存入他们发现最短的踪迹额外的信息素。

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;
}

结果

使用10个蚂蚁100个重复此蚁群方法仍然是非常快（16个目标仅为37微秒相比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

蚂蚁的方法似乎比贪婪显著更好，往往非常接近最优。

Answer 3:

该问题可能在广义TSP问题的角度来表示，然后转换到常规的TSP问题。 这是一个精心研究的问题。 这可能是业务方案的问题的最有效的解决方案并不比对TSP解决方案更有效，但不能肯定（我可能无法充分利用的任择议定书的问题，结构的某些方面，将允许更快的解决方案如它的周期性质）。 无论哪种方式，这是一个很好的起点。

从C.中午和J.Bean， 广义旅行商问题的高效转化 ：

广义旅行商问题 （GTSP）对于涉及选择和顺序的决策问题的有用模型。 问题的不对称版本被限定在与节点N1的有向图，连接弧A和对应的弧成本℃的载体。 这些节点pregrouped成m相互排斥和详尽的节点集。 连接弧只有属于不同组的节点之间定义的，即，不存在intraset弧。 每个限定的圆弧具有相应的非负成本。 的GTSP可以表述为寻找最小代价米弧循环包括来自每个节点集恰好一个节点的问题 。

对于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的任何两个部件就可以计算出manhattan(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)即鱼得到前在那里，可能是因为它不能达到的位置是在时间上向后）。 这后一种类型的电弧可以被移除。
• 一个额外的节点将需要添加代表用弧线和成本到所有其他节点的球员的位置。

那么解决这个问题将导致每个节点的子集（即获得一次每条鱼）与最低成本路径的单次访问（即最少的时间来获得所有的鱼）。

纸张接着描述如何将上述配方可以被转换成一个传统的TSP问题，并随后溶解或与现有技术近似。 我没有经历过的细节阅读，但另一篇文章，这是否在它宣称是有效的方式是这一个 。

有复杂性的明显问题。 特别是，节点空间是无限的！ 这可以通过仅生成节点达到一定的时间范围来减轻。 如果t是生成节点用于时间步的数量和f是鱼的数量，则节点空间的大小将是t * f 。 在时间节点j最多有(f - 1) * (t - j)传出弧（因为它不能在时间或自己的子组移动回）。 弧的总数将在顺序t^2 * f^2的弧。 拱式结构大概可以收拾，采取的事实鱼路径最终周期性的优势。 鱼会重复它们的配置，一旦他们的周期的每一个最小公分母长度因此，或许可以用这个事实。

我不知道有足够的了解的TSP说这是否可行与否，我不认为这意味着张贴的问题必然是NP难...但它是朝着找到最优或界解的一种方法。

Answer 4:

我认为另一个计算策略是：

• 计算目标的路径 - 预测。
• 不是使用Voronoi图

报价维基百科：

在数学中，Voronoi图是将空间划分为多个区域的方式。 一组点（称为种子，网站或发电机）被预先指定并且对于每个种子会有由比任何其他更接近种子的所有点的相应区域。

所以，你选择一个目标，遵循它的一些步骤，路径和设置种子点在那里。 做到这一点与所有其他目标，以及，你会得到一个voroni图。 根据你是哪个区域，你移动到它的seedpoint。 中提琴，你得到的第一条。 现在，重复此步骤，直到他们毫无遗漏的全部。

文章来源: How can I find the shortest path between 100 moving targets? (Live demo included.)