最近、特定のグラフの最小コストスパニングツリーを計算するアルゴリズムを見つけることができるかどうか尋ねられました。スパニングツリーの合計コストは、エッジコストの合計ではなく、積によって与えられます。
通常のミニウムスパニングツリーを計算するためのいくつかのアルゴリムがありますが、上記の場合にそれらを微調整する方法がわかりません。何か案は？
ありがとうございました。
3473 次
3 に答える
17
log（エッジコストの積）=合計（log（エッジコスト））なので、エッジの重みを対数変換し、これらの重みの最小コストスパニングツリーを見つけます。
于 2010-11-18T19:53:12.877 に答える
4
対数は単調変換であるため、すべての重みの対数を取得する場合と、すべての重みをそのままにしておく場合の最小全域木はまったく同じになります。したがって、すべての重みの合計とすべての重みの積に従ってMSTを見つけることに違いはありません。
グラフの最小スパニングツリーがグラオの重みの単調変換に対して不変であるという事実の証明の記事については、googleで「最小スパニングツリーの佐賀」と入力してください。そして、最初のリンクはあなたが必要とするものになります。ページ167、単調同型。
于 2011-07-14T08:15:45.360 に答える
0
私の最善のアイデア-ブルートフォースによってツリーにまたがるすべての最小（不要なエッジを意味する）を見つけ、最小の製品を持つものを選択します。
ほとんど（またはすべて）のより効率的なソリューションは適用されなくなりました。主にbcの最適なソリューションには、必ずしも最適なサブ問題が含まれていません。（制限は何ですか？非常に重要です-1未満のコストのエッジは実際には負のコストであり、長さ1のエッジは無料です。それらはすべて正です！）
この質問が本当に意味があるかどうかはわかりません。1つは、ゼロの製品を取得できないため、自己ループコストを与える（または1を想定する）必要があります。パスの分割は別の方法で機能します。同じパスを2回移動すると、c ^ 2のコストがかかりますか？さらに、これは「コスト」とは異なる名前のパスの異なる品質でなければならないように感じます
于 2010-11-18T19:55:00.653 に答える