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

わんくま同盟

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

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


(過去ログ 98 を表示中)
■58365 / )  Re[25]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (21回)-(2011/03/31(Thu) 14:28:09)
> 私が書いた方法を具体化しただけですね。プリム法は駄目なんじゃないの?
?
>賢くない方法ですが、抽出点i1〜imについてそれぞれの2点の最短経路を求めるとm点のグラフと同等になるので求められるんじゃないかな?
これのことでしょうか?
確かにヒントになってますね。
ありがとうございます、気付いてませんでした。
後、プリム法がダメな理由をお願いします。






リンク先掲示板で下記のような回答を頂きました。
http://www004.upp.so-net.ne.jp/s_honma/index.htm

>こんにちは。
>発電所の個数は1個だけであるとして考えます。
>以下のように考えれば(たぶん)よいのではないかと思います。
>与えられている n 個の地点とそれらをつなぐ何本かの道路の集合をグラフと考え、
>これをGとします。
>電気を送りたい m 個の地点と発電所を合わせた点集合をAとします。
>Gに属する点のうち、Aに属さないものの全体をBとします。
>Aに属する任意の2点p,qに対して、点集合{p}∪{q}∪Bによって生成される
>Gの点部分グラフをG_(p,q)とします。
>G_(p,q)の中でpとqを結ぶ最短経路の長さを求めます。
>この最短経路の長さをGにおけるpとqの距離とし、pとqを結ぶ辺上に書き込みます。
>(G_(p,q)の中でpとqを結ぶ経路がないときには何も書き込みません。)
>この作業をAに属する任意の2点に対して行います。
>すべての作業を終えた後のGをG_とし、Aによって生成されるG_の点部分グラフ
>は連結グラフになっているはずです。このグラフを A_ とします。
>A_に最小全点木の長さを求めるアルゴリズムを適用します。
>A_の最小全点木の長さが、敷設する電線の長さの総計の最小値です。


難しくて十分理解できたか自信がないのですが、この場合Bに電線の分岐点がある場合の視点が抜け落ちている?
ような気もします。
私が間違ってるのか上記記述が間違っているのかどなたかご指摘お願いします。
返信 編集キー/


管理者用

- Child Tree -