[ACCEPTED]-How to compute optimal paths for traveling salesman bitonic tour?-dynamic-programming

Accepted answer
Score: 16

Clarification on your algorithm.

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

Important notes:

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

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

Now the easy 31 cases (note the changes!):

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

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

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

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

Anf 16 finally the interesting part comes:

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

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

Hope you got it.

Implementation.

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

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

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

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

Score: 3

Okay, the key notions in a dynamic programming 16 solution are:

  • you pre-compute smaller problems
  • you have a rule to let you combine smaller problems to find solutions for bigger problems
  • you have a known property of the problems that let's you prove the solution is really optimal under some measure of optimality. (In this case, shortest.)

The essential property of a 15 bitonic tour is that a vertical line in 14 the coordinate system crosses a side of 13 the closed polygon at most twice. So, what 12 is a bitonic tour of exactly two points? Clearly, any 11 two points form a (degenerate) bitonic tour. Three 10 points have two bitonic tours ("clockwise" and 9 "counterclockwise").

Now, how can 8 you pre-compute the various smaller bitonic 7 tours and combine them until you have all 6 points included and still have a bitonic 5 tour?


Okay, you're on the righ track with 4 your update. But now, in a dynamic programming 3 solution, what you do with work it bottom-up: pre-compute 2 and memoize (not "memorize") the optimal 1 subproblems.

More Related questions