algorithm - 是否有一种算法可以在有向有根树(树状结构)中找到最小成本路径？

Question

更具体地说:我有一个有根树，它表示矩阵从第一个元素到最后一个元素的不同路径，只允许向右、向下和对角线向下移动。因此，每个节点最多可以有 3 个 child 。树将矩阵的第一个元素作为其根，每个最后一个节点将是矩阵的最后一个元素。每个节点代表一个成本。

这里有一个例子来说明我说的是哪种树:

此处最小成本路径为:1 -> 2 -> 9 或 [0,0,2] 在“坐标”中

那么有没有算法可以找到这种树的最小成本路径(我指的是路径而不是最小成本路径的总成本)？
如果是，是否有可能以递归方式实现它？

Answer 1

这可以在 O(n) 时间内完成，其中 n 是节点数。解决方案是递归的:

• 叶节点的最小成本路径是微不足道的 - 它只是节点本身，具有节点自身的成本。

• 要找到内部节点的最小成本路径，对其所有子节点进行递归调用，并选择成本最低的子节点作为其最小成本路径。路径的成本等于节点自身的成本加上该子节点的路径成本。

要恢复路径，只需从函数返回成本和路径。递归情况必须扩展当前节点的路径。

总运行时间为 O(n)，因为为内部节点完成的非递归工作与子节点数成正比。运行时间无法渐近改善，但可以在实践中使用 branch-and-bound algorithm 进行优化它跟踪到目前为止成本最低的路径，并拒绝超过它的路径。

---

这是 Python 中的示例:

class Node:
    def __init__(self, cost, children=()):
        self.cost = cost
        self.children = children
    def __repr__(self):
        return 'Node({})'.format(self.cost)

root = Node(1, (
    Node(2, (
        Node(5, (Node(9),)),
        Node(6, (Node(9),)),
        Node(9),
    )),
    Node(3, (
        Node(8, (Node(9),)),
        Node(9),
    )),
    Node(4, (Node(9),)),
))

def min_cost_path(node):
    if not node.children:
        return [node], node.cost
    else:
        # list of (path, cost) pairs
        options = [min_cost_path(c) for c in node.children]
        path, cost = min(options, key=lambda option: option[1])
        path.append(node)
        return path, cost + node.cost

例子:

>>> path, cost = min_cost_path(root)
>>> path
[Node(9), Node(2), Node(1)]
>>> cost
12

请注意，路径以相反的顺序返回。