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

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

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

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

(過去ログ 98 を表示中)

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

■58282 / inTopicNo.21)

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

▼■

□投稿者/ 鬼塚 (3回)-(2011/03/30(Wed) 16:04:56)

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

どうも、まるで君が家電量販店の店員に、テレビの液晶の光学特性について質問しているような感じである。

プログラムの範疇という言葉が出てきているが、君の言うプログラムの定義について教えてほしい。
一般的にプログラムとは、問題を解決するためのアルゴリズムではなく、
アルゴリズムをコンピューターに指示する命令の内容ではないのか？
私はそのことを指摘しているのだが、どうやら君は理解していないようである。

君は、純粋な知的好奇心からこの質問をしたとのことであるが、それを学ぶことよりも、
もっと情報に対して正確に理解する能力を学ぶべきではないか？
そもそも、「線形ロゴウスキー法」などというものはもしかして出鱈目なのではないか？
そのようなことだから、誤った情報に振り回されるのである。

ついでに言っておくが、君は情報分析力に加え、コミュニケーション力も
つけておくべきである。

引用返信 編集キー/

■58292 / inTopicNo.22)

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

▲▼■

□投稿者/ ＰＡＴＩＯ (105回)-(2011/03/30(Wed) 17:03:51)

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

プログラミングの関連している話なのでこの掲示板で質問する事自体はおかしくないと思いますけれど、
答えを得られるような掲示板なのかと言う話になると別なのではないかと言うことだと思います。
プログラミングについて話ができる人が必ずしもグラフ理論の専門家では無いという話です。
一般的な業務用のプログラムにグラフ理論の専門知識が必要かと言うとたぶん必要無いというのが
一般的な答えだと思います。
このまま、この掲示板でやり取りを続けても実りが少ないと思いますよいう指摘ですね。
実りが少ないのを覚悟の上でこの掲示板で話を続けると言うのも一つの判断なので否定はしません。

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

マルチで質問するのであれば、対応の方もきちんとマルチにやってください。
掲示板間の情報の調整（あちらからこちら、こちらからあちらへの情報の伝達）等結構大変です。
それがきちんとこなせるなら行為そのものを否定はしません。
マルチポストが批判されるのはそういう部分をきちんとできない人が多いからです。

引用返信 編集キー/

■58296 / inTopicNo.23)

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

▲▼■

□投稿者/ 堀江伸一 (14回)-(2011/03/30(Wed) 18:06:08)

＞マルチポストについて
両方にリンクを張りつけますし、解決したら両方に情報を掲載しますよ。
これで十分ですよね？
これ以上の何が必要なのでしょうか？

＞回答できない
回答できないと言われても私としては困るくらいしか対応できません。
グラフ理論はプログラムの範疇のはずなのでやはり期待はします。
それなら回答が付きそうな掲示板をお教えてください。

>グラフ理論について
一応、知識を持っている方が一人くらいいることを期待してもばちは当たらないと思います？
大勢の中に一人でもいればいというのが掲示板というものだと理解してますが。

＞出鱈目な答えを真に受けたことについて
実務で出鱈目な答えを見抜けず使ったなら私に非がありますが、今回の質問は知的好奇心からです。
このような質問に対しては、出鱈目な答えを出した人を責めるべきではないでしょうか？
私の場合、手法が本当に存在するのかきちんと調べて確証を得るまではコードに使いません。
まだ質問の段階でしたので、責められる理由がわかりませんが？

引用返信 編集キー/

■58298 / inTopicNo.24)

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

▲▼■

□投稿者/ 堀江伸一 (15回)-(2011/03/30(Wed) 18:17:57)

■No58267 (堀江伸一さん) に返信
C#のピクチャボックスで5分で実装。
何か問題があるでしょうか？

private void pictureBox1_Click_1(object sender, EventArgs e)
{
Graphics g = pictureBox1.CreateGraphics();
//Penオブジェクトの作成(幅2の黒色)
Pen blackPen = new Pen(Color.Black, 1);
pictureBox1.Height = 100;
pictureBox1.Width = 100;
int w = pictureBox1.Width;
int h = pictureBox1.Height;
double cx = w / 2;
double cy = h / 2;
int x1 = (int)(cx + cx *Math.Cos(35 / 180.0 * Math.PI));
int y1 = (int)(cy - cy *Math.Sin(35 / 180.0 * Math.PI));
int x2 = (int)(cx + cx *Math.Cos(78 / 180.0 * Math.PI));
int y2 = (int)(cy - cy *Math.Sin(78 / 180.0 * Math.PI));
g.DrawLine(blackPen, x1, y1, x2, y2);
g.DrawEllipse(blackPen, 0, 0, w, h);
}

引用返信 編集キー/

■58299 / inTopicNo.25)

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

▲▼■

□投稿者/ 堀江伸一 (16回)-(2011/03/30(Wed) 18:20:42)

＞プログラムの範疇という言葉が出てきているが、君の言うプログラムの定義について教えてほしい。
プログラムの定義については良くわかりませんが、
私の要求しているレベルはプログラマがプログラムやアルゴリズムのテクニックを競う大会のうち、高校生部門レベルです。
つまり初等的。
そんなに高度なことは質問してないはずです。

プログラムとは何かと問う質問事態、衒学的で意味がわかりませんが？
こんなレスしてて恥ずかしくないですか？

引用返信 編集キー/

■58301 / inTopicNo.26)

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

▲▼■

□投稿者/ 鬼塚 (4回)-(2011/03/30(Wed) 18:34:50)

>＞プログラムの範疇という言葉が出てきているが、君の言うプログラムの定義について教えてほしい。
>プログラムの定義については良くわかりませんが、

プログラムの定義も分からないくせに、「プログラムの範疇」という言葉を使うこと自体おかしい。
これを知ったかぶりというのだ。

>こんなレスしてて恥ずかしくないですか？

なるほど、君には客観的にものを見る能力が欠如しているようだ。
シェームレスとはそういうものか。
そもそも「知ったかぶり」なんて恥ずかしいものの最たるものだが。

どうやらコミュニケーション力の指摘についても理解できないようだ。

引用返信 編集キー/

■58302 / inTopicNo.27)

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

▲▼■

□投稿者/ 翔泳ミキオ (4回)-(2011/03/30(Wed) 18:50:11)

とりあえず、コードを提示しましょうよ。

シープラあるいは、ベーシックのコードがかけるかどうかの話ですよ。

ピクチャーボックスのイベントハンドラ内にコードを書いて、それをコピーして、ココに貼り付けるだけです。

書けるかどうか、2進数の回答が求められています。

引用返信 編集キー/

■58303 / inTopicNo.28)

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

▲▼■

□投稿者/ 翔泳ミキオ (5回)-(2011/03/30(Wed) 18:55:23)

■No58302 (翔泳ミキオさん) に返信
>おお、一応書いてあるね。

チョットC＃とやらをインストールして、検証してみます。

ありゃ、初めてのC#だ。（笑）

引用返信 編集キー/

■58304 / inTopicNo.29)

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

▲▼■

□投稿者/ みきぬ (958回)-(2011/03/30(Wed) 18:57:29)

このスレで自分が質問者にできるアドバイスは、変なコメントはスルーしたほうがよいということだけです。

引用返信 編集キー/

■58305 / inTopicNo.30)

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

▲▼■

□投稿者/ 堀江伸一 (17回)-(2011/03/30(Wed) 18:59:00)

■No58303 (翔泳ミキオさん) に返信
> ■No58302 (翔泳ミキオさん) に返信
> >おお、一応書いてあるね。
あの一つ聞きますが人をカンニング呼ばわりして楽しいですか？
この掲示板では難しすぎて答えられないんですということを、何か偉そうに書いて楽しいですが？
プログラムの定義がアルゴリズムの質問にどう影響するのか理解に苦しみます。

このスレ、答えが得られるまで粘着しましょうか？
スレを冷静に見変えて恥ずかしくないですか？
この板では人を小馬鹿にする回答が得られますよというのを他の板に張り付けてみましょうか？

引用返信 編集キー/

■58307 / inTopicNo.31)

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

▲▼■

□投稿者/ 翔泳ミキオ (6回)-(2011/03/30(Wed) 20:01:51)

■No58305 (堀江伸一さん) に返信
>ども＾＾；

一応、ギザギザな線が正確にでてましたよ。

別にバカにはしていません。最近へんな人が多いんで。

フロチャートを書いて、じっくり研究してください。

引用返信 編集キー/

■58308 / inTopicNo.32)

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

▲▼■

□投稿者/ επιστημη (2612回)-(2011/03/30(Wed) 20:02:19)

えーと...この問題は総延長距離が最短になるよういくつかの点をもれなく繋ぐ電線を引け、てことですか。
しかも途中に分岐点を置いてもいい、と。

どうなんだろ、これがNP問題だとすると(今のところ)どうあがこうがそんなに速く求める手段はないんだけど。
NPであるか否かは自明なんだろうか...

# 答にもヒントにもなってないですね、スンマセン

引用返信 編集キー/

■58309 / inTopicNo.33)

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

▲▼■

□投稿者/ 翔泳ミキオ (7回)-(2011/03/30(Wed) 20:07:21)

■No58307 (翔泳ミキオさん) に返信
> 本物の職人さんであれば、電線はカナリ重要ですね。
電線1メートルのお値段は非常に高いですから。（10円も集まると巨額になる）

引用返信 編集キー/

■58320 / inTopicNo.34)

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

▲▼■

□投稿者/ 堀江伸一 (18回)-(2011/03/31(Thu) 00:42:09)

計算量は悪いですがワーシャルフロイド法とプリム法を組み合わせる方法を考えつきましgた。
まずワーシャルフロイド法で、各地点iからjへの最短距離を求め、これをmap[i][j]とします。

地点と道路のグラフをｇとします。
一端ｇの辺を全て削除します。
次に、map[i][j]を点iからｊへまっすぐつながった線として解釈しなおし辺を引き直します。
すると全ての点が、他の点とつながったグラフが得られます。
このグラフをnewGとします。

電線の分岐点の集合をB={B1,B2,,,,Bm-1}
目的地の集合を M={M1,M2,,,,Mm}
発電所を　　　Hとします。
とします。
注意点としてBi=BjやBi=Mj,Bi=Hという場合もあります。
Bi=BjならBjを削除し、Bi＝Miや＝HならBiを削除します。

あるBの組み合わせを考えた時、newGからB、M、Hの点とそれらをつなげる辺を無視します。
後はB,M、Hをつなげる線をプリム法で求めます。
これでBがある組み合わせになった時の電線の最小距離がで木構造が作られます。
Biが木の葉になった場合があるので、葉になるBiがある限りBiを削除します。
これがBがあるセットになった時の電線の最小距離がでます。

後はこれを全てのBの組み合わせで試せば最小距離が出ます。

しかしこれは私が自分で思いついた素朴な方法ですのでもっとましな方法があると思います。

引用返信 編集キー/

■58321 / inTopicNo.35)

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

▲▼■

□投稿者/ 堀江伸一 (19回)-(2011/03/31(Thu) 00:45:40)

さっき気付いたのですアg
http://www004.upp.so-net.ne.jp/s_honma/index.htm
でお返事ありました。

もしかしたら私の思いついた方法と同じかも。
ちょっと印刷して良く読んでみます。

引用返信 編集キー/

■58322 / inTopicNo.36)

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

▲▼■

□投稿者/ 堀江伸一 (20回)-(2011/03/31(Thu) 00:56:03)

記述ミスがありました。
書き直します。

計算量は悪いですがワーシャルフロイド法とプリム法を組み合わせる方法を考えつきましgた。
まずワーシャルフロイド法で、各地点iからjへの最短距離を求め、これをmap[i][j]とします。

地点と道路のグラフをｇとします。
一端ｇの辺を全て削除します。
次に、map[i][j]を点iからｊへつながった辺と解釈しなおし辺を引き直します。
すると全ての点が、他の点とつながったグラフが得られます。
このグラフをnewGとします。

電線の分岐点の集合をB={B1,B2,,,,Bm-1}
目的地の集合を M={M1,M2,,,,Mm}
発電所を　　　Hとします。
とします。
注意点としてBi=BjやBi=Mj,Bi=Hという場合もあります。
Bi=BjならBjを削除し、Bi＝Miや＝HならBiを削除します。

あるBの組み合わせを考えたます。
まずnewGからB、M、Hの点とそれらをつなげる辺以外を無視します。
後はB,M、Hをつなげる最短の最小全域木をプリム法で求めます。
これでBがある組み合わせになった時の電線の最小距離を表す木構造が作られます。
このままでは答えになりません。
Biが木の葉になった場合があるので、葉になるBiがある限りBiを削除します。
これがBがあるセットになった時の電線の最小距離がでます。

後はこれを全てのBの組み合わせで試せば最小距離が出ます。
しかしこれは私が自分で思いついた素朴な方法ですのでもっとましな方法があると思います。

引用返信 編集キー/

■58325 / inTopicNo.37)

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

▲▼■

□投稿者/ shu (587回)-(2011/03/31(Thu) 07:43:29)

■No58322 (堀江伸一さん) に返信
> 記述ミスがありました。
> 書き直します。
>
> 計算量は悪いですがワーシャルフロイド法とプリム法を組み合わせる方法を考えつきましgた。
> まずワーシャルフロイド法で、各地点iからjへの最短距離を求め、これをmap[i][j]とします。
>
>
> 地点と道路のグラフをｇとします。
> 一端ｇの辺を全て削除します。
> 次に、map[i][j]を点iからｊへつながった辺と解釈しなおし辺を引き直します。
> すると全ての点が、他の点とつながったグラフが得られます。
> このグラフをnewGとします。
>
> 電線の分岐点の集合をB={B1,B2,,,,Bm-1}
> 目的地の集合を M={M1,M2,,,,Mm}
> 発電所を　　　Hとします。
> とします。
> 注意点としてBi=BjやBi=Mj,Bi=Hという場合もあります。
> Bi=BjならBjを削除し、Bi＝Miや＝HならBiを削除します。
>
> あるBの組み合わせを考えたます。
> まずnewGからB、M、Hの点とそれらをつなげる辺以外を無視します。
> 後はB,M、Hをつなげる最短の最小全域木をプリム法で求めます。
> これでBがある組み合わせになった時の電線の最小距離を表す木構造が作られます。
> このままでは答えになりません。
> Biが木の葉になった場合があるので、葉になるBiがある限りBiを削除します。
> これがBがあるセットになった時の電線の最小距離がでます。
>
> 後はこれを全てのBの組み合わせで試せば最小距離が出ます。
> しかしこれは私が自分で思いついた素朴な方法ですのでもっとましな方法があると思います。

私が書いた方法を具体化しただけですね。プリム法は駄目なんじゃないの？

引用返信 編集キー/

■58365 / inTopicNo.38)

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

▲▼■

□投稿者/ 堀江伸一 (21回)-(2011/03/31(Thu) 14:28:09)

> 私が書いた方法を具体化しただけですね。プリム法は駄目なんじゃないの？
?
>賢くない方法ですが、抽出点i1～imについてそれぞれの２点の最短経路を求めるとｍ点のグラフと同等になるので求められるんじゃないかな？
これのことでしょうか？
確かにヒントになってますね。
ありがとうございます、気付いてませんでした。
後、プリム法がダメな理由をお願いします。

リンク先掲示板で下記のような回答を頂きました。
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に電線の分岐点がある場合の視点が抜け落ちている？
ような気もします。
私が間違ってるのか上記記述が間違っているのかどなたかご指摘お願いします。

引用返信 編集キー/

■58366 / inTopicNo.39)

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

▲▼■

□投稿者/ shu (593回)-(2011/03/31(Thu) 14:56:21)

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

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

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

より。

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

引用返信 編集キー/

■58367 / inTopicNo.40)

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

▲　■

□投稿者/ ﾂＰﾂＡﾂＴﾂＩﾂＯ (2回)-(2011/03/31(Thu) 15:52:37)

2011/03/31(Thu) 15:54:01 編集(投稿者)

ちょっと見ない間にスレッドが伸びている。
まあ、議論とは直接関係無い部分でも伸びていますが。

■No58296 (堀江伸一さん) に返信
> ＞マルチポストについて
> 両方にリンクを張りつけますし、解決したら両方に情報を掲載しますよ。
> これで十分ですよね？
> これ以上の何が必要なのでしょうか？

いえ、きちんと対応していただけるなら特に言う事は有りません。
よく片方の議論で答えが出そうになるとそれ以外の掲示板は
すっかり忘れてしまう方が多いので老婆心ながら書かせていただきました。

> ＞回答できない
> 回答できないと言われても私としては困るくらいしか対応できません。
> グラフ理論はプログラムの範疇のはずなのでやはり期待はします。
> それなら回答が付きそうな掲示板をお教えてください。

数学的な議論をメインでやっているような掲示板があれば、
そっちの方が確率が高いかなと思った程度ですのでどこか教えてくれと
言われても難しいです。ただ、ご本人が当たらぬも八卦くらいのつもりで
質問されているのであれば、問題はないです。
ここに質問するのが間違いと言う意味で書いたわけでは無いので。

> >グラフ理論について
> 一応、知識を持っている方が一人くらいいることを期待してもばちは当たらないと思います？
> 大勢の中に一人でもいればいというのが掲示板というものだと理解してますが。

こちらも上記に同じです。
ここよりも確率の高い掲示板があるかもくらいの話です。
質問そのものを否定しているわけではない事はご理解ください。

実りが有りそうな議論も出てきていますから、
このままこの掲示板で続けても大丈夫かもしれませんね。
結局は読んでいる人の興味が向くかと言う話だと思いますし。

#どうもFirefox4にしてから名前がおかしくなるなぁ。

引用返信 編集キー/

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

- Child Tree -