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

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

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

Re[17]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと [2]


(過去ログ 98 を表示中)

[トピック内 48 記事 (41 - 48 表示)]  << 0 | 1 | 2 >>

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

>役に立つかは分かりませんがちょっと方法を変えて発電所と各地点との最短経路をまず求めそのうち一番短いものを固定化する。
>確定した経路からの最短経路を残りの地点で求め一番短いものを固定化する。を繰り返すというのはどうでしょう?
ちょっとまってください。
良く考えます。
私は決して理解力や思考力が高い法でないので、ちょっと考えさせてください。
なにか難しそうです。
引用返信 編集キー/
■58387 / inTopicNo.42)  Re[28]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ shu (595回)-(2011/04/01(Fri) 08:07:22)
2011/04/01(Fri) 08:34:00 編集(投稿者)

No58377 (堀江伸一 さん) に返信

> >役に立つかは分かりませんがちょっと方法を変えて発電所と各地点との最短経路をまず求めそのうち一番短いものを固定化する。
> >確定した経路からの最短経路を残りの地点で求め一番短いものを固定化する。を繰り返すというのはどうでしょう?
> ちょっとまってください。
> 良く考えます。
> 私は決して理解力や思考力が高い法でないので、ちょっと考えさせてください。
> なにか難しそうです。
ひとつ問題点をみつけたので提示しておきます。確定済みの経路の最後(端)の地点へ新しい地点がつながらない場合に
確定済みの地点から新しくつなげた経路への経路が存在するとき繋ぎなおしたほうが最短になるケースがあります。
確定済みの経路への接合点以降の地点について次の地点より新しい経路への経路の方が短い場合つなぎなおす必要がありそうです。そのとき接合点からのつなぎ直したところまでの間に指定地点がなければその辺は不要となりそうです。

引用返信 編集キー/
■58388 / inTopicNo.43)  Re[29]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (23回)-(2011/04/01(Fri) 14:19:07)
> ひとつ問題点をみつけたので提示しておきます。確定済みの経路の最後(端)の地点へ新しい地点がつながらない場合に
> 確定済みの地点から新しくつなげた経路への経路が存在するとき繋ぎなおしたほうが最短になるケースがあります。
> 確定済みの経路への接合点以降の地点について次の地点より新しい経路への経路の方が短い場合つなぎなおす必要がありそうです。そのとき接合点からのつなぎ直したところまでの間に指定地点がなければその辺は不要となりそうです。
>
何かいい感じですね、その考え方。
十分に理解できてませんが、原理的な感じがします。




私の方ではワーシャルフロイド法+Bの組み合わせを確定した後、プリム法がなぜ最善経路を見落とすかというと点について考えてみました。


S1 繋げる必要がないBに辺を繋げてしまう
S2 電線を重複して数えてしまう。

S1は明白です、プリム法は全部の抽出点を使いますがBは使わなくてもいい点なのですからBを使わない最小木が可能性として存在します。

S2は簡単な場合を考えればわかります。
地点1,2,3が目的地と発電所、4,5がその他の地点とします。
B={空集合}としてmap[1][3]とmap[2][3]をつなげるのが最短と出た場合、

map[1][3]が1,4,5,3という経路に,map[2][3]が2,5,3という経路なら
5,3という経路が重複しておりこれを足してしまいます。
これがグラフnewGからBを選び、これにプリム法を適用した後プリム法が最善経路を見落とす原因になります。

これを改善できればもしかしたら直接解を見つけられるかもしれません。


newGには特徴が一つあります。
newGは、ある地点iからjを直接結びますが、iからjへの最短経路なので,iから他の点を通ってjに向かう経路は全てi,jより遠回りになります。
この特徴を上手く使えるかもしれません。

色々考えてはいますが、グラフ理論をきちんと学んだ人からみたら私は滑稽なのかも?
ちゃんと勉強すればこの問題教科書に書いてあったりして?
とかは少し考えたりします。
引用返信 編集キー/
■58390 / inTopicNo.44)  Re[30]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (24回)-(2011/04/01(Fri) 16:20:16)
この問題解決しました。
http://www004.upp.so-net.ne.jp/s_honma/index.htm
最小シュタイナー木という方法で解けるそうです。

私に理解できるかどうか分かりませんが、理解頑張ってみます。
shuさんありがとうございました。
引用返信 編集キー/
■58391 / inTopicNo.45)  Re[31]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 堀江伸一 (25回)-(2011/04/01(Fri) 16:38:10)
解決マーク忘れていました。

リンク先で教えてもらった資料を読む限りこの問題、NP困難なために素人の生兵法的正攻法では計算量を下げることができないようです。

現実的なサイズになると遺伝的アルゴリズムのような高度な手法を使い最適解でなく準最適解を求める。
というのが限界のようです。

shuさん本当にありがとうございました。
解決済み
引用返信 編集キー/
■58394 / inTopicNo.46)  Re[17]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ 魔界の仮面弁士 (2150回)-(2011/04/01(Fri) 17:03:08)
No58296 (堀江伸一 さん) に返信
> >マルチポストについて
> 両方にリンクを張りつけますし、解決したら両方に情報を掲載しますよ。

あちらの掲示板に対しては、トップページ
 http://bbs.wankuma.com/
ではなく、具体的な投稿先の URL
 http://bbs.wankuma.com/index.cgi?mode=al2&namber=58179
をリンクしていますよね。

情報共有という意図であれば、こちらにもフレームトップの URL ではなく、
該当記事の URL (もしくは、トップから該当文書にたどり着けるだけの情報) を
投稿したほうが、双方向的になるかと思いますよ。

(とはいえ、過去ログに入ってしまうと URL が変わってしまうのですけれどね…)
解決済み
引用返信 編集キー/
■58399 / inTopicNo.47)  Re[32]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ shu (596回)-(2011/04/01(Fri) 22:04:33)
No58391 (堀江伸一 さん) に返信
> 解決マーク忘れていました。
>
> リンク先で教えてもらった資料を読む限りこの問題、NP困難なために素人の生兵法的正攻法では計算量を下げることができないようです。
>
> 現実的なサイズになると遺伝的アルゴリズムのような高度な手法を使い最適解でなく準最適解を求める。
> というのが限界のようです。
リンク先のシュタイナー木というのを見てみましたがこれは指定点以外は無数ある未指定点より確定するときの話のようですね。
そうすると今回の問題をNP困難な問題とこのリンクにより決めるのは早い気がします。
他いろいろ調べて頑張ってください。
解決済み
引用返信 編集キー/
■58402 / inTopicNo.48)  Re[33]: n点のグラフの中からm点を選び、m点を結ぶ最小全域木を選ぶと
□投稿者/ shu (598回)-(2011/04/02(Sat) 14:01:20)
No58399 (shu さん) に返信

http://keisan-genkai.lab2.kuis.kyoto-u.ac.jp/reports/2007/NHC-Report-part-C.pdf
によるとやはりNP困難問題であるようでした。
O(3^k)
で求めるアルゴリズムを与えたとあります。1点増えると最低でも3倍時間はかかるけど
なんとかみつけることが可能ということみたいです。

解決済み
引用返信 編集キー/

<前の20件
トピック内ページ移動 / << 0 | 1 | 2 >>

このトピックに書きこむ

過去ログには書き込み不可

管理者用

- Child Tree -