wu :: forums - Print Page


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

        riddles >> hard >> Two-Person Traversal of a Sequence of Cities
        
(Message started by: S4T4N on Jun 19^th, 2009, 11:50am)

Title: Two-Person Traversal of a Sequence of Cities
Post by S4T4N on Jun 19^th, 2009, 11:50am

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.

Source : http://people.csail.mit.edu/bdean/6.046/dp/

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Jun 20^th, 2009, 4:34am

I can do it in O(n²)

[hide]Compute for each i<j what is the minimum travel distance t[i,j] to visit cities up to j in order, where one traveler ends at i and the other ends at j.
t[i,j] can be computed from the previous values.
t[i,j] = t[i,j-1] + d[j-1,j] if i<j-1 (the same person visited the last 2 cities)
t[i,j] = min[k<j-1](t[k,j-1] + d[k,j]) if i=j-1 (a different person visited the last 2 cities)
[/hide]

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by towr on Jun 20^th, 2009, 5:30am

Do they have to visit their cities in the order of the sequence?
Otherwise it sounds a lot like the traveling salesman problem; which can't be solved so easily.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Obob on Jun 20^th, 2009, 9:53am

Your interpretation sounds correct, towr. A key word here is to "partition" the cities into two subsequences, which suggests we can specify which cities they visit but that the order they visit them is already specified by the original ordering.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by singh_sukhu on Sep 28^th, 2009, 1:26am

So does that mean we have to only list the partitions??

The following contains an approach to the problem using genetic algos.
www.icgst.com/aiml/Volume6/Issue3/P1120632001.pdf

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by R on Sep 28^th, 2009, 12:04pm

What I understood from the question is that we are given n cities in a certain order:

A₁, A₂, A₃, ....A_n.
Along with that we are given distance between each pair of cities, A_i,j for all 1http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifi,jhttp://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/le.gifn.

We have to divide it in two sequences,
A_i1, A_i2, A_i3, ....A_ik.
A_j1, A_j2, A_j3, ....A_jk.

such that i1 < i2 < i3 < .... < ik and j1 < j2 < j3 < .... < jk.

Which I think is quite different from and simpler than the Travelling salesmen problem. The source also suggests that a dynamic programming solution is expected for this problem.

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by Grimbal on Jan 10^th, 2012, 9:35am

(received this as PM)

Quote:

What can be the reccurence if you have also the information of travelling grid -let s the limits of the land-Huh

if you could help me it would be marvelous because i am really stucked

I don't understand. What is the "travelling grid"?

Title: Re: Two-Person Traversal of a Sequence of Cities
Post by towr on Jan 10^th, 2012, 9:46am

If that's the same person I got a PM from (tetraktida), then what I think he has in mind is Manhattan distance, so all cities are on a 2D grid, and distance between cities is horizontal + vertical distance.

I've exchanged a few PMs with him, here's the last PM I got. I haven't really found time to look at it, but it should give a better idea what he's working on (at least in as much as it reveals it has something to do with manhattan distance).

Quote:

i have write this

#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define NO_VALUE -1
#define size 101
#define size2 101

int Manhattan (int x1, int y1, int x2, int y2);
int minimum (int x, int y);
int min_all (int pin, int i, int r, int c);

int main()
{
int n,r, c, x, y;
// int *s = malloc(1000001 * 2 * sizeof(int));
int s;
// int *dp = malloc(1000001 * 11 * 11 * sizeof(int));
int dp;
int ax,ay,bx,by;
scanf("%d %d %d", &n, &r, &c);
scanf("%d %d", &ax, &ay);
scanf("%d %d", &bx, &by);
for (x = 1; x <= r; x++)
{
for (y = 1; y <= c; y++)
{
dp = NO_VALUE;
}
}
for (x = 1; x <= n; x++)
{
// printf("x : %d\n", x);
scanf("%d %d", &(s), &(s));
}
dp = Manhattan(s, s, bx, by);
dp = Manhattan(s, s, ax, ay);
int i;
for (i = 2; i <= n; i++)
{
dp[s[i - 1][s[i - 1] = NO_VALUE;
for (x = 1; x <= r; x++)
{
// printf("x : %d\n", x);
// sleep(1);
for (y = 1; y <= c; y++)
{
// printf("y : %d\n", y);
// sleep(1);
if (x != s[i - 1] || y != s[i - 1])
{
// printf("s[i - 1] = %d\ts[i - 1] = %d\n", s[i - 1], s[i - 1]);
// sleep(1);
int curr_dist = Manhattan(s, s, s[i - 1], s[i - 1]);
// printf("curr_dist = %d\n", curr_dist);
if (dp[i - 1] == NO_VALUE)
{
dp = NO_VALUE;
}
else
{
dp = dp[i - 1] + curr_dist;
dp[s[i - 1][s[i - 1] = minimum(dp[s[i - 1][s[i - 1], dp[i - 1] + Manhattan(x, y, s, s));
}
}
}
}
}
/* for (x = 1; x <= r; x++)
{
for (y = 1; y <= c; y++)
{
printf("%d\t", dp);
}
printf("\n");
}*/
printf("%d\n", min_all(dp, n, r, c));
return 0;
}

int Manhattan (int x1, int y1, int x2, int y2)
{
int x, y;
if (x1 >= x2)
{
x = x1 - x2;
}
else
{
x = x2 - x1;
}
if (y1 >= y2)
{
y = y1 - y2;
}
else
{
y = y2 - y1;
}
return x + y;
}

int minimum (int x, int y)
{
if (x == NO_VALUE)
{
return y;
}
else if (y == NO_VALUE)
{
return x;
}
else if (x > y)
{
return y;
}
else
{
return x;
}
}

int min_all (int pin, int i, int r, int c)
{
int min = NO_VALUE;
int j, k;
for (j = 1; j <= r; j++)
{
for (k = 1; k <= c; k++)
{
min = minimum(min, pin);
}
}
return min;
}

if you read it is NAB

A,B are the limitis of the city i want to do it smaller if you could help me

Don t see necesseraly the code if you have not the power

But if you could help me to tell me if i know the A,B -limitis of trip - how could make it better?? of N^2 or NAB

There is no better?