如何计算旅行商双音游的最佳路径? [英] How to compute optimal paths for traveling salesman bitonic tour?

问题描述

更新

阅读更多内容后，可以给出具有以下递推关系的解决方案:

After more reading, the solution can be given with the following recurrence relation:

(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)?

This is now starting to make sense, except for part C. How would I go about determining the minimum value k? I suppose it means you can iterate through all possible k values and just store the minimum result of ( l(k,i) + dist(pk,pj)?

是的，这绝对是我在学校学习的问题.我们正在研究旅行商问题的双音游.

Yes, definitely a problem I was studying at school. We are studying bitonic tours for the traveling salesman problem.

无论如何，假设我有 5 个顶点 {0,1,2,3,4}.我知道我的第一步是按 x 坐标递增的顺序对它们进行排序.从那里开始，我对如何使用动态编程来做到这一点感到有些困惑.

Anyway, say I have 5 vertices {0,1,2,3,4}. I know my first step is to sort these in order of increasing x-coordinates. From there, I am a bit confused on how this would be done with dynamic programming.

我读到我应该扫描已排序节点的列表，并为两个部分(初始路径和返回路径)维护最佳路径.我对如何计算这些最佳路径感到困惑.例如，我如何知道我是否应该在初始路径或返回路径中包含给定节点，因为它不能同时包含在两个路径中(端点除外).回想一下动态编程中的斐波那契，您基本上从您的基本案例开始，然后继续前进.我想我要问的是如何开始解决双音旅行商问题?

I am reading that I should scan the list of sorted nodes, and maintain optimal paths for both parts (initial path and the return path). I am confused as to how I will calculate these optimal paths. For instance, how will I know if I should include a given node in the initial path or the return path, since it cannot be in both (except for the endpoints). Thinking back to Fibonacci in dynamic programming, you basically start with your base case and work your way forward. I guess what I am asking is how would I get started with the bitonic traveling salesman problem?

对于斐波那契数列之类的东西，采用动态规划方法是很清楚的.然而，我不知道我是不是太密集了还是什么，但我很困惑试图解决这个问题.

For something like the Fibonacci numbers, a dynamic programming approached is quite clear. However, I don't know if I am just being dense or what but I am quite confused trying to wrap my head around this problem.

感谢您的关注！

注意:我不是在寻找完整的解决方案，而是至少寻找一些入门的好技巧.例如，如果这是斐波那契问题，则可以说明前几个数字是如何计算的.请让我知道如何改进问题.

NOTE: I am not looking for complete solutions, but at least some good tips to get my started. For example, if this were the Fibonacci problem, one could illustrate how the first few numbers are calculated. Please let me know how I can improve the question as well.

推荐答案

澄清你的算法.

l(i,j) 递归函数应该计算双音游程的最小距离 i ->1 ->j 访问所有小于 i 的节点.所以，初始问题的解将是 l(n,n)!

Clarification on your algorithm.

The l(i,j) recursive function should compute the minimum distance of a bitonic tour i -> 1 -> j visiting all nodes that are smaller than i. So, the solution to the initial problem will be l(n,n)!

重要说明:

1. 我们可以假设节点按其 x 坐标排序并相应地标记(p1.x < p2.x < p3.x ... < pn.x).如果它们没有被排序，我们可以在 O(nlogn) 时间内对它们进行排序.

1. we can assume that the nodes are ordered by their x coordinate and labeled accordingly (p1.x < p2.x < p3.x ... < pn.x). It they weren't ordered, we could sort them in O(nlogn) time.

l(i,j) = l(j,i).原因是在 lhs 中，我们有一个 i ->...->1 ->... ->j 最佳游览.然而，向后穿越这条路线会给我们带来相同的距离，并且不会破坏双音属性.

l(i,j) = l(j,i). The reason is that in the lhs, we have a i ->...-> 1 -> ... -> j tour which is optimal. However traversing this route backward will give us the same distance, and won't broke bitonic property.

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

Now the easy cases (note the changes!):

(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之前选择任意数量的其他点访问会导致更长的路径！)

Here we have the following tour : 1->1->...->2. Trivially this is equivalent to the length of the path 1->...->2. Since points are ordered by their .x coordinate, there is no point between 1 and 2, so the straight line connecting them will be the optimal one. ( Choosing any number of other points to visit before 2 would result in a longer path! )

(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 和 j 之间不能有.所以，这相当于游览:i ->... ->1 ->.... ->j-1 ->j，相当于l(i,j-1) + dist(pj-1,pj)!

In this case, j-1 must be on the part of the path 1 -> ... -> j, because the part i -> ... -> 1 can not contain nodes with an index bigger than i. Because all nodes in the path 1 -> ... -> j are in increasing order of index, there can be none between j-1 and j. So, this is equivalent to the tour: i -> ... -> 1 -> .... -> j-1 -> j, which is equivalent to l(i,j-1) + dist(pj-1,pj)!

终于有趣的部分来了:

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

这里我们知道我们必须从i 到1，但是没有任何关于向后扫描的线索！这里的关键思想是我们必须考虑在我们的后向路由中 j 之前的节点.它可以是从 1 到 j-1 的任何节点！让我们假设这个节点是 k.现在我们有一个游览:i ->... ->1 ->.... ->k->j，对吧?这次旅行的费用是l(i,k) + dist(pk,pj).

Here we know that we have to get from i to 1, but there is no clue on the backward sweep! The key idea here is that we must think of the node just before j on our backward route. It may be any of the nodes from 1 to j-1! Let us assume that this node is k. Now we have a tour: i -> ... -> 1 -> .... -> k -> j, right? The cost of this tour is l(i,k) + dist(pk,pj).

希望你明白.

您将需要一个二维数组，比如 BT[1..n][1..n].让 i 为行索引，j 为列索引.这张表应该怎么填?

You will need a 2-dimensional array say BT[1..n][1..n]. Let i be the row index, j be the column index. How should we fill in this table?

第一行我们知道BT[1][1] = 0，BT[1][2] = d(1,2)，所以我们只剩下 i,j 索引属于 (b) 类别.

In the first row we know BT[1][1] = 0, BT[1][2] = d(1,2), so we have only i,j indexes left that fall into the (b) category.

在剩余的行中，我们填充从对角线到末尾的元素.

In the remainin rows, we fill the elements from the diagonal till the end.

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

Here is a sample C++ code (not tested):

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

这篇关于如何计算旅行商双音游的最佳路径?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！