3

これは、私が次の問題に煮詰めた、より大きな問題からのものです。エッジの重みが正で、葉が k 個ある重み付きツリーがあるとします。リーフは、ツリー内に隣接するノードが 1 つだけあるノードです。ツリーからいくつかのエッジを削除して、ツリーが k 個のコンポーネントに分割され、各コンポーネントに元のツリーのリーフ ノードが 1 つだけ含まれるようにする必要があります。つまり、元のツリーのすべての葉が元のツリーの他のすべての葉から分離/切断されるように、エッジを削除する必要があります。

削除されたエッジの重み (コスト) の合計が最小になるようにこれを行う必要があります。k-1 個のエッジを削除する必要があることを示すのは簡単です。したがって、これらの k-1 エッジの重みの合計を最小化する必要があります。

これを行う最適な方法は何ですか? ヒントをいただければ幸いです。ありがとう！

4

1 に答える 1

1

ここでは貪欲なアルゴリズムが機能すると思います。

つまり、新しいコンポーネントを生成する最小の重みのエッジを削除し、k-1 回繰り返します。

次のようなグラフには注意が必要です。

D<-A->B->C

最初に B->C を削除すると、A->B を削除しても新しいコンポーネントは生成されません。これは、B がリーフではなく、分離する必要がないためです。

つまり、最も重みの低いエッジを選択するときは、まだリーフ ノードにつながっていないエッジを含めないでください。

于 2012-10-06T19:31:18.190 に答える