# 用贪婪算法解决邮差问题

2018-02-27 11:14:00来源:https://www.jianshu.com/p/5c4b17e6e7f8作者:不如葱油饼人点击

one出题

``import randomname = 'abcdefghijklmnopqrstuvwxyz'points = {}for i in name:    x = random.randint(0, 100)    y = random.randint(0, 100)    points[i] = (x, y)``

`{'a': (90, 65), 'b': (15, 12)...`

two距离计算函数

``def len_point(x, y):    a = (y[0] - x[0]) ** 2    b = (y[1] - x[1]) ** 2    c = a + b    length = round(c ** 0.5, 2)    return length``

three开始计算距离

``times = len(points) - 1  ``

``points_c = points.copy()min_p_group = ["a"]  # 给出一个列表存路径min_d_group = []  # 储存每次走的距离first_p = points_c["a"]  # 给出第一个点del points_c['a']  # 删除第一个点``

``for i in range(0, times):    key_points = []    for key in points_c.keys():        key_points.append(key)  # 计算还要走几个点    min_p = len_point(first_p, points[key_points[0]])  # 第一步    p_number = 0  # 重置点位置    for i in range(0, len(points_c)):        length = len_point(first_p, points[key_points[I]])        if length < min_p:            min_p = length  # 储存最短路径            p_number = i  # 储存最短路径的位置    min_p_group.append(key_points[p_number])  # 将最短路径的位置保存    min_d_group.append(min_p)    first_p = points_c[key_points[p_number]]  # 将最短路径位置保存下一个开始    del points_c[key_points[p_number]]  # 从字典里删除这个点``

``['a', 'v', 'd', 'p', 'j', 'x'...[6.08, 12.53, 9.06, 8.54...``

four画图

``points_d = points.copy()p_x = []  # 储存x坐标p_y = []  # 储存y坐标``

``for value in points_d.values():    x = value[0]    p_x.append(x)    y = value[1]    p_y.append(y)plt.subplots(2,2,figsize=(10,5))#规定两张图的尺寸plt.subplot(121)  # 第一张图for key in points_d.keys():    plt.annotate(key, xy=points_d[key])#给每个点标注plt.plot(p_x, p_y, 'o')``

``plt.subplot(122)  # 第二张图plt.title("TPS routes")for key in points_d.keys():    plt.annotate(key, xy=points_d[key])for i in range(0, times):    plt.plot([points_d[min_p_group[i]][0], points_d[min_p_group[i + 1]][0]],             [points_d[min_p_group[i]][1], points_d[min_p_group[i + 1]][1]], '-o')``

five大功告成
``plt.show() ``

six总结