Author |
Topic: Two-Person Traversal of a Sequence of Cities (Read 7287 times) |
|
S4T4N
Newbie
Posts: 1
|
 |
Two-Person Traversal of a Sequence of Cities
« on: Jun 19th, 2009, 11:50am » |
 Quote  Modify
|
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/
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender: 
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #1 on: Jun 20th, 2009, 4:34am » |
Quote Modify
|
I can do it in O(n2)
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)
|
|
IP Logged |
|
|
|
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: Jun 20th, 2009, 5:30am » |
Quote Modify
|
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.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Obob
Senior Riddler
Gender:
Posts: 489
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #3 on: Jun 20th, 2009, 9:53am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
nakli
Junior Member
 
Gender:
Posts: 62
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #4 on: Sep 28th, 2009, 1:26am » |
Quote Modify
|
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
|
| « Last Edit: Sep 28th, 2009, 1:42am by nakli » |
IP Logged |
I was born naked on a bed with a lady.
|
|
|
R
Senior Riddler
Addicted!!!
Gender:
Posts: 502
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #5 on: Sep 28th, 2009, 12:04pm » |
Quote Modify
|
What I understood from the question is that we are given n cities in a certain order:
A1, A2, A3, ....An.
Along with that we are given distance between each pair of cities, Ai,j for all 1 i,jn.
We have to divide it in two sequences,
Ai1, Ai2, Ai3, ....Aik.
Aj1, Aj2, Aj3, ....Ajk.
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.
|
|
IP Logged |
The first experience seems like Magic, but the second tells you the Trick behind it.
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Two-Person Traversal of a Sequence of Cities
« Reply #6 on: Jan 10th, 2012, 9:35am » |
Quote Modify
|
(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"?
|
|
IP Logged |
|
|
|
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 #7 on: Jan 10th, 2012, 9:46am » |
Quote Modify
|
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? |
|
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print