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

Question

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

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

此处的最小成本路径为：1 -> 2 -> 9 或 [0,0,2] in "coordinates"

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

Answer 1

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

叶节点的最小成本路径是微不足道的——它只是节点本身，加上节点自己的成本。
要找到内部节点的最小成本路径，对其所有子节点进行递归调用，然后 select 哪个子节点的最小成本路径的成本最低。路径的成本等于节点自身的成本加上该子节点的路径成本。

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

总运行时间为 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

注意路径是return倒序的。

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

Is there an algorithm to find the minimum cost path in a directed rooted tree (arborescence)?

algorithm

tree

directed-graph

path

minimum