весь путь в DAG (своего рода связное двоичное дерево)

Question

У меня есть этот DAG (он похож на двоичное дерево, но это граф .. имеет ли это указанное имя?):

(каждый номер - это узел и числа вузел, например, программа должна запускаться со случайными числами)

он представлен в виде списка списка:

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

мне нужно найти более функциональный способ, насколько это возможно, путькоторые максимизируют сумму узлов:

[1,3,6]

Я искал, и это действительно похоже на projecteuler # 18, но Project Euler спрашивает сумму дырки в пути, и в моей домашней работе я должен найти нетолько сумма, но все узлы.Я пытался адаптировать некоторые действительно хорошие решения для моей проблемы, но мне не удалось.какой-нибудь совет?

Answer 1

Как я понимаю, ваша проблема, узел глубины n и ранга r на этом уровне будет связан с узлами уровня n + 1 с рангом r и r + 1.

Прямой путь, безусловно, заключается в поиске некоторого рекуррентного отношения с использованием некоторой функции поиска, которая примет один из ваших символов в качестве входных данных. Конечно, вы можете начать с поиска максимального веса, когда это работает, и построение списка узлов не должно быть большой проблемой.

У меня он работал по этому пути, код и наборы тестов, которые я использовал, приведены ниже ... но я удалил самую интересную часть, чтобы не испортить тему. Я могу дать вам еще одну подсказку, если это необходимо. Это только начало.

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()

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

Похоже на вариацию проблемы самый длинный путь . Вам нужно будет обрабатывать значения узлов как веса ребер.