1

私はこのDAGを持っています（二分木に似ていますが、グラフです..これには指定された名前がありますか？）： 連結二分木

(各番号はノードであり、ノード内の番号はたとえば、プログラムは乱数で実行する必要があります)

リストのリストとして表されます。

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

ノードの合計を最大化するパスを可能な限り機能的な方法で見つける必要があります。

[1,3,6]

私が検索したところ、これは projecteuler #18 と非常に似ていますが、project euler はパスの穴の合計を尋ねます。宿題では、合計だけでなくすべてのノードを見つける必要があります。私は自分の問題にいくつかの本当に良い解決策を適応させようとしましたが、うまくいきませんでした. いくつかのアドバイス？

4

3 に答える 3

1

あなたの問題を理解しているように、そのレベルの深さ n とランク r のノードは、ランク r と r+1 のレベル n+1 のノードに接続されます。

ダイレクト パスは確かに、入力として 1 つの DAG を取得する検索機能を使用して、何らかの再帰関係を探すことです。最大ウェイトを探すことから始めることもできます。これが機能する場合、ノードのリストを作成することは大きな問題にはなりません。

このパスに従って動作させました。使用したコードとテスト セットは以下のとおりです...ただし、主題を台無しにしないように、最も興味深い部分を削除しました。必要に応じて、さらにヒントを与えることができます。それはあなたが始めるためだけです。

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()
于 2011-03-08T01:49:14.970 に答える
1

最長経路問題のバリエーションのように見えます。ノードの値をエッジの重みとして扱う必要があります。

于 2011-03-08T00:30:39.183 に答える
1

これが「可能な限り機能的な方法」と見なされるかどうかはわかりませんが、適切でクリーンな実用的なソリューションです。それが役に立てば幸い！

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] です。

于 2011-03-08T03:02:45.323 に答える