如何计算旅行商双调之旅的最佳路径？ [英] 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）递归函数应该计算的双调之旅我的最小距离 - ＆GT; 1 - ＆GT; Ĵ参观，比我更小的所有节点。因此，解决最初的问题将是 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＆LT; p2.x＆LT; p3.x ...＆LT; 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 - ＆GT; ...-＆GT; 1 - ＆GT; ... - ＆GT; Ĵ旅游是最佳的。然而来催落后会给我们带来同样的距离，并不会打破双调性。

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 ，因为 argmin K（D（K，J））= J-1 。 （节点从Ĵ可以在最短的路径到达是 J-1 ）。所以，这是等同于游： I - ＆GT; ... - ＆GT; 1 - ＆GT; ...... - ＆GT; J-1 - ＆GT; Ĵ，相当于 L（I，J-1）+ DIST（PJ-1，PJ）！

In this case, we must get to j-1, since argmin k (d(k,j) ) = j-1. (The node from which j can be reached at the shortest path is j-1). So, this is equivalent to the tour: i -> ... -> 1 -> .... -> j-1 -> j, which is equivalent to l(i,j-1) + dist(pj-1,pj)!

ANF终于有趣的部分是：

Anf finally the interesting part comes:

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

在这里，我们知道，我们已经从来得到我到 1 ，但没有线索上落后扫！这里的关键思想是我们必须思考的节点只是Ĵ在我们落后的路线了。这可能是任何一个节点从 1 到 J-1 ！让我们假设这个节点是 K 。 现在我们有一个旅游咨询： I - ＆GT; ... - ＆GT; 1 - ＆GT; ...... - ＆GT;的k - ＆GT; Ĵ，对不对？这次巡演的成本为 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).

希望你得到了它。

您将需要一个2维数组说 BT [1..1] [1..1] 。让我是行的索引，Ĵ是列索引。在此表中，我们应该如何填写？

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 左指标掉入（二）类别。

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.

在remainin行，我们填补对角线元素到最后。

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

下面是一个简单的C ++ code（未测试）：

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屋！