1

先生からその問題の動的計画法の解決策を教えてもらいましたが、グーグルで見つけられなかったので存在しないと思います。

とにかく、グラフとak、たとえば3が与えられた場合、そこから3つの最良のMSTを見つける必要があります。グラフがk個のサブツリーを持たないようなものである場合、同じツリーを複数回返すか、次善のツリーを返すことができます。

私はそれに対する解決策を本当に考えることができません。

4

1 に答える 1

3

あなたはそこでしばらく私を混乱させました、そして私はあなたが問題を誤解したかもしれないと思いました. "k-MST" 問題は、サブツリーを形成する k 個のエッジを見つけて、そのエッジの合計が、k 個のエッジのサブツリーから取得できる他のすべての合計以下になるようにすることで構成されます。しかし、その後、複数の s を見ました。

あなたの問題については、「次の」MSTを生成する方法と組み合わせたMSTを見つけるためのDPアルゴリズムを個人的に見つけようとします。これは動的プログラミングであるため、何かを繰り返し最適化する (この場合はステップごとに最適化を解除する) か、MST 設定で意味のあるサブセットにエッジを分割するさまざまな方法を調べます。いくつかの方法があるかもしれません。

ただし、パーティションと最小スパニングツリーを検索すると、これが見つかりました。答えが必要な場合は、これがより役立つかもしれません: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004

于 2010-07-10T10:31:04.833 に答える