最近、スパニングツリーの総コストが次のように与えられたグラフの最小コストスパニングツリーを計算するアルゴリズムを見つけることができましたか？それらの合計ではなくエッジコストの積である。エッジ重みを掛けることによってコストが与えられたときに最小スパニングツリーを見つけるアルゴリズム
通常のミニスパニングツリーを計算するアルゴリズムはいくつかありますが、上記のように調整する方法がわかりません。何か案は？
ありがとうございます。
log（エッジコストの積）= sum（log（エッジコスト））なので、エッジ重みをログ変換し、これらの重みの最小コストスパニングツリーを見つけます。
私のベストアイデア - ブルートフォースですべての最小限の（不必要なエッジを意味する）スパニングツリーを見つけて、最小の製品で1つを選んでください。
多くの（またはすべての）効率的なソリューションはもはや適用されません。主に最適なソリューションです。 （制限は何ですか？コストが1未満のエッジは実際に負のコストですが、長さ1のエッジはフリーです）。
この質問は本当に意味があるのか分かりません。 1つは、ゼロで製品を取ることができないため、自己ループコストをかける（または1と仮定する）必要があります。パスを分割するのは別の方法で、同じパスを2回移動するとc^2のコストがかかりますか？さらに、これは「コスト」とは異なる名前のパスの別の品質でなければならないと感じています
説明のために、すべてのコストは正の数は1以上です。 アイデアありがとうございます。 – AlexTex
対数は単調変換なので、すべてのログを取ると最小スパニングツリーはまったく同じになりますあなたがすべての体重を彼らのままにしておいたとき。 したがって、すべての重みの合計とすべての重みの積に応じてMSTを見つけることに違いはありません。グラフ の最小スパニングツリーは、グーグルでの最小スパニングツリーの タイプ佐賀graohにおける重みの単調変換に向かって不変である という事実の証拠の物品について
。 最初のリンクが必要なリンクになります。単調同型写像。
よろしくお願いします。なぜなら、コストはすべて正でなければならず、すべてが> 1でなければなりません。 –
@jon_darkstarあなたは正しいですが、すべて正でなければなりませんが、0-1の値はOKだと思います。結果として得られるツリーは最小コスト部分グラフではありません（余分なエッジを追加すると潜在的にコストが減少する可能性があります）が、最小コストは依然として_tree_です。 – Aniko
はい、あなたは正しいです、 '樹木'拘束はすでにそのような愚かさを禁じています。 –