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

わんくま同盟

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

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


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


管理者用

- Child Tree -