C# と VB.NET の質問掲示板

わんくま同盟

ASP.NET、C++/CLI、Java 何でもどうぞ

C# と VB.NET の入門サイト


(過去ログ 98 を表示中)
■58190 / )  Re[2]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (4回)-(2011/03/28(Mon) 17:16:24)
全域木の場合しか扱ってないので参考になりません。
私が求めたいのは2点間をつなげる最小距離とn点の全域木以外のその中間の場合なのです。



例えば、問題に直すとこういうイメージです。

ある電気の全く通ってない発展途上国で発電所を作り電力を流すことになりました。
電気を必要とする地点はn点ありますが、元の発電所の能力が低いために全部に流すことはできません。

病院などの優先度の高い地点にだけ電気を通すことになりました。
地点は0〜n-1までの番号が付けられており、それらを結ぶ道路が何本かあります。
電線は道路にそって敷設されることとなり、各地点は道路でつながっています。
特定の2点間を結ぶ道路が複数あたえられた場合一番短かい道路が経路として選択されます。
(地点と道路はグラフの関係になっています)

以下の情報が与えられます。
道路がつながっている2地点の番号とその距離。
電気を送りたい地点の数mとその地点の番号がm個、発電所のある地点の番号が情報として与えらます。
指定されたm個の地点全てに電気を流す必要があります。
発電所から到達できない地点はないと仮定して、敷設する電線の長さの総計が最小になるアルゴリズムか考え方を書いてください。

問題終わり。

この問題プリム法では解けないことが簡単に示せます。
地点と道路が輪になった状態を考えただけでもすぐにわかります。


一応私としてはワーシャルフロイド法で経路のコストを求めた後、最小木の分岐点を決めるための再帰を使う方法を考えていますが、
分岐点のつなげ方をどうすればいいのか思いつかない状態です。
返信 編集キー/


管理者用

- Child Tree -