python - Project Euler Problem #18 Python - 得到错误的结果。为什么？

Question

在下类后的最后几天，我正在尝试解决 Euler 项目作为学习 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

Answer 1

实际上，动态规划可以巧妙地解决这个问题。我对此问题和问题 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 算法。这要求您维护在搜索中到达的每个 节点的最佳路径。相反，您使用了逐行贪婪算法:您在整个过程中只保留了到目前为止的最佳路径。

具体来说，当您在底行右侧附近找到 98 时，您强制假设它是最佳路径的一部分。你一行一行地继续这个。数据集专门配置为使此方法失败。最佳路径以 93 + 73 + 58 序列开始。

您必须牢记所有路径；有一条路径不是底部几行的最佳总和，但在中间的行中 catch 了，而“胖”路径在中间的一些较低的数字中变得饥饿。