算法导论思考题 15-1 双调欧几里得旅行商问题
由 瞳人
发布于 March 13, 2017, 2:34 p.m.
1 个评论
题目
答案
网上参考答案
我的思考
由于双调旅程的性质，我们可以知道第 \( n \) 个结点一定与第 \(n-1\) 个结点相连，否则违反严格从左至右然后从右至左的性质。因此，\(d(n-1, n)\) 不变，问题其实就变成求最小的 \(B(n-1, n )\)，\(B\) 和 \(d\) 的定义如英文参考一致，即 \(B(i, j)\) 表示两条路径 \(1 \rightsquigarrow i\) 和 \( 1 \rightsquigarrow j \) 的最小和，其中 \( 1 \leqslant i \leqslant j \leqslant n\)，且这两个路径上除了\( 1 \)以外所有的点都不重合，并且覆盖了所有 \( 1 \) 到 \( \max(i, j) \) 的点，\(d(i, j)\) 表示这两个结点间距。
对于 \( i == j \) 这个情况，其实我们是不需要考虑的。因为从上述分析中，我们知道我们只需要求最小的 \(B(n-1, n )\) 且该问题不依赖于 \(B(i, i)\)。不过即使要求这个 \(B(i, i)\)，同上述分析，我们也不需要遍历求最小值，可以直接求 $B(i, i) = B(i-1, i) + d(i-1, i)$。
数学化的证明 $B(i-1, i) + d(i-1, i) = \min_{1\leqslant k < i} \{ B(k, i) + d(k, i)\}$ 如下：
- 若 $B(i, i)$ 取最小值时，$k=i-1$，易见相等。
- 当 $1\leqslant k < i-1$ 时，由上面英文答案中的 Case 1 可以知道，此时有 $B(k, i) = B(k, i-1) + d(i-1, i)$。因此，可得 \begin{eqnarray*} B(i, i) &=& \min_{1\leqslant k < i-1} \{ B(k, i) + d(k, i) \} \\ &=& \min_{1\leqslant k < i-1} \{ B(k, i-1) + d(i-1, i) + d(k, i)\} \\ &=& \min_{1\leqslant k < i-1} \{ B(k, i-1) + d(k, i)\} + d(i-1, i) \\ &=& B(i-1, i)+ d(i-1, i) \qquad \textrm{By Case 2, where $i = j - 1$} \end{eqnarray*}
证毕。
其他就如英文答案一样，总结一下，对于 $1 \leqslant i < j \leqslant n$：（注意是 $i < j$）
\[ B(i, j) = \left\{ \begin{array}{ll} B(i, j-1) + d(j-1, j) & \textrm{if $j > i+1$} \\ \min_{1\leqslant k < i} \{ B(k, i) + d(k, i)\} & \textrm{if $j = i+1$} \end{array} \right. \]
在求得最短双调闭合路线的长度之后，我们应该要打印出该路线，但是我发现我参考的答案（除了上述英文答案）都一致地没有提到这一点。根据上述英文答案，我想了很久，还问了师兄（我发现我真是太笨了。。）。。直接看代码大家就能理解了。
代码
其中 s[i][j]表示 $B(i+1, j+1)$，pre 用来记录 Case 2 中非连续的前驱信息。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 | # coding=utf-8 import math import plotly from plotly.graph_objs import Scatter __author__ = 'answ.me' class Location: def __init__(self, x, y): self.x = x self.y = y def __str__(self): return '(%s, %s)' % (self.x, self.y) def distance(locations, a, b): return math.sqrt((locations[a].x - locations[b].x) ** 2 + (locations[a].y - locations[b].y) ** 2) def bentley_shortest_tour(locations): locations.sort(key=lambda l: l.x) n = len(locations) s = [[0 for x in range(n)] for y in range(n)] pre = [0 for x in range(n)] s[0][1] = distance(locations, 0, 1) for j in range(2, n): # calculate s[1..j-2][j] for i in range(j-1): s[i][j] = s[i][j-1] + distance(locations, j-1, j) # calculate s[j-1][j] pre[j], s[j-1][j] = min(((k, s[k][j-1]+distance(locations, k, j)) for k in range(j-1)), key=lambda x: x[1]) return s[n-2][n-1] + distance(locations, n-2, n-1), pre def print_path(pre, i, j): """ Assume j > i """ if j > i+1: print(j-1, ' -> ', j) print_path(pre, i, j - 1) else: # j = i + 1 if i == 0: print(i, ' -> ', j) else: print(pre[j], ' -> ', j) print_path(pre, pre[j], i) def calculate_path(l, pre, i, j): res = [] if j > i+1: res.extend([(l[j-1].x, l[j-1].y, l[j].x, l[j].y)]) res.extend(calculate_path(l, pre, i, j-1)) else: if i == 0: res.extend([(l[i].x, l[i].y, l[j].x, l[j].y)]) else: res.extend([(l[pre[j]].x, l[pre[j]].y, l[j].x, l[j].y)]) res.extend(calculate_path(l, pre, pre[j], i)) return res def plot_path(l, pre): path = [Scatter( x=[l[-2].x, l[-1].x], y=[l[-2].y, l[-1].y], showlegend=False, hoverinfo='skip', line={ 'color': 'black', } )] for x1, y1, x2, y2 in calculate_path(l, pre, len(l)-2, len(l)-1): path.append( Scatter( x=[x1, x2], y=[y1, y2], showlegend=False, hoverinfo='skip', line={ 'color': 'black', } )) plotly.offline.plot(path) if __name__ == '__main__': def test(): xys = ( (1, 7), (2, 1), (3, 4), (6, 5), (7, 2), (8, 6), (9, 3), ) locations = [Location(x, y) for x, y in xys] d, pre = bentley_shortest_tour(locations) print([str(x) for x in locations]) print('distance: ', d) print_path(pre, len(xys) - 2, len(xys) - 1) plot_path(locations, pre) test() |
输出：
1 2 3 4 5 6 7 8 | ['(1, 7)', '(2, 1)', '(3, 4)', '(6, 5)', '(7, 2)', '(8, 6)', '(9, 3)'] distance: 25.58402459469133 4 -> 6 3 -> 5 1 -> 4 2 -> 3 0 -> 2 0 -> 1 |
图像显示如下：
参考链接
- https://www.cs.helsinki.fi/webfm_send/1449
- http://blog.csdn.net/z84616995z/article/details/38458183
- http://blog.csdn.net/mishifangxiangdefeng/article/details/7918983
瞳人 Dec. 9, 2019, 3 p.m. | Reply
test comment
1 Comments