有向无环图中的所有路径（连接的二叉树的一种）

Question

我有一个有向无环图（DAG），它看起来有点像二叉树，但其实是个图形。这个东西有没有特别的名字呢？

（每个数字代表一个节点，节点里的数字是程序运行时用的随机数）

这个图用一个列表的列表来表示：

[[1],[2,3],[4,5,6]]

我需要以尽可能更有效的方式找到一条路径，使得节点的总和最大：

[1,3,6]

我查了一下，这个问题和Project Euler的第18题非常相似，但Project Euler要求的是路径的总和，而我这个作业不仅要找出总和，还要找出所有的节点。我尝试过把一些很好的解决方案改编成适合我问题的，但没成功。有没有什么建议？

Answer 1

这看起来像是一个变种的最长路径问题。你需要把节点的值当作边的权重来处理。

Answer 2

我不知道这算不算“尽可能更函数化的方式”，但这是一个不错、干净、有效的解决方案。希望对你有帮助！

import random

class Tree(object):
    def __init__(self, depth=5, rng=None, data=None):
        super(Tree,self).__init__()
        if data is None:    # generate a random tree
            if rng is None:
                _ri = random.randint
                rng = lambda:_ri(1,20)
            self.tree = [[rng() for i in range(d+1)] for d in range(depth)]
        else:               # copy provided data
            self.tree = [row[:] for row in data]

    def copy(self):
        "Return a shallow copy"
        return Tree(data=self.tree)

    def maxsum(self):
        "Find the maximum achievable sum to each point in the tree"
        t = self.tree
        for row in range(1,len(t)):
            t[row][0] += t[row-1][0]
            for i in range(1,row):
                t[row][i] += max(t[row-1][i-1], t[row-1][i])
            t[row][row] += t[row-1][row-1]
        return self

    def maxpath(self):
        """Find the path (list of per-level indices)
        which leads to the greatest sum at the bottom of the tree.
        Note: only makes sense when applied to a summed tree.
        """
        t = self.tree
        maxval = max(t[-1])                    # find highest value in last row
        maxi = t[-1].index(maxval)
        path = [maxi]
        for row in range(len(t)-2, -1, -1):    # work backwards to discover how it was accumulated
            if maxi==0:
                maxi = 0
            elif maxi==row+1:
                maxi = row
            elif t[row][maxi-1] > t[row][maxi]:
                maxi -= 1
            path.append(maxi)
        path.reverse()
        return path

    def pathvalues(self, path):
        "Return the values following the given path"
        return [row[i] for row,i in zip(self.tree,path)]

    def __str__(self, width=2):
        fmt = '{0:>'+str(width)+'}'
        return '\n'.join(' '.join(fmt.format(i) for i in row) for row in self.tree)

    def solve(self, debug=False):
        copy = self.copy()
        maxpath = copy.maxsum().maxpath()
        origvalues = self.pathvalues(maxpath)
        sumvalues = copy.pathvalues(maxpath)
        if debug:
            print 'Original:'
            print self, '  ->', origvalues
            print 'Tree sum:'
            print copy, '  ->', sumvalues
        return origvalues

def main():
    tree = Tree(data=[[1],[2,3],[4,5,6]])
    solution = tree.solve(debug=True)

if __name__=="__main__":
    main()

结果是

Original:
 1
 2  3
 4  5  6   -> [1, 3, 6]
Tree sum:
 1
 3  4
 7  9 10   -> [1, 4, 10]

返回的结果是 [1,3,6]。

Answer 3

根据我对你问题的理解，深度为 n、等级为 r 的节点会和深度为 n+1、等级为 r 和 r+1 的节点连接在一起。

解决这个问题的直接方法是寻找一些递归关系，使用某种搜索函数，这个函数会把你的有向无环图（dags）作为输入。你可以先尝试找出最大权重，当这个方法有效时，构建节点列表也应该不会太难。

我之前就是按照这个思路来做的，下面有我用的代码和测试集……不过我把最有趣的部分去掉了，以免剧透。如果需要的话，我可以给你一些额外的提示。这只是为了帮助你入门。

import unittest

def weight(tdag, path):
    return sum([level[p] for p, level in zip(path,tdag)])

def search_max(tdag):
    if len(tdag) == 1:
        return (0,)
    if len(tdag) > 1:
        # recursive call to search_max with some new tdag
        # when choosing first node at depth 2
        path1 = (0,) + search_max(...)
        # recursive call to search_max with some new tdag 
        # when choosing second node at depth 2
        # the result path should also be slightly changed
        # to get the expected result in path2
        path2 = (0,) + ...
        if weigth(tdag, path1) > weigth(tdag, path2):
            return path1
        else:
            return path2

class Testweight(unittest.TestCase):
    def test1(self):
        self.assertEquals(1, weight([[1]],(0,)))

    def test2(self):
        self.assertEquals(3, weight([[1], [2, 3]],(0, 0)))

    def test3(self):
        self.assertEquals(4, weight([[1], [2, 3]],(0, 1)))

class TestSearchMax(unittest.TestCase):

    def test_max_one_node(self):
        self.assertEquals((0,), search_max([[1]]))

    def test_max_two_nodes(self):
        self.assertEquals((0, 1), search_max([[1], [2, 3]]))

    def test_max_two_nodes_alternative(self):
        self.assertEquals((0, 0), search_max([[1], [3, 2]]))

    def test_max_3_nodes_1(self):
        self.assertEquals((0, 0, 0), search_max([[1], [3, 2], [6, 4, 5]]))

    def test_max_3_nodes_2(self):
        self.assertEquals((0, 0, 1), search_max([[1], [3, 2], [4, 6, 5]]))

    def test_max_3_nodes_3(self):
        self.assertEquals((0, 1, 1), search_max([[1], [2, 3], [4, 6, 5]]))

    def test_max_3_nodes_4(self):
        self.assertEquals((0, 1, 2), search_max([[1], [2, 3], [4, 5, 6]]))

if __name__ == '__main__':
    unittest.main()