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

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

one出题

import random
name = '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总结