给出python代码,随机给出50个二维坐标点,使用启发式算法解决包含这50个点的旅行商问题,最终将路线绘制为动画
时间: 2023-03-07 14:09:53 浏览: 49
import random
import matplotlib.pyplot as plt
import matplotlib.animation as animation
# 随机产生50个坐标点
points = []
for i in range(50):
point = [random.randint(0, 100), random.randint(0, 100)]
points.append(point)
# 使用启发式算法解决旅行商问题
def solve_tsp(points):
current_point = points[0]
not_visited_points = points[1:]
route = [current_point]
while len(not_visited_points) > 0:
nearest_point = min(not_visited_points, key=lambda x: get_distance(current_point, x))
route.append(nearest_point)
not_visited_points.remove(nearest_point)
current_point = nearest_point
return route
# 获取两个点之间的距离
def get_distance(point1, point2):
return ((point1[0] - point2[0])**2 + (point1[1] - point2[1])**2)**0.5
# 将路线绘制为动画
def draw_animation(points, route):
fig = plt.figure(dpi=128, figsize=(10, 6))
ax = plt.subplot()
x, y = [], []
for point in points:
x.append(point[0])
y.append(point[1])
plt.scatter(x, y, s=10)
line, = ax.plot([], [], 'r-')
def animate(i):
line.set_data([route[i][0], route[i + 1][0]], [route[i][1], route[i + 1][1]])
return line,
a = animation.FuncAnimation(fig, animate,
frames=len(route) - 1, interval=200, repeat=False, blit=True)
plt.show()
route = solve_tsp(points)
draw_animation(points, route)