このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合スレ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/
【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
<集大成>アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/
アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html
データ構造,アルゴリズム,デザインパターン総合スレ 3©2ch.net
レス数が950を超えています。1000を超えると書き込みができなくなります。
2016/06/19(日) 14:47:29.63ID:5KvSKdL/
897デフォルトの名無しさん
2018/08/30(木) 16:30:03.75ID:OpvYfh8N >>896
数学からやり直したほうがいい
数学からやり直したほうがいい
898デフォルトの名無しさん
2018/08/30(木) 16:38:34.35ID:AAPeDezt >>897
どういう意味?
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ?)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構
どういう意味?
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ?)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構
899デフォルトの名無しさん
2018/08/30(木) 16:59:47.21ID:rxoSSaq5 論理的思考力を上げるために将棋をしなさい。数学など不要です。
900デフォルトの名無しさん
2018/08/30(木) 18:00:22.07ID:RB/Vojpj うむ
901デフォルトの名無しさん
2018/08/30(木) 18:13:22.55ID:OpvYfh8N >>898
DPは数学的に求まるよ
DPは数学的に求まるよ
902デフォルトの名無しさん
2018/08/30(木) 18:43:47.20ID:nhWZJRvT >>898
数学科の数学と物理科の数学とコンピュータの数学は違う(笑)
数学科の数学と物理科の数学とコンピュータの数学は違う(笑)
903デフォルトの名無しさん
2018/08/30(木) 19:55:53.34ID:dq2VmAiX904デフォルトの名無しさん
2018/08/30(木) 19:59:32.89ID:rxoSSaq5 例えば、バブルソートには
数学の、えっと、幾何?の知識が必要だろ?
え?
数学の、えっと、幾何?の知識が必要だろ?
え?
905デフォルトの名無しさん
2018/08/30(木) 20:02:00.51ID:JJE0QqNc フローチャートでも書けよバカ。
906デフォルトの名無しさん
2018/08/30(木) 20:07:14.70ID:dq2VmAiX >>905
無論書いたが分からん
無論書いたが分からん
907デフォルトの名無しさん
2018/08/30(木) 20:55:16.95ID:LfSXnVaM >>903
やったことないだろ(笑)
やったことないだろ(笑)
908デフォルトの名無しさん
2018/08/30(木) 20:58:00.20ID:LfSXnVaM 単に頭が悪い見栄っ張り
909デフォルトの名無しさん
2018/08/30(木) 21:05:25.02ID:fZXCQKMc >>906
分からんと思っているだけでは進まない。
なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。
と言うことを、私は数学で学んだ。
分からんと思っているだけでは進まない。
なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。
と言うことを、私は数学で学んだ。
910デフォルトの名無しさん
2018/08/30(木) 21:18:12.57ID:51/MDOyO 数I?数II?
911デフォルトの名無しさん
2018/08/30(木) 21:43:49.44ID:HM7SCTN2912デフォルトの名無しさん
2018/08/31(金) 00:40:53.58ID:/Xr6ByPq 俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに
913デフォルトの名無しさん
2018/08/31(金) 00:57:19.27ID:1Yp+WIrl まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし
914デフォルトの名無しさん
2018/08/31(金) 01:02:18.59ID:avsEGe4h915デフォルトの名無しさん
2018/08/31(金) 01:09:41.75ID:6Alav1/S そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ
916デフォルトの名無しさん
2018/08/31(金) 07:21:05.29ID:wT3DulcX 数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね
はい言いました
論理的思考力が無いのはあなたですね
917デフォルトの名無しさん
2018/08/31(金) 07:23:04.73ID:KNbvu5CI どうしてこうなった
918デフォルトの名無しさん
2018/08/31(金) 09:04:32.63ID:csqJsH/K919デフォルトの名無しさん
2018/08/31(金) 09:05:36.36ID:csqJsH/K ちなみに、数列は高校数学である
920デフォルトの名無しさん
2018/08/31(金) 11:52:41.02ID:5OSgw2nY921デフォルトの名無しさん
2018/08/31(金) 12:44:50.11ID:DXKxWv2O922デフォルトの名無しさん
2018/08/31(金) 14:32:18.54ID:5OSgw2nY923デフォルトの名無しさん
2018/08/31(金) 14:39:40.99ID:DXKxWv2O 信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・
一度ライブラリ作って、他の人はそれ使うだけだろ・・・
924デフォルトの名無しさん
2018/08/31(金) 16:28:19.03ID:5OSgw2nY925デフォルトの名無しさん
2018/08/31(金) 18:49:37.43ID:DXKxWv2O926デフォルトの名無しさん
2018/08/31(金) 19:18:52.92ID:5OSgw2nY 別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします
表面的なものしか作りたくないなら勉強しないことをおすすめします
927デフォルトの名無しさん
2018/08/31(金) 19:24:24.23ID:DXKxWv2O928デフォルトの名無しさん
2018/08/31(金) 19:27:43.29ID:5OSgw2nY >>927
つまり君はそういう層にはなるのを拒む側ってだけだ
つまり君はそういう層にはなるのを拒む側ってだけだ
929デフォルトの名無しさん
2018/08/31(金) 20:05:55.05ID:OUCwI4mz >>928
その理屈で言えば、君がそういう層になりたいだけでは?
残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね
そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。
その理屈で言えば、君がそういう層になりたいだけでは?
残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね
そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。
930デフォルトの名無しさん
2018/09/01(土) 00:41:52.18ID:GjC7kJfb >>929
作りたいものがあるから勉強する、それだけ
作りたいものがあるから勉強する、それだけ
931デフォルトの名無しさん
2018/09/01(土) 09:56:42.06ID:pu0WuyWZ うむ
932デフォルトの名無しさん
2018/09/01(土) 10:48:54.59ID:iQmzKze8 自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。
が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。
付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。
全部を知っておかなければいけない、って思いたくなるのもわかる。
が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。
付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。
933デフォルトの名無しさん
2018/09/01(土) 12:24:44.93ID:rDlJp/s7 ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった
何か良い事を言いってみたい必死さは伝わった
934デフォルトの名無しさん
2018/09/01(土) 12:52:20.45ID:mPcVbgud え?言いたいことがわからんの?
935デフォルトの名無しさん
2018/09/01(土) 13:01:11.42ID:8oBLXasx そりゃあ馬鹿の言ってることは分からんだろ
936デフォルトの名無しさん
2018/09/01(土) 13:13:44.90ID:mPcVbgud 言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの?
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが?
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが?
937デフォルトの名無しさん
2018/09/01(土) 13:42:02.18ID:8oBLXasx 俺に言わせれば世界はお前を中心に回ってないってこと
938デフォルトの名無しさん
2018/09/01(土) 13:47:09.53ID:mPcVbgud >>937
お前を中心に回ってるといいたいのかな?
お前を中心に回ってるといいたいのかな?
939デフォルトの名無しさん
2018/09/01(土) 14:37:08.16ID:8oBLXasx940デフォルトの名無しさん
2018/09/01(土) 14:47:05.92ID:mPcVbgud >>939
俺のレスがどうした?
俺のレスがどうした?
941デフォルトの名無しさん
2018/09/04(火) 02:27:34.18ID:Tt3u8CpR アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ?
・網羅性が高い
・支持されている(売れている)
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる
・網羅性が高い
・支持されている(売れている)
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる
942デフォルトの名無しさん
2018/09/04(火) 07:04:17.98ID:OlESf3Ok 英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村 晴彦
http://amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村 晴彦
http://amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。
943デフォルトの名無しさん
2018/09/04(火) 07:32:26.75ID:/VBaeORw 機械学習の何をアルゴリズム辞典に入れるべきだというのか
Amazonレビューかよテメェは
Amazonレビューかよテメェは
944デフォルトの名無しさん
2018/09/04(火) 07:36:36.34ID:5tN3iveh >>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い
945デフォルトの名無しさん
2018/09/04(火) 08:37:54.35ID:HF+7qfHp より網羅的な対案示してからでないと批判にならないよ。
共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。
個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。
共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。
個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。
946デフォルトの名無しさん
2018/09/04(火) 10:34:21.16ID:gEGTZvcA >>943
+1
+1
947デフォルトの名無しさん
2018/09/04(火) 10:36:29.76ID:ROt4XEkp 名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない
そんなのいくらやっても新しいものは生み出されない
948デフォルトの名無しさん
2018/09/04(火) 14:25:14.21ID:JAXadswE >>947
先輩、かっけぇっす
先輩、かっけぇっす
949デフォルトの名無しさん
2018/09/11(火) 14:44:06.44ID:O54onciS 質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png
950デフォルトの名無しさん
2018/09/11(火) 16:27:37.38ID:zEn+kcA0 質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい?
前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。
この保証がないのなら十分長く波形をとってFFTしてピークを探す。
前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。
この保証がないのなら十分長く波形をとってFFTしてピークを探す。
951デフォルトの名無しさん
2018/09/11(火) 22:09:31.90ID:i7axZbyN ♀だったらセクロス教えてやる
952デフォルトの名無しさん
2018/09/11(火) 22:11:28.88ID:4O7I7zcY え!?童貞なのにセクロスを!?
953デフォルトの名無しさん
2018/09/12(水) 03:44:12.77ID:gw3HbkUV できらあ!
954デフォルトの名無しさん
2018/09/12(水) 07:05:35.15ID:Jy3sklaz それページ逆だぞ
955デフォルトの名無しさん
2018/11/05(月) 18:00:44.74ID:ajh0QscM 有向グラフの有向閉路を求める問題です。
深さ優先探索を実行したときに、 Backward Edge が存在する。
⇔
有向閉路をもつ
⇒は自明ですが、逆はどう証明するのでしょうか?
深さ優先探索を実行したときに、 Backward Edge が存在する。
⇔
有向閉路をもつ
⇒は自明ですが、逆はどう証明するのでしょうか?
956デフォルトの名無しさん
2018/12/03(月) 20:50:16.30ID:wBSUle4B 深さ優先、幅優先探索を理解するのにオススメの本ってありますか?(コードサンプル付きでできればC)
957デフォルトの名無しさん
2018/12/04(火) 09:57:38.19ID:euG8Im7Y958デフォルトの名無しさん
2018/12/04(火) 10:14:50.08ID:GTmuusXQ959デフォルトの名無しさん
2018/12/04(火) 10:27:11.51ID:GTmuusXQ960デフォルトの名無しさん
2018/12/04(火) 11:20:17.46ID:6CbA0WHr 馬鹿アスペの推奨w
961デフォルトの名無しさん
2018/12/04(火) 14:19:52.12ID:X/ZQLD1J 学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)
962デフォルトの名無しさん
2018/12/04(火) 14:28:35.23ID:GTmuusXQ >>956
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部 有隆
固定リンク: http://amzn.asia/d/g8qmfS6
↑この本にも、 BFS、DFS共に書いてあります。
解説は非常に雑ですが。
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部 有隆
固定リンク: http://amzn.asia/d/g8qmfS6
↑この本にも、 BFS、DFS共に書いてあります。
解説は非常に雑ですが。
963デフォルトの名無しさん
2018/12/04(火) 14:33:05.75ID:GTmuusXQ964デフォルトの名無しさん
2018/12/04(火) 14:34:21.14ID:GTmuusXQ965デフォルトの名無しさん
2018/12/04(火) 14:39:02.72ID:eKuwOju4 前置記法(ポーランド記法) + 1 2
後置記法(逆ポーランド記法) 1 2 +
中置記法 1 + 2
確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している
後置記法(逆ポーランド記法) 1 2 +
中置記法 1 + 2
確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している
966デフォルトの名無しさん
2018/12/05(水) 13:24:47.73ID:2sSegHBZ shaderって何回書き換えてもメモリ壊れない?
967デフォルトの名無しさん
2018/12/05(水) 21:47:02.62ID:xYhP2Ga4 テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど
ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう
pdf買えはうざいけど
ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう
968デフォルトの名無しさん
2019/06/19(水) 04:49:26.98ID:tVNS+22r 【出資】松本卓朗 人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/
969デフォルトの名無しさん
2020/01/03(金) 12:48:16.96ID:LiTO8m+L O(n)で中央値を求めるアルゴリズムを思いついた
970デフォルトの名無しさん
2020/01/04(土) 01:21:11.30ID:buSsFrEd クイックセレクトのこと?
971デフォルトの名無しさん
2020/01/13(月) 02:33:48.51ID:D6MgPK0q こんにちは、初質問させていただきます、グラフアルゴリズム初心者です
・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。
考え方と共に、コーディング例をご教授いただけると幸いです。
浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。
お手数おかけしますが、ご助力いただけると幸いです。
・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。
考え方と共に、コーディング例をご教授いただけると幸いです。
浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。
お手数おかけしますが、ご助力いただけると幸いです。
972デフォルトの名無しさん
2020/01/13(月) 04:31:10.60ID:6QaMEdT1 適当に言うけど、
すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある?
すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある?
973デフォルトの名無しさん
2020/01/13(月) 12:21:39.99ID:jqPh5nAm >>971
グラフのサイズが書いてないと答えられないな
グラフのサイズが書いてないと答えられないな
974デフォルトの名無しさん
2020/01/13(月) 13:32:08.60ID:D6MgPK0q975デフォルトの名無しさん
2020/01/13(月) 13:32:16.76ID:D6MgPK0q976デフォルトの名無しさん
2020/01/13(月) 17:13:44.37ID:jqPh5nAm >>975
頂点数をn,辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる(最初にuに戻ってきたときの経路が最小)
あとはすべての頂点に対してこれをして,その中から一番短いものを選べばいいので,全体でO(n(n+m))で求められる
頂点数をn,辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる(最初にuに戻ってきたときの経路が最小)
あとはすべての頂点に対してこれをして,その中から一番短いものを選べばいいので,全体でO(n(n+m))で求められる
977デフォルトの名無しさん
2020/01/13(月) 22:42:08.62ID:D6MgPK0q978デフォルトの名無しさん
2020/01/13(月) 23:30:01.64ID:jqPh5nAm >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します.このグラフ上でuからvの最短距離dを求めます
すると,d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので,すべての辺に対して上の操作を実行します
その中から一番短いものを選べば,それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します.このグラフ上でuからvの最短距離dを求めます
すると,d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので,すべての辺に対して上の操作を実行します
その中から一番短いものを選べば,それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
979デフォルトの名無しさん
2020/01/15(水) 13:45:14.74ID:oHYk5H5Q >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・?
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・?
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
980デフォルトの名無しさん
2020/01/15(水) 16:39:42.37ID:Ex9G0OLU981デフォルトの名無しさん
2020/01/15(水) 21:49:25.61ID:oHYk5H5Q982デフォルトの名無しさん
2020/01/15(水) 23:25:41.19ID:Ex9G0OLU >>981
無向グラフだと面倒くさくて,uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので,辺は1度しか使えないようにすればいいと思う
無向グラフだと面倒くさくて,uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので,辺は1度しか使えないようにすればいいと思う
983デフォルトの名無しさん
2020/01/15(水) 23:28:15.13ID:Ex9G0OLU https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな 重みなしだけど
これとかわりとそのままだな 重みなしだけど
984デフォルトの名無しさん
2020/01/15(水) 23:56:14.28ID:Ex9G0OLU985デフォルトの名無しさん
2020/01/18(土) 22:58:37.26ID:iLU56BHo986デフォルトの名無しさん
2020/01/19(日) 12:55:00.98ID:VFlG/sWR CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
987デフォルトの名無しさん
2020/01/20(月) 15:11:46.01ID:+ZQhvd/Y 巨大なsparce行列(ゼロ要素が多い行列)で行列演算やるときデータ構造考えるよね
988デフォルトの名無しさん
2020/01/20(月) 17:27:30.27ID:/b+J8VIk >>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は,グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は,グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
989デフォルトの名無しさん
2020/01/20(月) 17:28:22.60ID:/b+J8VIk 途中で送信してしまった
このときの経路をvetorにいれておけばいい
このときの経路をvetorにいれておけばいい
990デフォルトの名無しさん
2020/01/25(土) 23:49:17.89ID:Q85YRMjK991デフォルトの名無しさん
2020/01/26(日) 01:32:16.02ID:63DOpTVc 言語の基本的な部分はさすがによそでやろうや・・・
992デフォルトの名無しさん
2020/01/26(日) 13:25:18.52ID:eN1PAkvI993デフォルトの名無しさん
2020/01/26(日) 13:32:46.65ID:eN1PAkvI >>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
994デフォルトの名無しさん
2020/01/26(日) 13:47:50.10ID:eN1PAkvI アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか?
995デフォルトの名無しさん
2020/01/26(日) 16:03:48.66ID:gJO14xRt996デフォルトの名無しさん
2020/01/26(日) 16:28:11.19ID:eN1PAkvIレス数が950を超えています。1000を超えると書き込みができなくなります。
ニュース
- 【音楽】Perfume・あ~ちゃんの結婚相手「一般男性」は吉田カバンの社長・吉田幸裕氏(41) 高身長で山本耕史似 [Ailuropoda melanoleuca★]
- 日本行き空路49万件キャンセル 中国自粛呼びかけ 日本行きチケット予約の約32%に相当 ★4 [ぐれ★]
- 【サッカー】U-17日本代表、激闘PK戦制す 北朝鮮撃破で6大会ぶり8強入り U17W杯 [久太郎★]
- 【インバウンド】中国人観光客の日本での消費額は年間約2兆円超…中国政府は公務員の出張取り消し [1ゲットロボ★]
- 【サッカー】日本代表、ボリビアに3発快勝 森保監督通算100試合目を飾る…鎌田、町野、中村がゴール [久太郎★]
- XやChatGPTで広範囲の通信障害 投稿や閲覧できず [蚤の市★]
- 毒親「働かないでいつもゴロゴロして!」俺「…」毒親「あっ近隣に熊が出たって!」俺「ふぅ」毒親「どこ行くんだ」
- アンケート調査で「高市発言は問題なし」 93.5%wwwwwwwwwwwwwwwwwwwwwwwww [279254606]
- 生活保護の受給額ってなんでこんなに安いの?
- お前らは“スカイマイルタワー”建設計画を知っているか?
- これ誰か分かるか?
- 支払い詰まってインターネット止まった
