- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
出于练习的原因,我正在研究 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
我很确定,这个问题有更完善的解决方案,我愿意接受建议,因为我只是一个爱好者。但是,如果我们能够解决我的方法的缺点并使其正常工作,我会很高兴。
最佳答案
感谢 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))
关于python - 找到最短距离,同时只访问每个节点一次,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/63691213/
Hackerrank - Dijkstra 最短距离 2 我被卡在了 TestCase 7(我唯一失败的一个),我认为这是我的错。我下载了测试用例并检查了我生成的输出。 我执行 git diff,我看
我是一名优秀的程序员,十分优秀!