<p>I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem.</p>

<p>From what I see, I need to sort the x-coordinates of the given set of points and then form a optimal path from the smallest x coordinate to the largest x coordinate.</p>

<p>For eg. (x1,y1) (x2,y2) ...(xn,yn) are sorted points. Isnt the optimal path simply x1,x2,x3,...xn-1,xn,xn-1,...,x3,x2,x1.</p>

<p>What am I missing here? How does dynamic programming come into picture here?</p>

CC BY-SA 3.0
2011-08-17T15:24:41.207Z
Not research level?
Mahdi Cheraghchi
CC BY-SA 3.0
2011-08-17T15:31:03.043Z
I have not consulted the book and I do not know which problem you are talking about, but if it is an exercise in the _Introduction to Algorithms_, then probably it is not suitable on cstheory.stackexchange.com.
Tsuyoshi Ito
CC BY-SA 3.0
2011-08-17T15:48:57.190Z
Vote to close. This is a homework exercise in Cormen, et al, and a complete answer can be found on the first link via Google by searching for the problem name.
Daniel Apon
CC BY-SA 3.0
2011-08-17T15:49:49.550Z
I am closing the question as off-topic, the question is probably more suitable for Math.SE, please refer to the [FAQ](http://cstheory.stackexchange.com/faq) to understand the scope of the site.
Kaveh
<ds.algorithms><dynamic-programming>
Cannot understand the problem of Bitonic Euclidean Traveling-Salesman
Arthur
# Cannot understand the problem of Bitonic Euclidean Traveling-Salesman

(Asked by: username_0 on 2011-08-17)

I am referring to the problem in Introduction to Algorithms. I kind of fail to understand the problem.

From what I see, I need to sort the x-coordinates of the given set of points and then form a optimal path from the smallest x coordinate to the largest x coordinate.

For eg. (x1,y1) (x2,y2) ...(xn,yn) are sorted points. Isnt the optimal path simply x1,x2,x3,...xn-1,xn,xn-1,...,x3,x2,x1.

What am I missing here? How does dynamic programming come into picture here?

**Tags:** ds.algorithms, dynamic-programming
> **Comments:**
> **username_1**: Not research level?  
> **username_2**: I have not consulted the book and I do not know which problem you are talking about, but if it is an exercise in the _Introduction to Algorithms_, then probably it is not suitable on cstheory.stackexchange.com.  
> **username_3**: Vote to close. This is a homework exercise in Cormen, et al, and a complete answer can be found on the first link via Google by searching for the problem name.  
> **username_4**: I am closing the question as off-topic, the question is probably more suitable for Math.SE, please refer to the [FAQ](http://cstheory.stackexchange.com/faq) to understand the scope of the site.  

---

## 0 answers

