如何改进我的 TSP 实施？ （使用回溯）（Python）
How to improve my TSP implementation ? (Using Backtracking) (Python)
我正在尝试使用回溯编写 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-tree bound。给定一些点上的路径，我们想估计将其扩展到游览而不经过的成本。每个这样的扩展都包含从给定路径中的最后一个点到某个未访问点的边，所有未访问点上的路径，以及从某个未访问点返回到给定路径中第一个点的边。在未访问点上获得路径的最小成本很困难——这基本上就是 TSP。然而，我们可以通过计算这些点上最小生成树的成本来降低它，因为路径是生成树。我们的最终估计是
- 当前路径的开销，
- 当前路径中的第一个点到最近的未访问点的距离，
- 当前路径最后一个点到最近的未访问点的距离，
- 未访问点上最小生成树的成本。
从那里开始，根据您对数学的熟练程度，有一整套关于改进精确 TSP 算法的文献。
我正在尝试使用回溯编写 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-tree bound。给定一些点上的路径，我们想估计将其扩展到游览而不经过的成本。每个这样的扩展都包含从给定路径中的最后一个点到某个未访问点的边，所有未访问点上的路径，以及从某个未访问点返回到给定路径中第一个点的边。在未访问点上获得路径的最小成本很困难——这基本上就是 TSP。然而，我们可以通过计算这些点上最小生成树的成本来降低它，因为路径是生成树。我们的最终估计是
- 当前路径的开销，
- 当前路径中的第一个点到最近的未访问点的距离，
- 当前路径最后一个点到最近的未访问点的距离，
- 未访问点上最小生成树的成本。
从那里开始，根据您对数学的熟练程度，有一整套关于改进精确 TSP 算法的文献。