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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58194 / )  Re[4]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (5回)-(2011/03/28(Mon) 18:36:27)
No58193 (shu さん) に返信
> ■No58190 (堀江伸一 さん) に返信
>
> m個の地点以外が入っても有効ということですか?
> m個だけだったらそこに含まれない地点との辺は削ればいいかと思ったのですが。

はい、電線の総計が最小になるならどんなルートでもいいです。


余談ですが、この問題m=2の場合は簡単です。
発電所をh,電気を流したい地点をm1,m2とします。
地点iとjを結ぶ最短距離をmap[i][j]と表現する時、map[m1][k]+map[m2][k]+map[h][k]が最小となる地点kを電線の分岐点とすればいいだけです。

これがmが一般になると途端に難しくなります。
どの地点を電線の分岐点とし分岐点どうしの繋げ方をどうするか、組み合わせの問題がたちあがってきてます。

ワーシャルフロイド法のような賢い方法が必要になってくるようです。
グラフ理論の中では初歩だと思うので何か賢い方法があるとは思うのですが。
返信 編集キー/


管理者用

- Child Tree -