找到你要的答案

Q:Finding the largest subsets of nodes in a tree subject to some constraints?

Q:找到一个树的最大子集的节点受到一定的限制?

Given a Tree like the following:

            X
    /               \
    1               6
/   |   \       /   |   \   
2   5   9       1   5   3
   ...             ...

For each node there is a number(except for the root), in the example the numbers are random.

If a node is taken, the next child-node of this node cannot be taken. But the child-child-node is allowed to take. So it's just not okay to take following nodes.

I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken.

I searched for solutions, I found the red-black-tree which is very similar but not really useful.

Any ideas on this?

给定一棵树如下:

            X
    /               \
    1               6
/   |   \       /   |   \   
2   5   9       1   5   3
   ...             ...

对于每个节点有一个数字(除了根),在示例中的数字是随机的。

如果采取了节点,则不能采取该节点的下一个子节点。但允许子节点。因此,这是不好的采取以下节点。

I'm searching for an algorithm which constructs a subset of all nodes which is has maximum amount(the sum of numbers of all taken nodes). The root has to be taken.

我寻找解决办法,我发现了红黑树非常相似,但不是真正有用的。

对此有何想法?

answer1: 回答1:

The problem you're trying to solve is called the maximum independent set problem applied to trees.

As a hint, think about the following:

  • For each complete subtree of the tree, think about the optimal solution for that subtree in two cases - the case where you include that node in the solution, and the case where you exclude that node from the solution.

  • Use dynamic programming: work from the leaves of the tree up to the root of the tree.

Hope this helps!

你试图解决的问题叫做应用于树的最大独立集问题。

作为提示,考虑以下内容:

  • 树的每一个完整的子树,子树,考虑最优解在两例的情况下,你的解决方案,包括节点的情况下,和你排除从解结。

  • 使用动态编程:从树的叶子到树的根。

希望这有助于!

tree  binary-search-tree  graph-algorithm  depth-first-search  breadth-first-search