CODEWITHSUNDEEP
algorithmdynamic-programminggraph-theoryshortest-path
OptimusPrime
OptimusPrime

Reputation: 143

A Constrained TSP: Find a minimum length tour which starts (and ends) at s and preserves the relative ordering of to sub set cities

I am trying to solve a problem with Dynamic Problem. I am familiar with classical TSP, but here it is a constrained TSP where there are two sets of cities and the relative order of the cities has to be preserved. This is the tricky part.

Given,
A starting city s
A sequence of n cities A=〈a_1,a_2,…,a_n 〉
Another sequence of n cities B=〈b_1,b_2,…,b_n 〉
A distance function D(x,y) which takes any pair of cities and returns the shortest distance between them.
Technically, we can say that L={s,a_1,a_2,…,a_n,b_1,…,b_n} and that D is a function

Objective is to ind a minimum length tour of all 2n+1 cities starting at s (and ending at s) subject to the following constraints:
The relative order of the cities in A must be preserved.
And the relative order of cities in B must be preserved.
In other words:
For all i:1 ≤ i < n, city a_i must be visited before cities a_(i+1),a_(i+2),…,a_n
And for all i:1 ≤ i < n, city b_i must be visited before cities b_(i+1),b_(i+2),…,b_n

Example:
A=〈a_1,a_2,a_3 〉
B=〈b_1,b_2,b_3 〉
Legal tours (return to s is implied):
s a_1 a_2 b_1 a_3 b_2 b_3
s b_1 a_1 a_2 b_2 b_3 a_3

An Illegal tour:
s a_1 b_2 a_2 b_1 a_3 b_3 (b_2 visited before b_1).

I am having problem finding the subproblem in O(n^2) time. Can anybody please help me.

Upvotes: 1

Views: 264

Answers (1)

mcdowella
mcdowella

Reputation: 19601

The cost of dynamic programming depends on how much state you need to hold to describe a sub-problem.

Here you can describe a solution with a series of pairs of numbers (i, j, k) where i is an index into the A array saying how many points of A you have visited, j is a similar index into the B array, and k is a bit saying which you are currently at. So (1,0,0) (2,0,0) (2,1,1)... means that the first two steps are to points in the A array and the next step is to a point in the B array.

The state you need to store to describe a partial solution is just (i,j,k). For each (i,j,k) you need to compute the best cost to that point, and e.g. if k=0 so you are computing the best cost to an A point you can do this by looking at the best costs for (i-1, j, 0) (i-1, j, 1) and the distances between A[i-1] and A[i] and between B[j-1] and A[i].

As usual, keep enough book-keeping that when you have computed the best cost of (all of A, all of B, 0) and (all of A, all of B, 1) and added on the distances back to the starting point you can track back from whichever of these is the smallest to recover the tour.

Upvotes: 3

Related Questions