给出如下数据帧
names = ['a', 'b', 'c', 'b', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l']
x = [3, 6, 6, 10, 12, 15, 3, 6, 13, 9, 13, 12]
y = [9, 12, 9, 9, 12, 9, 6, 3, 8, 3, 1, 3]
目标:我的目标是找到最短路径起点' a '到最后一点,我的算法是这样后,我把第一点"a",找到最接近3点例如b, c和d, a和d之间的距离计算,这样dist1 = abcd和dist2 = acbd acbd是否比我矮点' c '下一跳如果不是然后b是下一跳,然后我搬到下一个点"b"假设"b"是最接近。
我已经非常接近解决它，但似乎我有一些逻辑错误，因为有跳跃点的最终列表有重复的点。
我代码:
def distance(p1, p2):
return math.sqrt((p2[0] - p1[0])**2 + (p2[1] - p1[1])**2)
def get_hops():
hopes = []
for i in range(len(x)):
for j in range(len(y)):
dist = distance((x[i], y[i]), (x[j], y[j]))
hopes.append({'from': names[i], 'to': names[j], 'dist': dist})
return hopes
def get_points(points):
point_1 = points[0]
point_2 = points[0]
point_3 = points[0]
for point in points:
if point['dist'] < point_1['dist']:
point_1 = point
if point['dist'] < point_2['dist'] and point['to'] != point_1['to']:
point_2 = point
if point['dist'] < point_3['dist'] and point['to'] != point_1['to'] and point['to'] != point_2['to']:
point_3 = point
return point_1, point_2, point_3
def get_optimal_path(names_list):
backup_list = []
for elm in names_list:
backup_list.append(elm)
points_list = [names_list[0]]
backup_list.remove(names_list[0])
hops = get_hops()
for elm in itertools.cycle(names_list):
if len(points_list) != len(backup_list)-3:
print(elm, points_list[-1])
if elm == points_list[-1]:
# get closet 3 points to the last point in path
hop_1 = {'from': 'qdsofhvcl', 'to': 'qjf', 'dist': 10000000000000}
hop_2 = {'from': 'qdsofhvcl', 'to': 'qjf', 'dist': 10000000000000}
hop_3 = {'from': 'qdsofhvcl', 'to': 'qjf', 'dist': 10000000000000}
for hop in hops:
if hop['from'] == elm and hop['to'] != elm and hop['dist'] < hop_1['dist']:
hop_1 = hop
for hop in hops:
if hop['from'] == elm and hop['to'] != elm and hop['dist'] < hop_2['dist'] and hop['to'] != hop_1['to']:
hop_2 = hop
for hop in hops:
if hop['from'] == elm and hop['to'] != elm and hop['dist'] < hop_3['dist'] and hop['to'] != hop_1['to'] and hop['to'] != hop_2['to']:
hop_3 = hop
# calculate dist_1 and dist_2 to determine optimal hoping point
dist_1 = 0
dist_2 = 0
for hop in hops:
if hop['from'] == elm and hop['to'] == hop_1['to']:
dist_1 += hop['dist']
if hop_1['from'] == hop['from'] and hop_2['to'] == hop['to']:
dist_1 += hop['dist']
if hop_2['to'] == hop['from'] and hop['to'] == hop_3['to']:
dist_1 += hop['dist']
if hop['from'] == elm and hop['to'] == hop_2['to']:
dist_2 += hop['dist']
if hop_2['to'] == hop['from'] and hop_1['to'] == hop['to']:
dist_2 += hop['dist']
if hop_1['to'] == hop['from'] and hop['to'] == hop_3['to']:
dist_2 += hop['dist']
# compare 2 distances and determine the best hoping point
if dist_1 < dist_2:
points_list.append(hop_1['to'])
print(backup_list)
# backup_list.remove(hop_1['to'])
else:
points_list.append(hop_2['to'])
print(backup_list)
# backup_list.remove(hop_2['to'])
else:
print('exit')
break
print(points_list)
任何建议都是非常感谢的，如果有新的排序方法，我是开放的，但我的算法是优先考虑的。
谢谢。
没有必要在这里重新发明轮子。从你的描述中，我有点不确定你到底需要什么，但这可能有效:Dijkstra的算法。你也可以查找更多的图算法，找到一个符合你需要的。
编辑:是的，它将返回一条路径，将所有点连接到距离最短的源顶点