連結リスト (または有向非巡回グラフ) に似たグラフがあるとします。独立セットは、セット内の他のノードとエッジを共有しないノードで構成されます。各ノードが重み付けされている場合、ノードの独立したセットの最大可能値をどのように計算できますか? 動的プログラミングを使用する必要があることは理解しているので、少し手がかりがありますが、誰かがどのようにアプローチするかを説明してくれることを願っています. ありがとうございました！
質問する
2494 次
1 に答える
3
この問題は、任意の有向非巡回グラフでは NP 困難であると思います。無向グラフに対応する問題は NP 困難であることが知られており、その問題は、結果のグラフを DAG にする方法ですべてのエッジを方向付けることによって、問題の有向バージョンに変換できます。元のグラフの独立集合は有向グラフの独立集合になり、その逆も成り立つため、有向の場合の解は無向の場合を解決します。
あなたの質問は、リンクされたリストでこの問題を解決することについて語っています。リンクされたリストの問題だけを解決している場合は、動的計画法を使用した多項式時間のソリューションがあります。ヒントとして、リンクされたリストで 1 つのノードを選択した場合、次のノードをスキップする必要があり、残りを最大化する必要があります。ノードを選択しない場合は、リストの残りの値を最大化するだけです。これら 2 つのオプションの良い方を採用し、このボトムアップを評価すると、非常に高速な DP アルゴリズムが得られます。
お役に立てれば！
于 2014-10-19T22:01:48.480 に答える