wu :: forums
« wu :: forums - Two-Person Traversal of a Sequence of Cities »

Welcome, Guest. Please Login or Register.
Oct 1st, 2022, 11:44pm

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs
(Moderators: towr, SMQ, william wu, Grimbal, ThudnBlunder, Icarus, Eigenray)
   Two-Person Traversal of a Sequence of Cities
« Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Two-Person Traversal of a Sequence of Cities  (Read 10772 times)
singhar
Newbie
*





   


Posts: 22
Two-Person Traversal of a Sequence of Cities  
« on: Jul 21st, 2011, 11:04am »
Quote Quote Modify Modify

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.
IP Logged
nakli
Junior Member
**






   
WWW Email

Gender: male
Posts: 62
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #1 on: Jul 22nd, 2011, 8:20am »
Quote Quote Modify Modify

If I have understood correctly, we can solve TSP, and then simply delete the longest edge and then the next non-adjacent longest edge. Now how to solve TSP??  Tongue
IP Logged

I was born naked on a bed with a lady.
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
Posts: 13730
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #2 on: Jul 22nd, 2011, 8:25am »
Quote Quote Modify Modify

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

Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7519
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #3 on: Jul 30th, 2011, 2:18pm »
Quote Quote Modify Modify

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).
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7519
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #4 on: Jul 30th, 2011, 2:44pm »
Quote Quote Modify Modify

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.
« Last Edit: Jul 30th, 2011, 2:46pm by Grimbal » IP Logged
wiley
Newbie
*





   


Posts: 12
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #5 on: Sep 1st, 2011, 11:50am »
Quote Quote Modify Modify

Isn't this should be:
D(k,k+1) = min 0<=j<k { D(j,k+1)+d(j,k) }
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7519
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #6 on: Sep 5th, 2011, 1:15am »
Quote Quote Modify Modify

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.
« Last Edit: Sep 5th, 2011, 1:22am by Grimbal » IP Logged
birbal
Full Member
***





   


Gender: male
Posts: 250
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #7 on: Dec 25th, 2011, 10:02am »
Quote Quote Modify Modify

on Sep 5th, 2011, 1:15am, Grimbal wrote:
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.

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.
« Last Edit: Dec 27th, 2011, 9:59am by birbal » IP Logged

The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
Posts: 7519
Re: Two-Person Traversal of a Sequence of Cities  
« Reply #8 on: Dec 28th, 2011, 8:09am »
Quote Quote Modify Modify

D(i,j) is the shortest distance where one traveler ends at i and one at j, and each city is traveled exactly once.
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board