如何计算旅行推销员比特币之旅的最佳路径？

Question

更新

在更多阅读之后,可以给出具有以下递归关系的解决方案:

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj )
(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)
(c) When i = j - 1 and j > 2, min 1<=k<i (l(k; i) + dist(pk; pj ))

现在开始有意义了,除了C部分.我如何确定最小值k？我想这意味着你可以迭代所有可能的k值并只存储(l(k,i)+ dist(pk,pj)的最小结果？

---

是的,绝对是我在学校学习的一个问题.我们正在研究旅行商问题的比特旅游.

不管怎么说,我有5个顶点{0,1,2,3,4}.我知道我的第一步是按照增加x坐标的顺序对它们进行排序.从那里开始,我对动态编程如何完成这一点感到困惑.

我正在阅读我应该扫描已排序节点的列表,并维护两个部分(初始路径和返回路径)的最佳路径.我对如何计算这些最佳路径感到困惑.例如,我如何知道是否应该在初始路径或返回路径中包含给定节点,因为它不能同时包含(两个端点除外).回想一下斐波纳契的动态编程,你基本上从基础案例入手,继续前进.我想我要问的是如何开始使用比特型旅行推销员问题？

对于类似Fibonacci数字的东西,接近的动态编程非常清楚.但是,我不知道我是不是只是在密集或什么,但我很困惑试图绕过这个问题.

谢谢你的期待!

注意:我不是在寻找完整的解决方案,但至少有一些很好的技巧可以让我开始.例如,如果这是Fibonacci问题,可以说明如何计算前几个数字.请告诉我如何改进这个问题.

Answer 1

澄清你的算法.

该l(i,j)递归函数计算出一个双调之旅的最小距离i -> 1 -> j来访是小于所有节点i.所以,最初问题的解决方案将是l(n,n)!

重要笔记:

1. 我们可以假设节点按x坐标排序并相应地标记(p1.x < p2.x < p3.x ... < pn.x).它们没有订购,我们可以O(nlogn)及时对它们进行分类.

2. l(i,j) = l(j,i).原因是在lhs,我们有一个i ->...-> 1 -> ... -> j最佳的旅游.然而,向后穿过这条路线将给我们相同的距离,并且不会破坏比特的属性.

现在简单的案例(注意变化!):

(a) When i = 1 and j = 2, l(i; j) = dist(pi; pj ) = dist(1,2)

在这里我们有以下旅游:1->1->...->2.通常,这相当于路径的长度1->...->2.由于点按其.x坐标排序,因此在1和之间没有任何关系2,因此连接它们的直线将是最佳点.(选择之前要访问的任意数量的其他点2会导致更长的路径!)

(b) When i < j - 1; l(i; j) = l(i; j - 1) + dist(pj-1; pj)

在这种情况下,我们必须得到j-1,因为1 -> ... -> j.(i -> ... -> 1可以在最短路径到达的节点i).所以,这相当于巡演:1 -> ... -> j,相当于j-1!

Anf最后有趣的部分来了:

(c) When i = j - 1 or i = j, min 1<=k<i (l(k; i) + dist(pk; pj ))

在这里,我们知道,我们必须从取得j到i -> ... -> 1 -> .... -> j-1 -> j,但在向后的扫掠不知道!这里的关键思想是我们必须l(i,j-1) + dist(pj-1,pj)在我们的后向路线上考虑节点.它可以是任何节点从i到1!我们假设这个节点是j.现在我们有一个旅游:1对吗？这次旅行的费用是j-1.

希望你明白了.

实现.

你需要一个二维数组说k.让i -> ... -> 1 -> .... -> k -> j是行索引,l(i,k) + dist(pk,pj)是列索引.我们该如何填写此表？

我们知道,在第一排BT[1..n][1..n],i,所以我们只能j落入左侧指标BT[1][1] = 0类别.

在剩下的行中,我们从对角线填充元素直到结束.

这是一个示例C++代码(未测试):

void ComputeBitonicTSPCost( const std::vector< std::vector<int> >& dist, int* opt ) {
  int n = dist.size();
  std::vector< std::vector< int > > BT;
  BT.resize(n);
  for ( int i = 0; i < n; ++i )
    BT.at(i).resize(n);

  BT.at(0).at(0) = 0;  // p1 to p1 bitonic distance is 0
  BT.at(0).at(1) = dist.at(0).at(1);  // p1 to p2 bitonic distance is d(2,1)

  // fill the first row
  for ( int j = 2; j < n; ++j )
    BT.at(0).at(j) = BT.at(0).at(j-1) + dist.at(j-1).at(j);

  // fill the remaining rows
  int temp, min;  
  for ( int i = 1; i < n; ++i ) {
    for ( int j = i; j < n; ++j ) {
      BT.at(i).at(j) = -1;
      min = std::numeric_limits<int>::max();
      if ( i == j || i == j -1 ) {
        for( int k = 0; k < i; ++k ) {
          temp = BT.at(k).at(i) + dist.at(k).at(j);
          min = ( temp < min ) ? temp : min;
        }        
        BT.at(i).at(j) = min;        
      } else {
        BT.at(i).at(j) = BT.at(i).at(j-1) + dist.at(j-1).at(j);
      }
    }
  }

  *opt = BT.at(n-1).at(n-1);
}

Answer 2

好的，动态规划解决方案的关键概念是：

• 你预先计算较小的问题
• 你有一条规则可以让你结合较小的问题来找到更大问题的解决方案
• 您拥有问题的已知属性，可以让您证明该解决方案在某种最优性衡量标准下确实是最优的。（在本例中为最短。）

双调游览的本质属性是坐标系中的垂直线最多穿过闭合多边形的一条边两次。那么，什么是恰好两点的双调游览呢？显然，任何两点都会形成一个（退化的）双音之旅。三个点有两个双调游览（“顺时针”和“逆时针”）。

现在，您如何预先计算各种较小的双调旅行并将它们组合起来，直到包含所有点并且仍然拥有双调旅行？

好的，您的更新进展顺利。但现在，在动态编程解决方案中，您所做的事情是自下而上的：预先计算并记忆（而不是“记忆”）最佳子问题。