算法导论思考题 15-1 双调欧几里得旅行商问题

瞳人


发布于 March 13, 2017, 2:34 p.m.

0 个评论

Algorithm


题目

Algorithm exercise 15-1

答案

网上参考答案

clrs 15-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)\}$ 如下:

  1. 若 $B(i, i)$ 取最小值时,$k=i-1$,易见相等。
  2. 当 $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

图像显示如下:

clrs 15-1 图形输出

参考链接

  1. https://www.cs.helsinki.fi/webfm_send/1449
  2. http://blog.csdn.net/z84616995z/article/details/38458183
  3. http://blog.csdn.net/mishifangxiangdefeng/article/details/7918983

哎呦, 不错哦!

0 Comments


Leave a Comment:

博客搜索

友情链接

公告

本博客代码已经公布在 Github 上,欢迎交流指正。

QQ 邮箱对 mailgun 不太友好, 所以使用 QQ 邮箱的评论, 可能会无法及时收到邮件。我会尽快寻找其他解决方案的。

本人现在独自使用 linode vps, 20 美元/月, 感觉压力大, 如果有意一起合租, 可以联系我. 在我的任意一篇文章下面留言即可. 关于使用方式, 现在倾向于使用 docker.