Python訪問街區10個點，并倆倆繪制一條線，得到5條線，求最短的距離和？

• • 1. 效果圖
  • 2. 源碼
  • 參考

上一篇博客介紹了Python訪問街區所有節點最短路徑問題，并結合matplotlib可視化， 這一篇博客也基于博友的提問，將介紹平面圖中散落10個點，兩兩配對，共得5條邊，計算邊的長度和，如何找到長度和最小的配對方案？

依然以上一篇的10個街區點為例，理一下思路：

1. 10個點，倆倆配對，共得到5條邊，很明顯這是不考慮順序的?？梢杂酶咧袑W到的排列組合來計算共有：C(2,10) * C(2,8) * C(2,6) * C(2,4) * C(2,2) / A(5,5) 種組合方法
   = 10 * 9/(2 * 1) * (8 * 7/(2 * 1))*(6 * 5/(2 * 1)) * (4 * 3/(2 * 1)) * (2 * 1/(2 * 1))/ (5 * 4 * 3 * 2 * 1)
   = 45 * 28 * 15 * 6/(5 * 4 * 3 * 2 * 1)
   = 9 * 7 * 5 * 3 = 945種方法。

2. 計算每種路徑5條邊距離的總和

3. 找出距離總和最小的路徑，及對應的截取點坐標。

4. 為了方便理解，用matplotlib可視化。

1. 效果圖

5條線不考慮順序的排列組合共有945種，最短路徑為 ABDFCEGHIJ，距離和為449米，效果圖如下：

如下圖所示，10個街區 從A~J 用紅色五角星表示，最短路徑邊分別為AB、DF、CE、GH、IJ

2. 源碼

# 求最短路徑問題(N個點全排列）
import mathimport numpy as np# 街區點
node = ['A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', "J"]# 街區點對應坐標
node_coor = [(310, 385), (360, 305), (550, 330), (440, 270), (550, 250),(360, 225), (305, 150), (305, 90), (440, 120), (550, 65)]# 計算倆個坐標點的距離
def cal_dis(pt1, pt2):x0, y0 = pt1x1, y1 = pt2# print('\t\tdis: ', pt1, pt2, math.sqrt((math.pow((x0 - x1), 2) + math.pow((y0 - y1), 2))))return math.sqrt((math.pow((x0 - x1), 2) + math.pow((y0 - y1), 2)))# 計算一條路徑的總距離
def get_dis(nodes):# 初始化總距離total_dis = 0# 遍歷路徑for i in range(len(nodes) // 2):# 間隔2個點計算路徑 01 23 45 67 89dis = cal_dis(node_coor[node.index(nodes[i * 2])], node_coor[node.index(nodes[i * 2 + 1])])total_dis = total_dis + disreturn total_disprint('遞歸 start--------------------')
# 遞歸方法解決
nodes = node.copy()
path_set = set()# 排列組合（先2個全排列，然后每一小組排序忽略順序~）
# 相當于C(2,10)*C(2,8)*C(2,6)*C(2,4)*C(2,2)/A(5,5) = 10*9/(2*1)*(8*7/(2*1))*(6*5/(2*1))
# *(4*3/(2*1))*(2*1/(2*1))/ (5*4*3*2*1)
# = 45*28*15*6/(5*4*3*2*1)
# = 9*7*5*3 = 945種
def permutations(position):if position == len(nodes) - 2:# print(nodes, "".join(["".join(sorted(set(nodes[i * 2] + nodes[i * 2 + 1]))) for i in range(len(nodes) // 2)]))path_set.add("".join(["".join(sorted(set(nodes[i * 2] + nodes[i * 2 + 1]))) for i in range(len(nodes) // 2)]))else:for index in range(position, len(nodes)):nodes[index], nodes[position] = nodes[position], nodes[index]permutations(position + 2)nodes[index], nodes[position] = nodes[position], nodes[index]permutations(0)  # 全排列print(sorted(path_set))
print('共有路徑：', len(path_set))dict_path_dis = {}
# 計算距離
for path in path_set:dict_path_dis[path] = get_dis(list(np.array(list(path))))# 獲取最小的value對應的key，即獲取最短路徑距離對應的路徑
key_min = min(dict_path_dis.keys(), key=(lambda k: dict_path_dis[k]))
print('遞歸——Minimum path & dis: ', key_min, dict_path_dis[key_min])print('繪圖start——————————')
# 構建最短路徑的街區點及坐標
min_node = list(np.array(list(key_min)))
min_path_coor = []
for i in min_node:min_path_coor.append(node_coor[node.index(i)])print('min_node: ', min_node)
print('min_path_coor: ', min_path_coor)import matplotlib.pyplot as pltfig, ax = plt.subplots()  # 創建一個圖表
x1 = [x for (x, y) in min_path_coor]
y1 = [y for (x, y) in min_path_coor]for i, (node_name, (x, y)) in enumerate(zip(min_node, min_path_coor)):# 繪制坐標點及坐標點上方文字plt.scatter(x, y, s=120, c='red', marker='*')plt.text(x=x, y=y + 2, s=node_name + '(' + str(x) + ',' + str(y) + ')', ha='center', va='baseline',fontdict={'color': 'black','size': 8})  # 中心點上方文字if (i % 2 == 0):print(node_name, '->', min_node[i + 1])# print(i, i + 1, [x, min_path_coor[i + 1][0]], [y, min_path_coor[i + 1][0]])ax.plot([x, min_path_coor[i + 1][0]], [y, min_path_coor[i + 1][1]])  # 繪制線plt.show()

參考

• https://www.cnblogs.com/xiao-apple36/p/10861830.html

總結

以上是生活随笔為你收集整理的Python访问街区10个点，并俩俩绘制一条线，得到5条线，求最短的距离和？的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。