找出最短路径，要求恰好访问每个节点一次。

Question

为了练习，我正在做2015年的编程挑战活动“Advent of Code”，目前卡在第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

我相信在这个问题上有更加精细的解决方案，因为我只是一个业余爱好者，所以我很乐意听取建议。然而，如果我们能够找出我的方法存在的缺陷并使其正常工作，我会非常高兴。

- Márton Szekeres

---

你的情况是否类似于这个？如果是，我可以提供帮助。 - Ann Zen

你能否修改这行代码 loc_set = set([i[0] for i in edges])，使其也添加 i[1]？ - Setonix

Ann Zen：目标是在图中找到最短路径。然而，起点和终点节点没有预定义，唯一的要求是恰好访问图中的每个节点一次。Setonix：那会如何帮助呢？ - Márton Szekeres

这被称为旅行商问题，它并不像看起来那么简单。 - Mark Ransom

Answer 1

感谢Setonix的评论，我已经找到了错误！事实证明，这种方法是有效的（正如Mark Ransom所提到的，它可能远非TSP的良好实现，但它仍然是功能性的！），我只是在定义位置集时有些粗心。

我假设每个位置都至少在指令字符串的开头出现一次。然而，一个位置（“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))

- Márton Szekeres