algorithm - 查找二叉树中最大独立集的大小 - 为什么错误的 "solution"不起作用？

Question

这是一个类似问题的链接，答案很好:Java Algorithm for finding the largest set of independent nodes in a binary tree .

我想出了一个不同的答案，但我的教授说它行不通，我想知道为什么(他不回复电子邮件)。

问题:

Given an array A with n integers, its indexes start with 0 (i.e, A[0], A[1], …, A[n-1]). We can interpret A as a binary tree in which the two children of A[i] are A[2i+1] and A[2i+2], and the value of each element is the node weight of the tree. In this tree, we say that a set of vertices is "independent" if it does not contain any parent-child pair. The weight of an independent set is just the summation of all weights of its elements. Develop an algorithm to calculate the maximum weight of any independent set.

我得出的答案使用了以下关于二叉树中独立集的两个假设:

1. 同一层级的所有节点相互独立。
2. 交替级别上的所有节点都相互独立(没有父/子关系)

警告:我在考试中想到了这个，它并不漂亮，但我只是想看看我是否可以至少获得部分学分。

那么，为什么不能只构建两个独立的集合(一个用于奇数级别，一个用于偶数级别)？

如果每个集合中的任何权重是非负的，则将它们相加(丢弃负元素，因为这不会对最大权重集有贡献)以找到具有最大权重的独立集合。

如果集合中的权重都是负数(或等于0)，则对其进行排序，返回最接近0的负数作为权重。

比较两个集合中每一个的最大独立集合的权重，并将其作为最终解决方案返回。

我的教授声称它行不通，但我不明白为什么。为什么它不起作用？

Answer 1

Interjay 已经注意到您的回答不正确的原因。这个问题可以用递归算法find-max-independent 来解决，给定一个二叉树，考虑两种情况:

1. 给定根节点的最大独立集是多少 包括？
2. 给定根节点的最大独立集是多少 不包括在内？

在情况 1 中，由于包含了根节点，因此它的子节点都不能。因此，我们将 root 的孙子的 find-max-independent 的值加上 root 的值(必须包括在内)相加，然后返回它。

在情况 2 中，我们返回子节点的 find-max-independent 的最大值，如果有的话(我们只能选择一个)

算法可能看起来像这样(在 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

测试用例2

测试用例 3

测试用例4

memoized 算法的复杂度为 O(n)，因为 rec(n) 为每个节点调用一次。这是一个使用深度优先搜索的自上而下的动态规划解决方案。

(测试用例插图由 leetcode 的交互式二叉树编辑器提供)