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

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

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

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

(過去ログ 98 を表示中)

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

■58179 / inTopicNo.1)

　ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▼■

□投稿者/ 堀江伸一 (2回)-(2011/03/28(Mon) 15:46:15)

分類:[C/C++]　

グラフに関する質問です。

重み付きグラフ内の2点間の最短距離を求めるなら、ダイクストラ法。
全部の点を辺で結ぶ時、辺の長さの計の最短を求めるなら、最小全域木。

では辺で結ばれたｎ点のグラフがある時、その中から指定されたm点を選び、このｍ点を結ぶ最小全域木の作り方はどうなるのでしょうか？

3点を結ぶ場合はワーシャルフロイド法で最小コストを求め、3点を結ぶ最小全域木の分岐点を探せばいいだけでした。

この方法では4,5、、n-1点と一般になると手に負えません。
どなたか良い方法のご紹介をお願いします。

引用返信 編集キー/

■58180 / inTopicNo.2)

　Re[1]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ shu (567回)-(2011/03/28(Mon) 16:04:48)

■No58179 (堀江伸一さん) に返信

いい方法かは分かりませんが、参考になりますか？
http://www.deqnotes.net/acmicpc/prim/

引用返信 編集キー/

■58190 / inTopicNo.3)

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

▲▼■

□投稿者/ 堀江伸一 (4回)-(2011/03/28(Mon) 17:16:24)

全域木の場合しか扱ってないので参考になりません。
私が求めたいのは2点間をつなげる最小距離とｎ点の全域木以外のその中間の場合なのです。

例えば、問題に直すとこういうイメージです。

ある電気の全く通ってない発展途上国で発電所を作り電力を流すことになりました。
電気を必要とする地点はｎ点ありますが、元の発電所の能力が低いために全部に流すことはできません。

病院などの優先度の高い地点にだけ電気を通すことになりました。
地点は0～ｎ-1までの番号が付けられており、それらを結ぶ道路が何本かあります。
電線は道路にそって敷設されることとなり、各地点は道路でつながっています。
特定の2点間を結ぶ道路が複数あたえられた場合一番短かい道路が経路として選択されます。
（地点と道路はグラフの関係になっています）

以下の情報が与えられます。
道路がつながっている２地点の番号とその距離。
電気を送りたい地点の数mとその地点の番号がm個、発電所のある地点の番号が情報として与えらます。
指定されたｍ個の地点全てに電気を流す必要があります。
発電所から到達できない地点はないと仮定して、敷設する電線の長さの総計が最小になるアルゴリズムか考え方を書いてください。

問題終わり。

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

一応私としてはワーシャルフロイド法で経路のコストを求めた後、最小木の分岐点を決めるための再帰を使う方法を考えていますが、
分岐点のつなげ方をどうすればいいのか思いつかない状態です。

引用返信 編集キー/

■58193 / inTopicNo.4)

　Re[3]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ shu (571回)-(2011/03/28(Mon) 17:51:25)

■No58190 (堀江伸一さん) に返信

ｍ個の地点以外が入っても有効ということですか？
ｍ個だけだったらそこに含まれない地点との辺は削ればいいかと思ったのですが。

引用返信 編集キー/

■58194 / inTopicNo.5)

　Re[4]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (5回)-(2011/03/28(Mon) 18:36:27)

■No58193 (shu さん) に返信
> ■No58190 (堀江伸一さん) に返信
>
> ｍ個の地点以外が入っても有効ということですか？
> ｍ個だけだったらそこに含まれない地点との辺は削ればいいかと思ったのですが。

はい、電線の総計が最小になるならどんなルートでもいいです。

余談ですが、この問題ｍ=2の場合は簡単です。
発電所をh,電気を流したい地点をm1,m2とします。
地点iとjを結ぶ最短距離をmap[i][j]と表現する時、map[m1][k]+map[m2][k]+map[h][k]が最小となる地点ｋを電線の分岐点とすればいいだけです。

これがｍが一般になると途端に難しくなります。
どの地点を電線の分岐点とし分岐点どうしの繋げ方をどうするか、組み合わせの問題がたちあがってきてます。

ワーシャルフロイド法のような賢い方法が必要になってくるようです。
グラフ理論の中では初歩だと思うので何か賢い方法があるとは思うのですが。

引用返信 編集キー/

■58197 / inTopicNo.6)

　Re[5]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ shu (572回)-(2011/03/28(Mon) 21:31:19)

■No58194 (堀江伸一さん) に返信

> 余談ですが、この問題ｍ=2の場合は簡単です。
> 発電所をh,電気を流したい地点をm1,m2とします。
> 地点iとjを結ぶ最短距離をmap[i][j]と表現する時、map[m1][k]+map[m2][k]+map[h][k]が最小となる地点ｋを電線の分岐点とすればいいだけです。

賢くない方法ですが、抽出点i1～imについてそれぞれの２点の最短経路を求めるとｍ点のグラフと同等になるので求められるんじゃないかな？

引用返信 編集キー/

■58201 / inTopicNo.7)

　Re[6]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (6回)-(2011/03/28(Mon) 22:20:53)

■No58197 (shu さん) に返信
> ■No58194 (堀江伸一さん) に返信
>
>>余談ですが、この問題ｍ=2の場合は簡単です。
>>発電所をh,電気を流したい地点をm1,m2とします。
>>地点iとjを結ぶ最短距離をmap[i][j]と表現する時、map[m1][k]+map[m2][k]+map[h][k]が最小となる地点ｋを電線の分岐点とすればいいだけです。
>
> 賢くない方法ですが、抽出点i1～imについてそれぞれの２点の最短経路を求めるとｍ点のグラフと同等になるので求められるんじゃないかな？
>
その方法は無理ではないでしょうか？
電線を途中まで共有するという視点が抜け落ちてしまいます。

引用返信 編集キー/

■58202 / inTopicNo.8)

　Re[7]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 翔泳みきお (1回)-(2011/03/28(Mon) 22:54:08)

■No58201 (堀江伸一さん) に返信
うむ。
実際にコードを書いてみてください。

不具合のある箇所があれば、

ボクが修正してみますけど。

引用返信 編集キー/

■58220 / inTopicNo.9)

　Re[8]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (7回)-(2011/03/29(Tue) 13:51:28)

>実際にコードを書いてみてください。
どうやって解いたらいいかわからないから質問してるのですが。
ｍ＝３くらいまでは力づくで解けそうですが、一般のｍの解き方は思いつかない状態です。
グラフ理論に詳しい方なら何かいい方法を知ってそうだと期待もするのですが。

引用返信 編集キー/

■58221 / inTopicNo.10)

　Re[9]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 鬼塚 (1回)-(2011/03/29(Tue) 14:06:28)

分類がC/C++になっているけど、
C/C++の問題ではなくてアルゴリズムの問題じゃないの？

引用返信 編集キー/

■58224 / inTopicNo.11)

　Re[10]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (8回)-(2011/03/29(Tue) 15:40:33)

■No58221 (鬼塚さん) に返信
> 分類がC/C++になっているけど、
> C/C++の問題ではなくてアルゴリズムの問題じゃないの？

アルゴリズムという分類ありませんし、私の場合最近C++を良く使ってるのでC++で返事が頂けたらと考えてC++という分類で質問しました。
何か気になりましたか？

引用返信 編集キー/

■58231 / inTopicNo.12)

　Re[11]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 鬼塚 (2回)-(2011/03/29(Tue) 17:21:16)

言いたいことは、例えばアルゴリズムが明確で、それをコード化するにはどうすればいいかという質問であれば、
ここでも多くの回答を期待できるが、アルゴリズムについての質問であれば、（難しいものであればある程）
ここで回答を得ることは難しいのではないかということだ。
知恵袋などで質問した方が多くの意見を得られるのでは？

もっとも、これが学校の宿題・研究課題などについての質問ではないことを祈る。

引用返信 編集キー/

■58236 / inTopicNo.13)

　Re[12]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (9回)-(2011/03/29(Tue) 17:44:25)

■No58231 (鬼塚さん) に返信
> 言いたいことは、例えばアルゴリズムが明確で、それをコード化するにはどうすればいいかという質問であれば、
> ここでも多くの回答を期待できるが、アルゴリズムについての質問であれば、（難しいものであればある程）
> ここで回答を得ることは難しいのではないかということだ。
> 知恵袋などで質問した方が多くの意見を得られるのでは？
>
> もっとも、これが学校の宿題・研究課題などについての質問ではないことを祈る。

知恵袋の場合見当外れの答えを自信満々で記載してくる方が多い感じで、あまり使えないのです。
後この問題については純粋な知的好奇心からの質問です。

引用返信 編集キー/

■58238 / inTopicNo.14)

　Re[13]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 翔泳ミキオ (1回)-(2011/03/29(Tue) 18:07:03)

■No58236 (堀江伸一さん) に返信
>
ミニマムコードが1行も書かれていないので、本当にシープラを勉強しているのか疑問ですね。
で、もっと、簡単なスグに作れるもののコードを書いてみてください。

たとえば、中心点から円周のA点（35度）と円周のB点（78度）の点と点を結ぶプログラムを書いてみて。

コレ簡単なんで、コレくらいができないレベルであれば、貴殿は貴殿が質問したコードはかけませんよ。

引用返信 編集キー/

■58239 / inTopicNo.15)

　Re[14]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 堀江伸一 (11回)-(2011/03/29(Tue) 18:59:52)

GUIでですか？
普通に質問しただけでこういう対応されるというのが意味がよくわからないのですが？

会津大学オンラインジャッジというプログラムの勉強用のサイトがあります。
そちらの問題を全て自力で解いております。
リンク先に成績があり、円グラフのList of 266 solved Problemsというのが私が問題を解いた数です。

http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=sinapusu2002

この回答数どうでしょうか？
最低限のプログラム能力はあると思っています。
あくまで高校生レベルの最低限ですが、グラフ理論を理解する程度の素養はあると思うのですが？
これでは証明になりませんか？

引用返信 編集キー/

■58240 / inTopicNo.16)

　Re[15]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ norimaki1945 (1回)-(2011/03/29(Tue) 19:27:24)

ヒンと

線形ロゴウスキー法

引用返信 編集キー/

■58242 / inTopicNo.17)

　Re[16]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ 翔泳ミキオ (2回)-(2011/03/29(Tue) 20:16:47)

シープラで2次元の線を引くだけのプログラムなんですけどね。

カンニング的回答では証拠にはなりません。

ボクの簡単な問題はオリジナルですから、コノ世の中で答えは1つです。

カンニングはできません。

ちなみに中2レベルの問題なんですけど^^;

引用返信 編集キー/

■58267 / inTopicNo.18)

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

▲▼■

□投稿者/ 堀江伸一 (12回)-(2011/03/30(Wed) 12:15:16)

■No58242 (翔泳ミキオさん) に返信
カンニング、、、
カンニングしてたら、ワーロングアンサーやタイムリミッドエクスパッションはとってないです。
もっといい成績してますよ。

まあズルはしてます。
自信のない問題に挑戦する前や、テストする時間を取らずとりあえずテスト的に書き上げた自信のないコードはtesterという別の名前で挑戦しています。
http://rose.u-aizu.ac.jp/onlinejudge/UserInfo.jsp?id=tester
こちらです。

引用返信 編集キー/

■58270 / inTopicNo.19)

　Re[13]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲▼■

□投稿者/ shu (581回)-(2011/03/30(Wed) 12:45:02)

このレスの時点で

■No58236 (堀江伸一さん) に返信
> ■No58231 (鬼塚さん) に返信
>>言いたいことは、例えばアルゴリズムが明確で、それをコード化するにはどうすればいいかという質問であれば、
>>ここでも多くの回答を期待できるが、アルゴリズムについての質問であれば、（難しいものであればある程）
>>ここで回答を得ることは難しいのではないかということだ。
この内容について特に何も思わなかったですか？ここの掲示板でグラフ理論に詳しい人を求めても回答を得るのは
難しいという事ですよ。グラフ理論を勉強する為の掲示板ではないですから。サイト内の過去ログをグラフで
検索しても一般的なグラフの書き方のスレしか見つからないと思います。書き込んではいけないとは言いま
せんがこの部分についてレスが書かれていなかったので気づいてないのかと思ったしだいです。

>>知恵袋などで質問した方が多くの意見を得られるのでは？
>>
>>もっとも、これが学校の宿題・研究課題などについての質問ではないことを祈る。
>
> 知恵袋の場合見当外れの答えを自信満々で記載してくる方が多い感じで、あまり使えないのです。
> 後この問題については純粋な知的好奇心からの質問です。
こっちの内容は付加的な提案であって上記の方が重要かと思います。

引用返信 編集キー/

■58271 / inTopicNo.20)

　Re[14]: ｎ点のグラフの中からｍ点を選び、ｍ点を結ぶ最小全域木を選ぶと

▲　■

□投稿者/ 堀江伸一 (13回)-(2011/03/30(Wed) 13:04:18)

■No58270 (shu さん) に返信
> このレスの時点で
グラフ理論は、プログラムの問題や大会で良く出てくるのでプログラムの範疇だと考えたのですが？

＞線形ロゴウスキー法
線形ロゴウスキー法調べてみましたが、Googleで検索してみて何も出てきません。
ということは難しい専門書を参照する必要があるということですね？
うーん、大学行ったことがないので大学レベルの数学の専門書を読みこなすほどの能力はないんです、私。

できたら概論だけでもお教え願えたらと思います。
この掲示板はマルチポスト禁止でないようですので、こちらの掲示板でも質問の続きをすることにしました。
http://www004.upp.so-net.ne.jp/s_honma/index.htm

引用返信 編集キー/

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

- Child Tree -