You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
66 lines
2.2 KiB
66 lines
2.2 KiB
11 months ago
|
import numpy as np
|
||
|
|
|
||
|
|
def tsp_backtracking(distances):
|
||
|
|
num_cities = len(distances)
|
||
|
|
path = [0] # 起始城市为0
|
||
|
|
visited = [False] * num_cities
|
||
|
|
visited[0] = True
|
||
|
|
min_distance = float('inf')
|
||
|
|
shortest_path = None
|
||
|
|
|
||
|
|
def backtrack(curr_city, curr_distance, visited, path):
|
||
|
|
nonlocal min_distance, shortest_path
|
||
|
|
if len(path) == num_cities:
|
||
|
|
# 到达所有城市，更新最短路径
|
||
|
|
if curr_distance + distances[curr_city][0] < min_distance:
|
||
|
|
min_distance = curr_distance + distances[curr_city][0]
|
||
|
|
shortest_path = path + [0]
|
||
|
|
else:
|
||
|
|
for next_city in range(num_cities):
|
||
|
|
if not visited[next_city]:
|
||
|
|
# 选择下一个未访问的城市
|
||
|
|
visited[next_city] = True
|
||
|
|
path.append(next_city)
|
||
|
|
new_distance = curr_distance + distances[curr_city][next_city]
|
||
|
|
# 剪枝条件：当前路径已经大于最短路径，不继续搜索
|
||
|
|
if new_distance < min_distance:
|
||
|
|
backtrack(next_city, new_distance, visited, path)
|
||
|
|
# 回溯
|
||
|
|
visited[next_city] = False
|
||
|
|
path.pop()
|
||
|
|
backtrack(0, 0, visited, path)
|
||
|
|
return shortest_path
|
||
|
|
# 示例用法
|
||
|
|
# distances = np.array([
|
||
|
|
# [np.inf, 50, 99, np.inf, 64, np.inf],
|
||
|
|
# [50, np.inf, 12, 45, 74, 13],
|
||
|
|
# [99, 12, np.inf, 25, np.inf, 61],
|
||
|
|
# [np.inf, 45, 25, np.inf, 45, 47],
|
||
|
|
# [64, 74, np.inf, 45, np.inf, np.inf],
|
||
|
|
# [np.inf, 13, 61, 47, np.inf, np.inf]
|
||
|
|
# ])
|
||
|
|
# inf = np.inf
|
||
|
|
# distances = np.array(
|
||
|
|
# [[inf, 69, 48, inf, 41, 78],
|
||
|
|
# [69, inf, 48, 53, 91, inf],
|
||
|
|
# [48, 48, inf, 19, 86, inf],
|
||
|
|
# [inf, 53, 19, inf, 96, 10],
|
||
|
|
# [41, 91, 86, 96, inf, inf],
|
||
|
|
# [78, inf, inf, 10, inf, inf]]
|
||
|
|
# )
|
||
|
|
|
||
|
|
inf = float('inf')
|
||
|
|
|
||
|
|
distances = np.array([
|
||
|
|
[inf, 72, inf, inf, 81, 67],
|
||
|
|
[72, inf, 26, inf, 61, inf],
|
||
|
|
[inf, 26, inf, 53, 97, inf],
|
||
|
|
[inf, inf, 53, inf, inf, inf],
|
||
|
|
[81, 61, 97, inf, inf, 38],
|
||
|
|
[67, inf, inf, inf, 38, inf]
|
||
|
|
])
|
||
|
|
path = tsp_backtracking(distances)
|
||
|
|
if path:
|
||
|
|
print(path)
|
||
|
|
else:
|
||
|
|
print('不存在')
|