Re: A cycle with minimum length
- From: "Googmeister" <googmeister@xxxxxxxxx>
- Date: 31 Mar 2007 02:08:33 -0700
On Mar 31, 3:26 am, "Mahdi" <mahdi.dabest...@xxxxxxxxx> wrote:
Hello everyone!
We have n points in a chart that none of them have the same length(I
mean their 'x' parameter). We want to find a cycle with MINIMUM length
with these assumptions :
We start from the point with minimum length, meeting all of the points
and finally return to the starting point. We are allowed to change our
direction of moving only one time. I mean we go through more positive
points seeing some of them, and when we arrive to the rightest point,
we change our direction to the left, and seeing reminding points,
return to the starting point.
Let me give an example:
We have 3 points a,b,c :
a : x=2 y=0
b: x=10 y=8
c: x=17 y=0
one possible cycle is : a-->b-->c-->a
another : a-->c-->b-->a
One of them is shorter than the another.
thanks.
Sounds like the "bitonic traveling salesman problem."
You can solve it efficiently via dynamic programming.
.
- References:
- A cycle with minimum length
- From: Mahdi
- A cycle with minimum length
- Prev by Date: Re: A cycle with minimum length
- Next by Date: Re: A cycle with minimum length
- Previous by thread: Re: A cycle with minimum length
- Next by thread: A cycle with minimum length
- Index(es):
Relevant Pages
|
