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

Question

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

Pet*_*vaz 89 javascript algorithm graph-theory

背景

这张照片说明了问题: square_grid_with_arrows_giving_directions

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

我想以最少的步数收集所有目标.

每回合我必须向左/向右/向上或向下移动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;
}

Run Code Online (Sandbox Code Playgroud)

我考虑过的

我想知道的一些选项是:

缓存中间结果.距离计算重复了许多模拟,并且可以缓存中间结果.
但是,我不认为这会阻止它具有指数复杂性.
一个A*搜索算法,虽然我不清楚什么是适当的可接受的启发式,以及它在实践中的效果如何.
研究旅行商问题的好算法,看看它们是否适用于这个问题.
试图证明问题是NP难的,因此寻求最佳答案是不合理的.

Answer 1

uld*_*all 23

你搜索过文献了吗？我发现这些文件似乎可以分析你的问题:

"跟踪移动目标和非固定旅行商问题":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

Pet*_*vaz 13

贪心的方法

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

我已经提出了一个版本,其中包括通过这种贪心法计算的成本演示在这里.

代码是:

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

Run Code Online (Sandbox Code Playgroud)

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

Run Code Online (Sandbox Code Playgroud)

结果

使用100个重复10个蚂蚁的这种蚁群方法仍然非常快(16个目标为37ms,穷举搜索为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

Run Code Online (Sandbox Code Playgroud)

蚂蚁方法似乎明显优于贪婪并且通常非常接近最优.

Answer 3

tim*_*xyz 8

问题可以用广义旅行商问题来表示,然后转换成传统的旅行商问题.这是一个研究得很好的问题.OP问题的最有效解决方案可能不比TSP的解决方案更有效,但绝不是确定的(我可能没有利用OP的问题结构的某些方面,这将允许更快的解决方案,如其周期性).无论哪种方式,这都是一个很好的起点.

来自C. Noon和J.Bean,广义旅行商问题的有效转换:

在广义旅行商问题(GTSP)对于涉及选择和顺序的决策问题的有用模型.问题的非对称版本在具有节点N的有向图上定义,连接弧A和相应电弧成本c的矢量.节点被预先分成m个互斥和穷举的节点集.连接弧仅在属于不同组的节点之间定义,即,没有帧内弧.每个定义的弧具有相应的非负成本.GTSP可以说是找到最小成本m-arc循环的问题,其中包括来自每个节点集的恰好一个节点.

对于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)(即,在鱼到达之前不能达到位置,可能是因为它在时间上倒退).可以去除后一种类型的弧.
需要添加一个额外的节点,表示播放器的位置,其中包括弧线和所有其他节点的成本.

解决该问题然后将导致对每个节点子集的单次访问(即,每次获得一次鱼)以获得具有最小成本的路径(即,获得所有鱼的最小时间).

本文接着描述了如何将上述公式转化为传统的旅行商问题,并随后用现有技术解决或近似.我没有仔细阅读细节,但另一篇文章以一种宣称有效的方式来做这件事.

复杂性存在明显问题.特别是,节点空间是无限的!这可以通过仅生成直到特定时间范围的节点来缓解.如果t是生成节点的时间步数,并且f是鱼的数量,那么节点空间的大小将是t * f.一个节点在时间j上将具有最多(f - 1) * (t - j)输出弧(因为它不能及时移回或移动到其自己的子集).弧的总数将按弧的顺序排列t^2 * f^2.可以整理弧形结构,以利用鱼道最终是周期性的事实.鱼的周期长度的每个最小公分母都会重复它们的配置,所以也许可以使用这个事实.

我对TSP的了解不足以说明这是否可行,我认为这并不意味着所发布的问题必然是NP难的......但它是寻找最佳或有限解决方案的一种方法.

Answer 4

Jür*_*mer 1

我认为另一种方法是：

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

引用维基百科：

在数学中，沃罗诺伊图是一种将空间划分为多个区域的方法。预先指定一组点（称为种子、站点或生成器），对于每个种子，都会有一个相应的区域，该区域由距离该种子比任何其他距离更近的所有点组成。

因此，您选择一个目标，沿着它的路径执行一些步骤，并在那里设置一个种子点。对所有其他目标也执行此操作，您将得到一个 voroni 图。根据您所在的区域，您将移动到该区域的种子点。维奥拉，你得到了第一条鱼。现在重复这个步骤，直到你把它们全部咳出来。

归档时间：	12 年，5 月前
查看次数：	3447 次
最近记录：	12 年，5 月前