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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58377 / )  Re[27]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (22回)-(2011/03/31(Thu) 17:23:46)
No58366 (shu さん) に返信
>>この問題プリム法では解けないことが簡単に示せます。
>>地点と道路が輪になった状態を考えただけでもすぐにわかります。
ワーシャルフロイド法を適用した後のグラフに、一回だけプリム法を適用するなら駄目です。
でもBの全ての組み合わせで試す場合は、何の問題もありません。
あるBの組み合わせでプリム法で解いて最善の答えを見逃す場合、その最善の答えは別のBの組み合わせで試した時のプリム法の答えになるので何の問題もないわけです。

>役に立つかは分かりませんがちょっと方法を変えて発電所と各地点との最短経路をまず求めそのうち一番短いものを固定化する。
>確定した経路からの最短経路を残りの地点で求め一番短いものを固定化する。を繰り返すというのはどうでしょう?
ちょっとまってください。
良く考えます。
私は決して理解力や思考力が高い法でないので、ちょっと考えさせてください。
なにか難しそうです。
返信 編集キー/


管理者用

- Child Tree -