我正试图使用回溯来编写TSP问题的递归实现。
试了几次，但我刚刚完成，似乎奏效了。
但是它有点慢，所以我想办法改进它
def search_best_route(distance_matrix):
best_route = [None] * (len(distance_matrix[0]))
route = best_route.copy()
visited = [False] * (len(distance_matrix[0]))
current_distance = 0
return search_routes(0, route, best_route, -1, -1, current_distance, distance_matrix, visited, 0)
def search_routes(start_index1, route, best_route, min_distance, best_distance, current_distance, distance_matrix, visited, last_visited):
if start_index1 == len(route):
current_distance += distance_matrix[last_visited][0]
if current_distance < best_distance or best_distance == -1:
best_distance = current_distance
for k in range(0, len(route)):
best_route[k] = route[k]
else:
for k in range(len(route)):
if not visited[k]:
new_min = min_distance - distance_matrix[last_visited][k]
if new_min < best_distance or start_index1 == 0:
new_current_distance = current_distance + distance_matrix[last_visited][k]
route[start_index1] = k
visited[k] = True
best_distance = search_routes(start_index1 + 1, route, best_route, new_min, best_distance,
new_current_distance, distance_matrix, visited, k)[1]
visited[k] = False
return best_route, best_distance
def build_distance_matrix(x, y):
distance_matrix = [[0 for col in range(len(x))] for row in range(len(x))]
for i in range(len(x)):
for j in range(len(x)):
distance_matrix[i][j] = ((x[i] - x[j]) ** 2 + (y[i] - y[j]) ** 2) ** 0.5
return distance_matrix
n = int(input())
x = [None] * n
y = x.copy()
for i in range(n):
x_y = input()
x[i] = x_y.split()[0]
y[i] = x_y.split()[1]
x = list(map(float, x))
y = list(map(float, y))
best_route = search_best_route(build_distance_matrix(x, y))
print("%.4f" % best_route[1])
print(' '.join(map(str, best_route[0])))
很抱歉，如果我做错了什么，而你看着这个就要死了，哈哈。
一个可能会有所帮助的小更改是，您在每一步都迭代整个路由列表。你可以像递归排列枚举算法那样，通过维护一个尚未访问的点列表来保存一个因子n
从纸面上看，因子n可能看起来很多，但由于算法仍然是θ(n！(，因此在相同的运行时间内，改进相当于多了一个点。要做得更好，您需要实现分支和绑定。
基本的分支和绑定并不难实现，因为递归回溯已经是"分支和绑定"的大部分工作；分支"；部分最简单的边界策略是检查到目前为止的距离是否超过了当前的最小值，如果超过了，则拒绝探索分支。如果您首先探索最有前途的分支(例如，通过增加与当前点的距离来排列候选的下一个点(，效果会更好。
复杂性的一个进步是使用1-树绑定。给定其中一些点上的路径，我们想估计将其扩展到不经过的旅行的成本。每个这样的扩展都包括从给定路径中的最后一个点到某个未访问点的边，所有未访问点上的路径，以及从某个未访点返回到给定路径中第一个点的边。在未访问的点上获得路径的最小成本是困难的——这基本上是TSP。然而，我们可以通过计算这些点上最小生成树的代价来降低它，因为路径就是生成树。我们的最终估计是的总和
- 当前路径的成本
- 从当前路径中的第一个点到最近的未访问点的距离
- 从当前路径中的最后一个点到最近的未访问点的距离
- 未访问点上最小生成树的代价
根据你对数学的流利程度，有一整套关于精确TSP算法改进的文献。