algorithm - 二分木で最大独立集合のサイズを見つける-なぜ誤った「解決策」が機能しないのですか？

Question

良い答えのある同様の質問へのリンクは次のとおりです。バイナリツリーで独立したノードの最大のセットを見つけるためのJavaアルゴリズム。

私は別の答えを思いついたが、私の教授はそれがうまくいかないと言ったので、理由を知りたい（彼は電子メールに答えない）。

質問：

n個の整数を持つ配列Aが与えられると、そのインデックスは0で始まります（つまり、、、、A[0]… A[1]、A[n-1]）。A[i]Aは、の2つの子がA[2i+1]とである二分木として解釈できA[2i+2]ます。各要素の値はツリーのノードの重みです。このツリーでは、親子のペアが含まれていない場合、頂点のセットは「独立」していると言います。独立集合の重みは、その要素のすべての重みの合計にすぎません。独立集合の最大重みを計算するアルゴリズムを開発します。

私が思いついた答えは、二分木の独立集合について次の2つの仮定を使用しました。

同じレベルのすべてのノードは互いに独立しています。
交互のレベルのすべてのノードは互いに独立しています（親子関係はありません）

警告：私は試験中にこれを思いついたので、きれいではありませんが、少なくとも部分的なクレジットについて議論できるかどうかを確認したいだけです。

では、なぜ2つの独立したセット（1つは奇数レベル用、もう1つは偶数レベル用）を作成できないのでしょうか。

各セットの重みのいずれかが負でない場合は、それらを合計して（最大の重みセットに寄与しないため、負の要素を破棄します）、最大の重みを持つ独立集合を見つけます。

セット内の重みがすべて負（または0に等しい）の場合は、それを並べ替えて、重みの0に最も近い負の数を返します。

2つのセットのそれぞれから最大の独立集合の重みを比較し、それを最終的な解として返します。

私の教授はそれがうまくいかないと主張していますが、理由はわかりません。なぜうまくいかないのですか？

score 1 · Accepted Answer

インタージェイは、あなたの答えが間違っている理由を指摘しました。find-max-independentこの問題は、二分木が与えられた場合に2つのケースを考慮する再帰的アルゴリズムで解決できます。

ルートノードが含まれている場合、最大独立集合とは何ですか？
ルートノードが含まれていない場合、最大独立集合とは何ですか？

ケース1では、ルートノードが含まれているため、その子はどちらも含まれていません。したがってfind-max-independent、rootの孫の値とrootの値（含まれている必要があります）を合計し、それを返します。

ケース2では、子ノードの最大値がfind-max-independentあればそれを返します（1つしか選択できません）

アルゴリズムは次のようになります（Pythonの場合）。

def find_max_independent ( A ):
    N=len(A)

    def children ( i ):
        for n in (2*i+1, 2*i+2):
            if n<N: yield n

    def gchildren ( i ):
        for child in children(i):
            for gchild in children(child):
                yield gchild

    memo=[None]*N

    def rec ( root ):
        "finds max independent set in subtree tree rooted at root. memoizes results"

        assert(root<N)

        if memo[root] != None:
            return memo[root]

        # option 'root not included': find the child with the max independent subset value
        without_root = sum(rec(child) for child in children(root))

        # option 'root included': possibly pick the root
        # and the sum of the max value for the grandchildren
        with_root =  max(0, A[root]) + sum(rec(gchild) for gchild in gchildren(root))

        val=max(with_root, without_root)
        assert(val>=0)
        memo[root]=val

        return val


    return rec(0) if N>0 else 0

いくつかのテストケースを示します。

tests=[
    [[1,2,3,4,5,6], 16], #1
    [[-100,2,3,4,5,6], 6], #2
    [[1,200,3,4,5,6], 200], #3
    [[1,2,3,-4,5,-6], 6], #4
    [[], 0],
    [[-1], 0],
]

for A, expected in tests:
    actual=find_max_independent(A)
    print("test: {}, expected: {}, actual: {} ({})".format(A, expected, actual, expected==actual))

サンプル出力：

test: [1, 2, 3, 4, 5, 6], expected: 16, actual: 16 (True)
test: [-100, 2, 3, 4, 5, 6], expected: 15, actual: 15 (True)
test: [1, 200, 3, 4, 5, 6], expected: 206, actual: 206 (True)
test: [1, 2, 3, -4, 5, -6], expected: 8, actual: 8 (True)
test: [], expected: 0, actual: 0 (True)
test: [-1], expected: 0, actual: 0 (True)

テストケース1