如何找到100个移动目标之间的最短路径?(包括现场演示)。

Background

This picture illustrates the problem:

这幅图说明了问题:

I can control the red circle. The targets are the blue triangles. The black arrows indicate the direction that the targets will move.

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

I want to collect all targets in the minimum number of steps.

我想在最小的步骤中收集所有的目标。

Each turn I must move 1 step either left/right/up or down.

每次转弯时，我必须左/右/上/下移动一步。

Each turn the targets will also move 1 step according to the directions shown on the board.

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

Demo

I've put up a playable demo of the problem here on Google appengine.

我在谷歌appengine上提供了这个问题的可播放演示。

I would be very interested if anyone can beat the target score as this would show that my current algorithm is suboptimal. (A congratulations message should be printed if you manage this!)

如果有人能超过目标分数，我会很感兴趣，因为这将表明我目前的算法是次优的。(如果你能做到这一点，就应该打印一条祝贺信息!)

Problem

My current algorithm scales really badly with the number of targets. The time goes up exponentially and for 16 fish it is already several seconds.

我目前的算法与目标的数量相比实在是太糟糕了。时间呈指数增长，16条鱼已经有几秒钟了。

I would like to compute the answer for board sizes of 32*32 and with 100 moving targets.

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

Question

What is an efficient algorithm (ideally in Javascript) for computing the minimum number of steps to collect all targets?

什么是有效的算法(最好是Javascript)，用于计算收集所有目标所需的最小步骤数?

What I've tried

My current approach is based on memoisation but it is very slow and I don't know whether it will always generate the best solution.

我目前的方法是基于记忆化，但它非常缓慢，我不知道它是否总是能产生最好的解决方案。

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?".

我解决了“收集给定目标集并最终到达特定目标的最小步骤数是多少?”的子问题。

The subproblem is solved recursively by examining each choice for the previous target to have visited. I assume that it is always optimal to collect the previous subset of targets as quickly as possible and then move from the position you ended up to the current target as quickly as possible (although I don't know whether this is a valid assumption).

子问题通过检查前一个要访问的目标的每个选项来递归地解决。我认为，尽可能快地收集之前的目标子集，然后尽可能快地从最终到达当前目标的位置移动到当前目标位置总是最优的(尽管我不知道这是否是一个有效的假设)。

This results in n*2^n states to be computed which grows very rapidly.

这导致n * 2 ^ n计算,增长非常迅速。

The current code is shown below:

当前代码如下所示:

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

What I've considered

Some options that I've wondered about are:

我想知道的一些选项是:

1. Caching of intermediate results. The distance calculation repeats a lot of simulation and intermediate results could be cached.
   However, I don't think this would stop it having exponential complexity.

   缓存的中间结果。距离计算重复了大量的模拟，中间结果可以缓存。但是，我认为这不会阻止它的指数复杂度。

2. An A* search algorithm although it is not clear to me what an appropriate admissible heuristic would be and how effective this would be in practice.

   A*搜索算法，虽然我不清楚什么是合适的启发式算法，以及它在实践中有多有效。

3. Investigating good algorithms for the travelling salesman problem and see if they apply to this problem.

   研究好旅行推销员问题的算法，看看它们是否适用于这个问题。

4. Trying to prove that the problem is NP-hard and hence unreasonable to be seeking an optimal answer for it.

   试图证明这个问题是np困难的，因此寻找一个最优的答案是不合理的。

4 个解决方案

#1

Have you searched the literature? I found these papers which seems to analyse your problem:

你查过文献了吗?我找到了这些论文，它们似乎分析了你的问题:

• "Tracking moving targets and the non- stationary traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.85.9940

  “追踪移动目标和非静止旅行推销员问题”:http://citeseerx.ist.psu.edu/viewdoc/summary?doi= 10.1.85.9940

• "The moving-target traveling salesman problem": http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.57.6403

  “移动目标旅行商问题”:http://citeseerx.ist.psu.edu/viewdoc/summary? doi10.1.1.57.6403。

UPDATE 1:

更新1:

The above two papers seems to concentrate on linear movement for the euclidian metric.

以上两篇论文似乎集中讨论了欧几里得度规的线性运动。

#2

Greedy method

One approach suggested in the comments is to go to the closest target first.

评论中建议的一种方法是先去最近的目标。

I've put up a version of the demo which includes the cost calculated via this greedy method here.

我放了一个演示的版本，包含了通过这个贪心方法计算的成本。

The code is:

的代码是:

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

For 10 targets it is around twice the optimal distance, but sometimes much more (e.g. *4) and occasionally even hits the optimum.

对于10个目标，它大约是最佳距离的两倍，但有时更多(例如*4)，有时甚至达到最佳。

This approach is very efficient so I can afford some cycles to improve the answer.

这种方法非常有效，所以我可以用一些周期来改进答案。

Next I'm considering using ant colony methods to see if they can explore the solution space effectively.

接下来，我考虑使用蚁群方法，看看它们能否有效地探索解决方案空间。

Ant colony method

An Ant colony method seems to work remarkable well for this problem. The link in this answer now compares the results when using both greedy and ant colony method.

蚁群算法似乎在这个问题上很有效。这个答案中的链接现在比较了使用贪婪和蚁群方法时的结果。

The idea is that ants choose their route probabilistically based on the current level of pheromone. After every 10 trials, we deposit additional pheromone along the shortest trail they found.

这个想法是，蚂蚁根据当前的信息素水平选择它们的路线。每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;
}

Results

This ant colony method using 100 repeats of 10 ants is still very fast (37ms for 16 targets compared to 3700ms for the exhaustive search) and seems very accurate.

这种使用10只蚂蚁重复100次的蚁群方法仍然非常快(16个目标用37ms，而穷尽搜索用3700ms)，而且似乎非常准确。

The table below shows the results for 10 trials using 16 targets:

下表显示了使用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

The ant method seems significantly better than greedy and often very close to optimal.

蚂蚁方法似乎明显比贪婪好，而且往往非常接近最优。

#3

The problem may be represented in terms of the Generalized Traveling Salesman Problem, and then converted to a conventional Traveling Salesman Problem. This is a well-studied problem. It is possible that the most efficient solutions to the OP's problem are no more efficient than solutions to the TSP, but by no means certain (I am probably failing to take advantage of some aspects of the OP's problem structure that would allow for a quicker solution, such as its cyclical nature). Either way, it is a good starting point.

问题可以用广义旅行商的问题来表示，然后转化为传统的旅行商问题。这是一个经过充分研究的问题。可能是最有效的解决方案,OP的问题比解决TSP不再有效,但绝不是某些(我可能无法利用OP的某些方面的问题结构,它将允许更快的解决方案,如周期性)。不管怎样，这都是一个好的起点。

From C. Noon & J.Bean, An Efficient Transformation of the Generalized Traveling Salesman Problem:

从c。Noon & J。Bean，广义旅行商问题的有效转化:

The Generalized Traveling Salesman Problem (GTSP) is a useful model for problems involving decisions of selection and sequence. The asymmetric version of the problem is defined on a directed graph with nodes N, connecting arcs A and a vector of corresponding arc costs c. The nodes are pregrouped into m mutually exclusive and exhaustive nodesets. Connecting arcs are defined only between nodes belonging to different sets, that is, there are no intraset arcs. Each defined arc has a corresponding non-negative cost. The GTSP can be stated as the problem of finding a minimum cost m-arc cycle which includes exactly one node from each nodeset.

广义旅行商问题(GTSP)是一个有用的模型，用于涉及选择和顺序的决策。问题的非对称版本定义在一个有向图上，节点N连接弧a和相应的弧代价c的向量。连接弧仅定义在属于不同集合的节点之间，即不存在内部弧。每个定义的弧都有相应的非负成本。GTSP可表示为找到最小成本m-弧周期的问题，该周期包含来自每个节点的一个节点。

For the OP's problem:

OP的问题:

• Each member of N is a particular fish's location at a particular time. Represent this as (x, y, t), where (x, y) is a grid coordinate, and t is the time at which the fish will be at this coordinate. For the leftmost fish in the OP's example, the first few of these (1-based) are: (3, 9, 1), (4, 9, 2), (5, 9, 3) as the fish moves right.
• N的每个元素都是特定时间内某条鱼的位置。表示为(x, y, t)，其中(x, y)是一个坐标，而t是鱼在这个坐标上的时间。对于OP示例中最左边的鱼，当鱼向右移动时，前几个(基于1)是:(3,9,1)，(4,9,2)，(5,9,3)。
• For any member of N let fish(n_i) return the ID of the fish represented by the node. For any two members of N we can calculate manhattan(n_i, n_j) for the manhattan distance between the two nodes, and time(n_i, n_j) for the time offset between the nodes.
• 对于N的任何成员，让fish(n_i)返回由节点表示的fish的ID。对于N中的任意两个元素，我们可以计算出两个节点之间的曼哈顿距离(n_i, n_j)，以及节点之间的时间偏移量(n_i, n_j)。
• The number of disjoint subsets m is equal to the number of fish. The disjoint subset S_i will consist only of the nodes for which fish(n) == i.
• 不相交子集m的数量等于鱼的数量。disjoint子集S_i只包含fish(n) == i的节点。
• If for two nodes i and j fish(n_i) != fish(n_j) then there is an arc between i and j.
• 如果对于两个节点i和j fish(n_i) != fish(n_j)，则i和j之间存在一条弧。
• The cost between node i and node j is time(n_i, n_j), or undefined if time(n_i, n_j) < distance(n_i, n_j) (i.e. the location can't be reached before the fish gets there, perhaps because it is backwards in time). Arcs of this latter type can be removed.
• 节点i和节点j之间的成本是时间(n_i, n_j)，或者是未定义的if time(n_i, n_j) < distance(n_i, n_j)(也就是说，在fish到达之前无法到达位置，可能是因为时间向后)。后一种类型的弧可以被移除。
• An extra node will need to be added representing the location of the player with arcs and costs to all other nodes.
• 需要添加一个额外的节点来表示玩家的位置，并向所有其他节点添加弧和成本。

Solving this problem would then result in a single visit to each node subset (i.e. each fish is obtained once) for a path with minimal cost (i.e. minimal time for all fish to be obtained).

然后，解决这个问题将导致对每个节点子集(即每条鱼获得一次)的一次访问，以最小的成本(即获取所有鱼的最小时间)访问路径。

The paper goes on to describe how the above formulation may be transformed into a traditional Traveling Salesman Problem and subsequently solved or approximated with existing techniques. I have not read through the details but another paper that does this in a way it proclaims to be efficient is this one.

本文接着描述了如何将上述公式转化为一个传统的旅行商问题，然后用已有的技术解决或近似解决。我没有读过细节，但另一篇文章说，这是一种有效的方法。

There are obvious issues with complexity. In particular, the node space is infinite! This can be alleviated by only generating nodes up to a certain time horizon. If t is the number of timesteps to generate nodes for and f is the number of fish then the size of the node space will be t * f. A node at time j will have at most (f - 1) * (t - j) outgoing arcs (as it can't move back in time or to its own subset). The total number of arcs will be in the order of t^2 * f^2 arcs. The arc structure can probably be tidied up, to take advantage of the fact the fish paths are eventually cyclical. The fish will repeat their configuration once every lowest common denominator of their cycle lengths so perhaps this fact can be used.

有明显的复杂性问题。特别是节点空间是无限的!只有在一定的时间范围内生成节点，才能缓解这一问题。如果t是步伐的数量生成节点和f是鱼的数量然后节点空间的大小将t * f。一个节点在时间j将最多(f - 1)*(t - j)即将离任的弧(因为它不能向后移动或其子集)。弧的总数将在t f ^ ^ 2 * 2的顺序弧。弧形结构可能会被整理，以利用鱼道最终是周期性的这一事实。鱼将重复它们的配置，每一个最小公分母的周期长度，所以也许这个事实可以使用。

I don't know enough about the TSP to say whether this is feasible or not, and I don't think it means that the problem posted is necessarily NP-hard... but it is one approach towards finding an optimal or bounded solution.

我不太清楚TSP是否可行，也不认为这意味着发布的问题一定很难解决……但这是一种寻找最优或有界解的方法。

#4

I think another approch would be:

我认为另一个方法是:

• calculate the path of the targets - predictive.
• 计算目标的路径——预测。
• than use Voronoi diagrams
• 比用泰森多边形法图

Quote wikipedia:

引用*:

In mathematics, a Voronoi diagram is a way of dividing space into a number of regions. A set of points (called seeds, sites, or generators) is specified beforehand and for each seed there will be a corresponding region consisting of all points closer to that seed than to any other.

在数学中，Voronoi图是一种将空间划分为若干区域的方法。预先指定一组点(称为种子、地点或生成器)，对于每一颗种子，将有一个相应的区域，包含与该种子较近的所有点。

So, you choose a target, follow it's path for some steps and set a seed point there. Do this with all other targets as well and you get a voroni diagram. Depending in which area you are, you move to the seedpoint of it. Viola, you got the first fish. Now repeat this step until you cought them all.

所以，你选择一个目标，沿着它的路径进行一些步骤，并在那里设置一个种子点。对所有其他目标也这样做，就会得到一个voroni图。取决于你所在的区域，你移动到它的种子点。维奥拉，你钓到了第一条鱼。现在重复这个步骤，直到你把它们都做完。