找到最短距离，同时只访问每个节点一次

Question

出于练习的原因，我正在研究 Advent of Code 2015，并且卡在了 day 9。目标是找到最短距离，同时只访问图中的每个位置一次。每个点都直接相连，终点必须不同于起点。我制定了一个解决方案，但最终值不正确，我没有看到潜在的问题。

首先，我创建了一个包含位置和距离的图形对象。然后我将位置的每个排列收集到一个列表中，然后找到并总结每个排列的距离。最后打印出最小距离值，也就是习题的解法

代码：

from collections import defaultdict
from itertools import permutations

with open("input.txt") as file:
    input_ = file.read().split("\n")[:-1]

class Graph():
    def __init__(self):
        self.edges = defaultdict(list)
        self.weights = {}
    
    def add_edge(self, from_node, to_node, weight):
        self.edges[from_node].append(to_node)
        self.edges[to_node].append(from_node)
        self.weights[(from_node, to_node)] = weight
        self.weights[(to_node, from_node)] = weight

graph = Graph()

edges = [(i.split()[0], i.split()[2], int(i.split()[-1])) for i in input_]
for edge in edges:
    graph.add_edge(*edge)
    
loc_set = set([i[0] for i in edges])
routes = list(permutations(loc_set, len(loc_set)))

dists = []
for i in routes:
    print(i)
    dist_temp = []
    for k in range(len(i))[1:]:
        dist_temp.append(graph.weights[(i[k-1], i[k])])
    dists.append(sum(dist_temp))
    print(dist_temp)
    print(sum(dist_temp))
    
print(min(dists))

得到无效值后，我手动检查了一些排列及其对应的距离，因此在代码中打印。

输入（将其复制并粘贴到记事本并将其另存为 input.txt 对于我的代码应该可以正常工作）：

Faerun to Tristram = 65
Faerun to Tambi = 129
Faerun to Norrath = 144
Faerun to Snowdin = 71
Faerun to Straylight = 137
Faerun to AlphaCentauri = 3
Faerun to Arbre = 149
Tristram to Tambi = 63
Tristram to Norrath = 4
Tristram to Snowdin = 105
Tristram to Straylight = 125
Tristram to AlphaCentauri = 55
Tristram to Arbre = 14
Tambi to Norrath = 68
Tambi to Snowdin = 52
Tambi to Straylight = 65
Tambi to AlphaCentauri = 22
Tambi to Arbre = 143
Norrath to Snowdin = 8
Norrath to Straylight = 23
Norrath to AlphaCentauri = 136
Norrath to Arbre = 115
Snowdin to Straylight = 101
Snowdin to AlphaCentauri = 84
Snowdin to Arbre = 96
Straylight to AlphaCentauri = 107
Straylight to Arbre = 14
AlphaCentauri to Arbre = 46

我很确定，这个问题有更完善的解决方案，我愿意接受建议，因为我只是一个爱好者。但是，如果我们能够解决我的方法的缺点并使其正常工作，我会很高兴。

Answer 1

感谢 Setonix 的评论，我找到了错误！事实证明，该方法是有效的（它很可能离 TSP 的一个很好的实现很远，正如 Mark Ransom 所提到的，但它仍然可以正常工作！），我只是在定义位置集时粗心。

我假设每个位置在指令字符串的开头至少出现一次。但是，一个位置（“Arbre”）仅出现在说明的末尾。因此，图表不完整，因此输出错误。

作为快速修复，我按以下方式修改了代码：

loc_set = set([i[0] for i in edges])

到

loc_set = list(set([i[0] for i in edges]))
loc_set.append("Arbre")

此外，事实证明，顺便说一句，该方法对本练习很有用，因为第二部分要求最长距离，可以通过最后一行额外的代码找到：

print(max(dists))

找到最短距离，同时只访问每个节点一次

Find shortest distance, while visiting every node exactly once

python

graph

permutation