算法导论思考题15-3：双调欧几里得旅行商问题详解

（双调欧几里得旅行商问题）在欧几里得 旅行商问题 中，给定平面上 n n n个点作为输入，希望求出连接所有 n n n个点的最短巡游路线。下图(a)给出了一个7点问题的解。此问题是NP难问题，因此大家相信它并不存在多项式时间的求解算法（参见第34章）。

   　　J. L. Bentley建议将问题简化，限制巡游路线必须为双调巡游(bitonic tours)，即从最左边的点开始，严格向右前进，直至最右边的点，然后调头严格向左前进，直至回到起始点。下图(b)给出了相同7个点的最短双调巡游路线。问题简化之后，存在一个多项式时间的算法。

设计 一个 O ( n 2 ) O(n^2) O(n2)时间的最优双调巡游路线算法。你可以认为任何两个点的 x x x 坐标 均不同，且所有实数运算都花费单位时间。（提示：由左至右扫描，对巡游路线的两个部分分别维护可能的最优解。）

解

   　　对 n n n个点按 x x x坐标从小到大排序 p 1 , p 2 , … , p n p_1, p_2, … , p_n p1​,p2​,…,pn​，其中 p 1 p_1 p1​为最左边的点， p n p_n pn​为最右边的点。假设 P i , j ( i ≤ j ) P_{i,j} (i ≤ j) Pi,j​(i≤j)表示一条包含 p 1 , p 2 , … , p j p_1, p_2, … , p_j p1​,p2​,…,pj​的最短双调路径，这条路径从 p i p_i pi​向左直到 p 1 p_1 p1​，然后从 p 1 p_1 p1​向右直到 p j p_j pj​。显然， P n , n P_{n,n} Pn,n​就是本题需要求的路径。假设路径 P i , j P_{i,j} Pi,j​的长度为 l ( i , j ) l (i, j) l(i,j)，并且点 p i p_i pi​和 p j p_j pj​之间的距离为


   　　在路径 P i , j P_{i,j} Pi,j​中， p i p_i pi​一定在路径 p i → p 1 p_i→p_1 pi​→p1​中， p j p_j pj​一定在路径 p 1 → p j p_1→p_j p1​→pj​中。现在考虑 p j − 1 p_{j-1} pj−1​的位置，分以下几种情况：

   　　(1)  i < j − 1 i < j-1 i<j−1

   　　此时 p j − 1 p_{j-1} pj−1​在 p i p_i pi​的右边，故 p j − 1 p_{j-1} pj−1​只能出现在路径 p 1 → p j p_1→p_j p1​→pj​中。又由于 p j − 1 p_{j-1} pj−1​是路径 p 1 → p j p_1→p_j p1​→pj​中除 p j p_j pj​外的最右边的点，所以在路径中 p j − 1 p_{j-1} pj−1​直接跟 p j p_j pj​相连，如下图所示。


   　　根据以上分析，当 i < j − 1 i < j-1 i<j−1时，路径 P i , j P_{i,j} Pi,j​的长度等于路径 P i , j − 1 P_{i,j-1} Pi,j−1​的长度加上 ∣ ∣ p j − 1 p j ∣ ∣ || p_{j-1} p_j || ∣∣pj−1​pj​∣∣。于是可以得到以下递归式


   　　(2)  i = j − 1 i = j-1 i=j−1

   　　在这种情况下， p j − 1 p_{j-1} pj−1​即是 p i p_i pi​，所以 p j − 1 p_{j-1} pj−1​一定位于路径 p i → p 1 p_i→p_1 pi​→p1​上。而路径 p 1 → p j p_1→p_j p1​→pj​中直接跟 p j p_j pj​相连的点可以是 p 1 , p 2 , … , p j − 2 p_1, p_2, … , p_{j-2} p1​,p2​,…,pj−2​中的任意一点，假设该点为 p k ( 1 ≤ k ≤ j − 2 ) p_k (1 ≤ k ≤ j-2) pk​(1≤k≤j−2)。如下图所示。


   　　路径 P i , j P_{i,j} Pi,j​的长度等于路径 P k , j − 1 P_{k,j-1} Pk,j−1​的长度加上 ∣ ∣ p k p j ∣ ∣ || p_k p_j || ∣∣pk​pj​∣∣。要使得 P i , j P_{i,j} Pi,j​为最短双调路径，则必须选择合适的 p k p_k pk​使得 l ( i , j ) l (i, j) l(i,j)最小。于是可以得到以下递归式


   　　(3)  i = j i = j i=j

   　　在这种情况下， P i , j P_{i,j} Pi,j​是一条闭合路径。这种情况只会发生在 i = j = n i = j = n i=j=n，此时的路径为 P n , n P_{n,n} Pn,n​。此时 p j − 1 p_{j-1} pj−1​即为 p n − 1 p_{n-1} pn−1​，而 p n − 1 p_{n-1} pn−1​既可以在 p n → p 1 p_n→p_1 pn​→p1​上，也可以在 p 1 → p n p_1→p_n p1​→pn​上。而无论 p n − 1 p_{n-1} pn−1​在哪条路径， p n − 1 p_{n-1} pn−1​必然直接连接在 p n p_n pn​上，因为 p n − 1 p_{n-1} pn−1​是除 p n p_n pn​外的最右边的点。如下图所示。


   　　路径 P n , n P_{n,n} Pn,n​的长度等于路径 P n − 1 , n P_{n-1,n} Pn−1,n​的长度加上 ∣ ∣ p n − 1 p n ∣ ∣ || p_{n-1} p_n || ∣∣pn−1​pn​∣∣，即


   　　综合上述三种情况，路径 P i , j P_{i,j} Pi,j​的长度满足如下递归式


   　　根据以上的递归式，可以使用动态规划方法，按照自底向上的方式计算出最短双调路径 P n , n P_{n,n} Pn,n​的长度 l ( n , n ) l (n, n) l(n,n)。

   　　然而，我们应当如何得到最短双调路径本身，即路径中所有点的顺序？根据上面的递归过程，每次递归都会找出路径 P i , j P_{i,j} Pi,j​中与最右点 P j P_j Pj​直接相连的点，可以将这个点保存在数组 l e f t [ i , j ] left[i, j] left[i,j]中。从 P n , n P_{n,n} Pn,n​开始，依次找到每条路径的 l e f t [ i , j ] left[i, j] left[i,j]即可生成最短双调路径 P n , n P_{n,n} Pn,n​。


   　　本节相关的code链接。
https://github.com/yangtzhou2012/Introduction_to_Algorithms_3rd/tree/master/Chapter15/Problems/Problem_15-3

免责声明：本文系网络转载或改编，未找到原创作者，版权归原作者所有。如涉及版权，请联系删