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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58322 / )  Re[23]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (20回)-(2011/03/31(Thu) 00:56:03)
記述ミスがありました。
書き直します。

計算量は悪いですがワーシャルフロイド法とプリム法を組み合わせる方法を考えつきましgた。
まずワーシャルフロイド法で、各地点iからjへの最短距離を求め、これをmap[i][j]とします。


地点と道路のグラフをgとします。
一端gの辺を全て削除します。
次に、map[i][j]を点iからjへつながった辺と解釈しなおし辺を引き直します。
すると全ての点が、他の点とつながったグラフが得られます。
このグラフをnewGとします。

電線の分岐点の集合をB={B1,B2,,,,Bm-1}
目的地の集合を M={M1,M2,,,,Mm}
発電所を   Hとします。
とします。
注意点としてBi=BjやBi=Mj,Bi=Hという場合もあります。
Bi=BjならBjを削除し、Bi=Miや=HならBiを削除します。

あるBの組み合わせを考えたます。
まずnewGからB、M、Hの点とそれらをつなげる辺以外を無視します。
後はB,M、Hをつなげる最短の最小全域木をプリム法で求めます。
これでBがある組み合わせになった時の電線の最小距離を表す木構造が作られます。
このままでは答えになりません。
Biが木の葉になった場合があるので、葉になるBiがある限りBiを削除します。
これがBがあるセットになった時の電線の最小距離がでます。

後はこれを全てのBの組み合わせで試せば最小距離が出ます。
しかしこれは私が自分で思いついた素朴な方法ですのでもっとましな方法があると思います。
返信 編集キー/


管理者用

- Child Tree -