随机生成点的坐标并依据点集生成距离矩阵，通过点的坐标实现可视化
c代码看我的这篇文章tsp动态规划递归解法c++
from typing import List, Tuple
import matplotlib.pyplot as plt
from random import randintN: int = 4
MAX: int = 0x7f7f7f7fdistances: List[List[int]] = [[0 for _ in range(N)] for _ in range(N)]
path: List[List[int]] = [[0 for _ in range(1 << (N - 1))] for _ in range(N)]
dp: List[List[int]] = [[0 for _ in range(1 << (N - 1))] for _ in range(N)]
points: List[Tuple[int, int ]]def creatDistances():global distances, dp# for i in range(N):# for j in range(N):# if i == j:# distances[i][j] = MAX# else:# temp = randint(1, 10)# while temp == 0:# temp = randint(1, 10)# distances[i][j] = temp# x=[[MAX, 3, 6, 7],# [5, MAX, 2, 3],# [6, 4, MAX, 2],# [3, 7, 5, MAX]]# for i in range(N):# for j in range(N):# distances[i][j] = x[i][j]creatpoints()for i in range(N):dp[i][0] = distances[i][0]def printDistances():global distancesprint("代价矩阵为：")for i in range(N):for j in range(N):if distances[i][j] == MAX:s = "INF"print(f"{s:<17}", end=" ")else:print(f"{distances[i][j]:<17}", end=" ")print()for i, point in enumerate(points):plt.text(*point, f'{i }', fontsize=12, ha='center', va='bottom')plt.scatter(*zip(*points))def removeCity(j: int, k: int) -> int:return j - (1 << (k - 1))def printPath(i: int, j: int) -> None:if j != 0:print(f"{i} -> ", end="")next_city = path[i][j]plt.plot((points[i][0],points[next_city][0]), (points[i][1],points[next_city][1]))printPath(next_city, removeCity(j, next_city))else:print(f"{i} -> {0}")plt.plot((points[i][0],0), (points[i][1],0))def creatpoints() ->None:ldasc: int = 1hdasc: int = 10dapr: int = N - 1global pointspoints = [(0,0)]+[(randint(ldasc, hdasc), randint(ldasc, hdasc)) for i in range(dapr)]for i in range(N):for j in range(i, N):if i == j:distances[i][j] = MAXelse:distances[i][j] = distances[j][i] = ((points[i][0]-points[j][0])**2+(points[i][1]-points[j][1])**2)**.5
def drewpoints() ->None:global pointsdef TSP(v: int, s: int) -> int:global distances, dp, pathif dp[v][s] != 0:return dp[v][s]min = MAXfor k in range(1, N):if ((s >> (k - 1)) & 1) == 1:t = TSP(k, removeCity(s, k))if (t + distances[v][k]) < min:min = t + distances[v][k]path[v][s] = kdp[v][s] = minreturn minif __name__ == "__main__":creatDistances()printDistances()print(f"最短距离为：{TSP(0, (1 << (N - 1)) - 1)}")print("最短路径为：")printPath(0, (1 << (N - 1)) - 1)print(points)plt.show()