?

Algorithms & Data Structures

Free Version

Upgrade subject to access all content

Difficult

Dynamic Programming: The Traveling Salesrep Problem

ALGOR-HJDHPK

Professor Smartypants has given pseudocode for the following exponential-time dynamic program for the traveling salesrep problem, defined as follows:

Input: A set $\{1, ..., n\}$ of cities, and a travel time $d(i,j)$ for every pair of cities $i$ and $j$. Note that the time taken to travel between cities $i$ and $j$ could be different from the time taken to travel from $j$ to $i$.
Output: The length of a minimum distance, closed, Hamiltonian tour of the cities. A closed Hamiltonian tour visits all of the cities EXACTLY once, and begins and ends with the same city.

1:   function TSP(int n, float[][] d)
2:   {
3:      // We will use opt[S, i] to hold the length of the current path starting in city 1,
4:      // visiting all the cities in the set S \ {i} in arbitrary order, and ending at city i.
5:      //
6:      // initially, all values of opt[S,i] are set to infinity.
7:      for k = 1, ... , n {
8:         opt[{i},i] = d[1][i];
9:      }
10:      for each subset S of {2, ..., n} {
11:          for each j in S \ {i} {
12:            opt[S,i] = min( opt[S,i], opt[S \ {i}, j] + d[j][i] );
13:          }
14:      }
15:      finalMin = infinity;
16:      for j = 2, ..., n {
17:         finalMin = min( opt[{2, ..., n}, j], finalMin );
18:      }
19:      return finalMin;
20:   }

Professor Smartypants claims that the algorithm works because of the following (correct) observation:

Any portion of a Hamiltonian tour which starts at city 1, visits all of the cities in $S \setminus \{i\}$, and ends at city $i$ must take the shortest path through the set $S$ which ends at city $i$.

Professor Know-it-all claims to have found some errors in the algorithm as it is currently written.

Which of the following errors must be fixed for the algorithm to return the correct solution?

Select ALL that apply.

A

The for loop at line 10 should visit subsets of $\{1,..., n\}$.

B

The for loop at line 10 should visit subsets of $\{2,..., n\}$ in order of increasing cardinality.

C

The for loop at line 10 should visit subsets of $\{2,..., n\}$ in order of decreasing cardinality.

D

The statement at line 17 should read:
finalMin = min( opt[{2, ..., n}, j) + d[1][j], finalMin );

E

The statement at line 17 should read:
finalMin = min( opt[{2, ..., n}, j) + d[j][1], finalMin );

F

The algorithm is correct as written.