Assignment # 2
Problem 15.1: Bitonic euclidean traveling-salesman problem
The euclidean traveling-salesman problem is the problem of determining the shortest closed tour that connects the given points in the plane. Figure 15.9 (a) show the solution to 7 point problem. The general problem is NP-complete and it 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 starts at the leftmost point, go strictly left to right to the rightmost point, 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.
Given a set of points on a same plane [p1, p2, ….pn] moving strictly from left to right and we can assume that there are no two points have the same x coordinate, if i < j then pi(xi,yj) and pj(xj,yj) with (xi<xj) then O(n²)- time algorithm can be used.
Assume that the optimal path from point pi to point pj is p(i,j) where i > j and for any k on that path pk with k < i, the problem can be solved by using recursion.
The optimal path between P2 and P1 can be generated as P(2,1) = |p2p1|. We can define P(i,j) as:
P(i,j) = min(P(i,j-1) + |pjpj-1|,P(j,j-1) + |pj+1pj-1| + Sj+1£k<i|Pk + 1Pk|
For any points of pk these points must be exist on the optimal path from p1 to pi since this path is bitonic path and pj is an end point, therefore point pj-1 can be either on the path from p1 to pi, or it on the path p1 to pj . P(i,j) is assigned to the shorter of the two paths.
To check the optimal paths: If pj-1 is on the path from p1 to pj then pj-1 has to be connected to pj. Therefore p(i,j) is optimal as long as p(i,j-1) is optimal. Vice versa if pj-1is on p1 to pi then pj-1 is connected to pj+1 and it is on the path from pj-1 to pi, which contains all point pk where j<k£i. P(i,j) is optimal if p(j,j-1) is optimal.
By calculating each subproblem using O(n²) in the correct order, we can calculate each constant time therefore the run-time is O(n²).
(Reference from “Dynamic – Programming – Study – Guide”).