我正努力解决欧拉项目作为学习Python的练习，在工作后的最后几天，我现在在Problem 18
我查看了这个问题，并认为可以通过使用Dijkstra算法解决，将节点的值作为负整数，以便找到“最长”的路径。
我的解决方案似乎几乎是正确的（我得到了1068） - 这就是说错了。它会打印一条路径，但据我所知，它不是正确的路径。但是从一段时间以来看过它，我不知道为什么。
也许这个问题不能通过我的方法解决，我需要一些其他的方法，比如动态编程 - 或者我的Dijkstra实现可能有问题？
我非常有信心从文件到图形的解析按预期工作。
这是数据集：
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
这是代码。它是一个完全“工作的例子”，只要具有上述内容的文件的路径是正确的。
class Graph:
def __init__(self):
self.nodes = []
self.edges = []
def add_node(self, node):
self.nodes.append(node)
def add_edge(self, edge):
self.edges.append(edge)
def edges_to_node(self, n):
edges = [edge for edge in self.edges if edge.node1.id == n.id]
return edges
class Node:
def __init__(self, id, value, goal):
self.id = id
self.value = value
self.goal = goal
self.visited = False
self.distance = 10000
self.previous = None
def __str__(self):
return "{} - {}".format(self.value, self.goal)
def __repr__(self):
return "{} - {}".format(self.value, self.goal)
class Edge:
def __init__(self, node1, node2):
self.node1 = node1
self.node2 = node2
f = open("problem18.data", "r")
content = f.read()
lines = content.split("\n")
data = []
graph = Graph()
index_generator = 1
last_line = len(lines) - 1
for i in range(len(lines)):
data.append([])
numbers = lines[i].split()
for number in numbers:
goal = i == last_line
data[-1].append(Node(index_generator, -int(number), goal))
index_generator += 1
for i in range(len(data)):
for j in range(len(data[i])):
node = data[i][j]
graph.add_node(node)
if i != last_line:
node2 = data[i+1][j]
node3 = data[i+1][j+1]
edge1 = Edge(node, node2)
edge2 = Edge(node, node3)
graph.add_edge(edge1)
graph.add_edge(edge2)
def dijkstra(graph, start):
start.distance = 0
queue = [start]
while len(queue):
queue.sort(key=lambda x: x.value, reverse=True)
current = queue.pop()
current.visited = True
if current.goal:
return reconstrcut_path(start, current)
edges = graph.edges_to_node(current)
for edge in edges:
neighbour = edge.node2
if neighbour.visited:
continue
queue.append(neighbour)
new_distance = current.distance + neighbour.value
if new_distance < neighbour.distance:
neighbour.distance = new_distance
neighbour.previous = current
return []
def reconstrcut_path(start, n):
path = []
current = n
while current.id is not start.id:
path.append(current)
current = current.previous
path.append(start)
return path
path = dijkstra(graph, graph.nodes[0])
tally = 0
for node in path:
number = max(node.value, -node.value)
print(number)
tally += number
print(tally)
你能帮我解决这个解决方案的问题吗？
编辑：运行的控制台输出：
98
67
91
73
43
47
83
28
73
75
82
87
82
64
75
1068
实际上，动态编程将彻底解决这个问题。我对此问题67的解决方案少于20行。
这里的重点是Dijkstra方法：沿着三角形向下工作，保持每个节点的最大路径成本。第1行是微不足道的：
75
第2行同样是微不足道的，因为两个值都是结束：每个只有一条可能的路径：
95+75 64+75
评估为
170 139
第3行有两端，但中间值给出了关键逻辑：保留两条路径中较大的一条：
17+170 47+max(170, 139) 82+139
187 217 221
第4行有两个中间...继续进行：
18+187 35+max(187, 217) 87+max(217, 221) 10+221
205 252 308 231
你能从这里拿走吗？
作为对你的检查，正确的答案非常接近你最初的答案。
您的解决方案失败，因为您没有应用Dijkstra的算法。这要求您保持在搜索中到达的每个节点的最佳路径。相反，你使用了逐行贪婪的algotriothm：你在整个传球中只保留了迄今为止最好的路径。
具体来说，当您在底行右侧附近发现98时，您强制假设它是最佳路径的一部分。你继续这一行，一行一行。数据集专门配置为使此方法失败。最好的路径从93 + 73 + 58序列开始。
你必须牢记所有的道路;有一条路径不是最下面一对行的最佳总和，但是在中间行捕获，而“胖”路径在中间有一些较低的数字。
考虑这个替代数据集：
01
00 01
00 00 01
00 00 00 01
99 00 00 00 01
至少在成本为负的情况下，Dijkstra将探索1s的路径和“刚刚离开路径”的零点，但没有别的。沿着该路径向下走1s的节点始终是队列中的最佳节点，并且它以目标节点结束，因此算法终止而不探索三角形的其余部分。它甚至不会看到左下角有99隐藏。