Author |
Topic: Two-Person Traversal of a Sequence of Cities (Read 11108 times) |
|
singhar
Newbie
Posts: 22
|
 |
Two-Person Traversal of a Sequence of Cities
« on: Jul 21st, 2011, 11:04am » |
 Quote  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
 
Gender: 
Posts: 62
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #1 on: Jul 22nd, 2011, 8:20am » |
Quote 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?? 
|
|
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:
Posts: 13730
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #2 on: Jul 22nd, 2011, 8:25am » |
Quote 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:
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #3 on: Jul 30th, 2011, 2:18pm » |
Quote 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:
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #4 on: Jul 30th, 2011, 2:44pm » |
Quote 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 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:
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #6 on: Sep 5th, 2011, 1:15am » |
Quote 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:
Posts: 250
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #7 on: Dec 25th, 2011, 10:02am » |
Quote 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:
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #8 on: Dec 28th, 2011, 8:09am » |
Quote 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 |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print