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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58366 / )  Re[26]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ shu (593回)-(2011/03/31(Thu) 14:56:21)
No58365 (堀江伸一 さん) に返信

> 後、プリム法がダメな理由をお願いします。

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

より。




> 難しくて十分理解できたか自信がないのですが、この場合Bに電線の分岐点がある場合の視点が抜け落ちている?
> ような気もします。
> 私が間違ってるのか上記記述が間違っているのかどなたかご指摘お願いします。
役に立つかは分かりませんがちょっと方法を変えて発電所と各地点との最短経路をまず求めそのうち一番短いものを固定化する。確定した経路からの最短経路を残りの地点で求め一番短いものを固定化する。を繰り返すというのはどうでしょう?


返信 編集キー/


管理者用

- Child Tree -