python - DAG(一种连通二叉树)中的所有路径

Question

我有这个 DAG(它类似于二叉树，但它是一个图..有指定的名称吗？):

(每个数字是一个节点，节点中的数字为例，程序应该以随机数运行)

它表示为列表的列表:

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

我必须以尽可能更实用的方式找到最大化节点总和的路径:

[1,3,6]

我已经搜索过，这与projecteuler＃18非常相似，但是projecteuler询问路径的孔总和，在我的作业中，我不仅要找到总和，还要找到所有节点。我尝试过针对我的问题采用一些非常好的解决方案，但我没有成功。有什么建议吗？

Answer 1

据我了解您的问题，该级别的深度为 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()