- Bitonic euclidean traveling-salesman problem
The euclidean traveling-salesman problem is the problem of determining the
shortest closed tour that connects a given set of n points in the plane. Figure 15.9(a)
shows the solution to a 7-point problem. The general problem is NP-complete, and
its solution is therefore believed to require more than polynomial time .
J. L. Bentley has suggested that we simplify the problem by restricting our attention to bitonic tours, that is, tours that start at the left most point, go strictly left
to right to the right most point, and then go strictly right to left back to the starting
point. Figure 15.9(b) shows the shortest bitonic tour of the same 7 points. In this
case, a polynomial-time algorithm is possible.
Describe an O(n
)- time algorithm for determining an optimal bitonic tour. You
may assume that no two points have the same x-coordinate. (Hint:Scan left to
right, maintaining optimal possibilities for the two parts of the tour.)
resimleri ekleyemedim boyut büyüktü diye yardımcı olabilirseniz resimleride eklerim.
22 May '13, 03:04
cevap kabul oranı: