dynamic programming : traversal of cities

Question

I came across this question:

There are two persons. There is an ordered sequence of n cities, and the distances between every pair of cities is given. You must partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and such that the sum of the total distances travelled by A and B is minimized. Assume that person A and person B start initially at the first city in their respective subsequences.

I looked for its answer and the answer was:
Let c[i,j] be the minimum distance travelled if first person stops at city i and second at city j. Assume i< j

c[0,j]= summation of (d[k,k+1]) for k from 1 to j-1
c[i,j] = min(c[k,j]+ d[k,i]) if i!=0 where 0

The solution can also be seen at question 10 here

Now, my problems are:
1. This solution has no definition for i=1 (as then k has no value).
2. Now, suppose we are finding c[2,3]. It would be c[1,3]+ d[1,2]. Now c[1,3] means person B visited 0, 2 and 3 and person A remained at 1 or person B visited 2 and 3 and A visited 0 and 1. Also, c[2,3] means A visited just 2/ 0,1,2 /0,2 /1,2. So,

 c[1,3] = min(d[0,1]+ d[2,3], d[0,2]+ d[2,3])
 c[2,3] = min(d[0,1]+ d[1,2], d[0,2]+ d[1,3], d[1,2]+d[0,3], d[0,1]+d[1,3])

As can be seen the solutions are not overlapping.

To put it in other way, 2 is already covered by B in c[1,3]. So if we include c[1,3] in c[2,3] it would mean that 2 is visited by both A and B which is not required as it would just increase the cost.

Please correct me if I am wrong.

Answer 1

Q:: Two-Person Traversal of a Sequence of Cities: You are given an ordered sequence of n cities, and the distances between every pair of cities. Design an algorithm to partition the cities into two subsequences (not necessarily contiguous) such that person A visits all cities in the first subsequence (in order), person B visits all cities in the second subsequence (in order), and the sum of the total distances travelled by A and B is minimised. Assume that person A and person B start initially at the first city in their respective subsequences.

Here is how I understood the solution ::

Let us say the cities are number from 1 to n. We recurse on C(i, j), the minimum distance traveled if person A ends at city i and person B ends at city j. Assume without loss of generality i < j.

Let C(0, n) denote that person A does not visit any city, while person B visits all the cities from [1, n].

Hence, C(0, j) = d(1,2) + d(2,3) + .... + d(j-1, j) (B starting from city 1, going in order till city j).

C(i, j), where i is not 0 = minimum of following two cases :

case 1 : person A starts and stops at city i. In which case, C(i, j) = distance travelled by person B, travelling to all cities from 1 to j in order, skipping city i = d(1,2) + d(2,3) + ... + d(i-1, i+1) + d(i+1, i+2) + ... + d(j-1, j)

case 2 : person A starts at some city before i, and hence there is a city k which he travels just before going to city i (second last city in his traversal). In this case, C(i, j) = minimum {C(k, j) + d(k, i)} where k can vary from 1 to i-1.

The solution to the problem is minimum { C(i,n) } where i varies from 0 to n-1.

We can fill the DP matrix in row major order, as each calculation of C(i,j) requires either the distances d, or C(k,j) where k < i.

The running time of the algorithm will be O(n^3), as there are O(n^2) entries for which we do the calculation, and each calculation takes O(n) time.

Edit :: I think the solution given in the handout is missing case1.

Answer 2

You're right that the proposed solution is somewhat messy and incorrect.

The way to think about the problem is, as always, inductive: If I need to solve the problem of size n, how can I reduce it to smaller problems (0,..., n-1). If you'd like to solve this problem for size n, you note that one of the players needs to take the node n into their path.

The C[i, j] function is a helper function denoting as you described "minimal cost with A stopping at i and B stopping at j".

To arrive to the state C[i,j] player B had to come to j from j-1, unless of course j-1 = i. In the case that j-1 = i, then j had to come from some k < i. Therefore the function C[i, j] can be described as follows:

C[i,j] = {
   C[i,j-1] + d[j-1,j]                   (if i < j-1)
   min C[k,i] + d[k,j] for 0 <= k < i    (if i = j-1)
}

With this setting your base case is simply C[0, 1] = d[0,1].

Your final answer is then min C[k, n] for 0 <= k < n.