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

Question

出于练习的原因，我正在研究 Advent of Code 2015，但我被困在了第 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

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

Answer 1

我发现了错误！事实证明，该方法是有效的，我只是在定义位置集时粗心了。我假设每个位置在指令字符串的开头至少出现一次。然而，一个位置（“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))