独立したノードとは、返されるセットに直接関係のあるノードを含めることはできず、親と子の両方を含めることはできないことを意味します。Googleを使おうとしましたが、うまくいきませんでした。私は正しい検索語を持っていないと思います。
リンク、どんな助けでも大歓迎です。今これを始めたばかりです。
量だけでなく、実際の独立ノードのセットを返す必要があります。
質問する
2181 次
3 に答える
6
この再帰関数は、動的計画法 (メモ化) で計算できます。
MaxSet(node) = 1 if "node" is a leaf
MaxSet(node) = Max(1 + Sum{ i=0..3: MaxSet(node.Grandchildren[i]) },
Sum{ i=0..1: MaxSet(node.Children[i]) })
アイデアは、ノードを選択するか、選択しないことを選択できるということです。それを選択すると、直接の子を選択することはできませんが、孫から最大のセットを選択できます。選択しない場合は、直接の子から最大セットを選択できます。
セット自体が必要な場合は、ノードごとに「最大」を選択した方法を保存するだけです。これは、 LCS アルゴリズムに似ています。
このアルゴリズムは O(n) です。二分木だけでなく、木全般で機能します。
于 2009-10-14T16:47:59.557 に答える
0
最初にすべての葉を取得して削除し、親を非取得としてマークし、次にマークされたすべての葉をそのような葉がなくなるまで削除し、ツリーが空になるまで再帰します。これが常に可能な限り最大のセットを生成するという証拠はありませんが、そうすべきだと信じています。
于 2009-10-14T17:01:12.057 に答える