wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> Two-Person Traversal of a Sequence of Cities
        
(Message started by: singhar on Jul 21^st, 2011, 11:04am)

Title: Two-Person Traversal of a Sequence of Cities
Post by singhar on Jul 21^st, 2011, 11:04am

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. 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.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by nakli on Jul 22^nd, 2011, 8:20am

If I have understood correctly, we can [hide]solve TSP, and then simply delete the longest edge and then the next non-adjacent longest edge. Now how to solve TSP?? :P[/hide]

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by towr on Jul 22^nd, 2011, 8:25am

[hide]In TSP, you have to determine the best order of the cities, but here the order is already given.[/hide] This can probably be done in polynomial time; dynamic programming seems like an option.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Jul 30^th, 2011, 2:18pm

For each i,k compute the best distance to travel
Let d(i,j) the distance between i and j.
Let D(i,k) = the minimal distance to visit cities 1..k, where the first traveler ends at city k and the second traveler ends at city (i<k). Use i=0 if the second traveler did not yet start its journey.

Then add one city at a time in the optimal way.

The problem is to cover all the cases when computing D(i,k).

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Jul 30^th, 2011, 2:44pm

I think the following works

for convenience, use d(0,j) = 0

D(0,1) = 0
D(i,k+1) = D(i,k)+d(k,k+1) for 0<=i<k
D(k,k+1) = min 0<=j<k { D(j,k)+d(j,k+1) }

The minimum distance for n cities and 2 travelers is the minimum of the D(i,n) over 0<i<n.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by wiley on Sep 1^st, 2011, 11:50am

Isn't this should be:
D(k,k+1) = min 0<=j<k { D(j,k+1)+d(j,k) }

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Sep 5^th, 2011, 1:15am

No.

In D(j,k)+d(j,k+1) you start with D(j,k): one person ends at k the other at j, then you add d(j,k+1): the person at j adds a leg from j to k+1.

In your formula, D(j,k+1) already includes a passage in city k. If you add a leg from j to k, you visit the city twice.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by birbal on Dec 25^th, 2011, 10:02am

on 09/05/11 at 01:15:38, Grimbal wrote:

Can we say that all the states that can exist in our formation are valid and optimal? for example D(3,4) mean that one person ending at 3 and the other at 4 in first four cities. but it may be the case that for optimal value (least sum), both the cities should be travelled by only one of them.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Dec 28^th, 2011, 8:09am

D(i,j) is the shortest distance where one traveler ends at i and one at j, and each city is traveled exactly once.