- 1 名前：デフォルトの名無しさん mailto:sageteoff [2016/06/19(日) 14:47:29.63 ID:5KvSKdL/.net]
- このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
echo.2ch.net/test/read.cgi/tech/1362301811/
【関連スレ】
3Dアルゴリズム全般
toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
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
- 897 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 11:20:01.67 ID:mZzpchFU.net]
- >>879
https://www.microsoft.com/net/learn/get-started-with-dotnet-tutorial
- 898 名前： mailto:sage [2018/08/11(土) 11:23:26.77 ID:vW2Ha+vq.net]
- >>880
固定資産税なら5月に収めました
- 899 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 13:12:12.75 ID:eIyvbe4d.net]
- >>882
固定資産もってるんだスゲー（笑）
- 900 名前：デフォルトの名無しさん [2018/08/16(木) 01:50:12.60 ID:c6C4Pdqe.net]
- 最も重要ななのはアルゴリズムとデータ構造
次にI/O
つぎに無名関数やハンドラ、イベント駆動
つぎに並列、非同期処理
その次は画像処理とか3Dとか
ディジタル信号処理またいな各ドメインの専門
技術。
オブジェクトやクラスなんてこれらを達成する
上での手段でしかない。
それ以上のオブジェクト指向の設計思想は
もはや宗教。
唯一絶対に正しいわけでもないし
概念を余計に複雑にするだけ。
SQLやHTML XMLやJavaScript シェルスクリプト
URLなんかが絡んでくるとグダグダに崩壊
するものばかり。
そして現代のアプリケーションはこれら無しで
作るのは無理だからオブジェクト指向の高度な
技法はほどんど不要。
- 901 名前：デフォルトの名無しさん [2018/08/16(木) 10:35:20.66 ID:wiNukf+g.net]
- NoSQLω
- 902 名前：デフォルトの名無しさん mailto:sage [2018/08/16(木) 14:12:13.61 ID:sOMWRYDA.net]
- NoSQL db って、Redis以外はわりと滅びた感じ。
RDBでもスキーマレスなデータ
- 903 名前：扱えるようになったし、
トランザクションあった方が便利なことやっぱり多いし、
SQLってなんだかんだ言って表現力高いし。 [] - [ここ壊れてます]
- 904 名前：デフォルトの名無しさん [2018/08/16(木) 21:39:02.86 ID:xTRm/dST.net]
- pythonスレにも書いたのですが、pandasのMultiIndexにしたデータのままで、データを追加したり、値を更新したり、csvに入出力する方法をご存知の方はいませんか？
- 905 名前：デフォルトの名無しさん mailto:sage [2018/08/17(金) 05:33:12.57 ID:kMdEBKXA.net]
- マルチ
- 906 名前：デフォルトの名無しさん mailto:sage [2018/08/18(土) 16:47:45.36 ID:Misswrnn.net]
- マルチインデックスだけに
- 907 名前：デフォルトの名無しさん mailto:sage [2018/08/22(水) 13:56:25.55 ID:Opme7aq9.net]
- >>886
その辺はクラウドに吸収されたよ
- 908 名前：デフォルトの名無しさん mailto:sage [2018/08/22(水) 14:04:12.93 ID:85QcXChJ.net]
- クラウドだけに雲散霧消
- 909 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 08:51:55.17 ID:rDVjwTPV.net]
- クラウドってなんだっけ？
- 910 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 11:43:20.70 ID:oFGqb4Dq.net]
- 興味ないね
- 911 名前：デフォルトの名無しさん mailto:sage [2018/08/26(日) 12:02:43.50 ID:Ecv/l33V.net]
- 雲の中にトレーラーがいっぱいあること
- 912 名前：デフォルトの名無しさん mailto:sage [2018/08/29(水) 11:59:51.59 ID:t35BnR1i.net]
- >>893
チリチリしてろ
- 913 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 11:36:30.01 ID:jf9m7XuW.net]
- AOJ の「DPL_1_I: Knapsack Problem with Limitations II」が分からん。
個数制限付きナップサック問題の
・ある品物の重さと個数制限
・ナップサック容量
が極めて大きいバージョン。
例えば解法
judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=2856557#1
を見ると、品物の価値の総和が i であるときの最大容量を記録した動的計画法テーブルを作った後に貪欲法で答えを出してるんだが
・なぜこの方法で上手くいくのか
・前半の動的計画法で、品物の個数を min(m[i], MAX_V) としている (できる) 理由が分からない。
誰か知恵を貸してください。
僕としてはこの解法が理解できれば満足です。
- 914 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:30:03.75 ID:OpvYfh8N.net]
- >>896
数学からやり直したほうがいい
- 915 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:38:34.35 ID:AAPeDezt.net]
- >>897
どういう意味？
「このアルゴリズムを理解するのに必要な数学の分野」というものがあるならそれを参照するが、そんなものはない (挙げられないでしょ？)
俺個人の専門は物理で、「数学の勉強」というものも一応してきたが、このごく具体的な問の一解法を理解することと「数学の勉強」は関係がない
単純に論理的思考力を上げよ、と言っているなら会話になっていないのでこれ以上は結構
- 916 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 16:59:47.21 ID:rxoSSaq5.net]
- 論理的思考力を上げるために将棋をしなさい。数学など不要です。
- 917 名前：デフォルトの名無しさん [2018/08/30(木) 18:00:22.07 ID:RB/Vojpj.net]
- うむ
- 918 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 18:13:22.55 ID:OpvYfh8N.net]
- >>898
DPは数学的に求まるよ
- 919 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 18:43:47.20 ID:nhWZJRvT.net]
- >>898
数学科の数学と物理科の数学とコンピュータの数学は違う（笑）
- 920 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 19:55:53.34 ID:dq2VmAiX.net]
- >>901
最適性の証明のことを言ってるの？
いずれにせよこの問題に限った話じゃないよね？
別に動的計画法が上手くいく理由が分からないと言っているのではなく、>>896の解法が分からないのだが。
>>902
違わない
算術、代数、幾何、解析だ全て
- 921 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 19:59:32.89 ID:rxoSSaq5.net]
- 例えば、バブルソートには
数学の、えっと、幾何？の知識が必要だろ？
え？
- 922 名前：デフォルトの名無しさん [2018/08/30(木) 20:02:00.51 ID:JJE0QqNc.net]
- フローチャートでも書けよバカ。
- 923 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:07:14.70 ID:dq2VmAiX.net]
- >>905
無論書いたが分からん
- 924 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:55:16.95 ID:LfSXnVaM.net]
- >>903
やったことないだろ（笑）
- 925 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 20:58:00.20 ID:LfSXnVaM.net]
- 単に頭が悪い見栄っ張り
- 926 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:05:25.02 ID:fZXCQKMc.net]
- >>906
分からんと思っているだけでは進まない。
なにを目的にして、どのようなフローチャートを描いて、
その結果なにが理解できていて、なにがまだ理解できていないのか、
可能な限り事細かに洗い出して、自分の理解の最前線を特定してみるといい。
と言うことを、私は数学で学んだ。
- 927 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:18:12.57 ID:51/MDOyO.net]
- 数I？数II？
- 928 名前：デフォルトの名無しさん mailto:sage [2018/08/30(木) 21:43:49.44 ID:HM7SCTN2.net]
- >>909
だからそれは>>896の時点で書いてるんだが
関係ないことしか言えないならレス不要です
>>907
何を？
- 929 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 00:40:53.58 ID:/Xr6ByPq.net]
- 俺の周りで物理やってる人はとんでもなく数学ができる人ばかりなのに
- 930 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 00:57:19.27 ID:1Yp+WIrl.net]
- まあゲームじゃない限り物理なんて使わないよね
本格的な物理系シミュレーションとかだと
専門家が担当するだろうし
- 931 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 01:02:18.59 ID:avsEGe4h.net]
- この程度の問題で数学数学言ってるアホ多過ぎて呆れる
多分>>910みたいな感じで高校の算数基準で話してるんだろうな
- 932 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 01:09:41.75 ID:6Alav1/S.net]
- そんなに言うのなら、具体的に数学のどの分野なのか
それが具体的に何と同じなのか言えって。
どうせ論理的思考力がーみたいな精神論しか言えないんだろ
- 933 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 07:21:05.29 ID:wT3DulcX.net]
- 数列、非線形解析学
はい言いました
論理的思考力が無いのはあなたですね
- 934 名前：デフォルトの名無しさん [2018/08/31(金) 07:23:04.73 ID:KNbvu5CI.net]
- どうしてこうなった
- 935 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 09:04:32.63 ID:csqJsH/K.net]
- >>916
では、数列、非線形解析学を利用した
アルゴリズムを答えてください
- 936 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 09:05:36.36 ID:csqJsH/K.net]
- ちなみに、数列は高校数学である
- 937 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 11:52:41.02 ID:5OSgw2nY.net]
- >>918
>>896
- 938 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 12:44:50.11 ID:DXKxWv2O.net]
- >>920
数学の問題をコンピュータで解決するってのはわかる、
だが数学・物理特有の問題以外をコンピュータで解決するのに
数学はいらねーだろって話
- 939 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 14:32:18.54 ID:5OSgw2nY.net]
- >>921
微分積分も理解せずにコンピュータに信号処理をやらせるの？
そういうレベルの質問
- 940 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 14:39:40.99 ID:DXKxWv2O.net]
- 信号処理なんて、誰がやっても同じなんだから
一度ライブラリ作って、他の人はそれ使うだけだろ・・・
- 941 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 16:28:19.03 ID:5OSgw2nY.net]
- >>923
それじゃあ初音ミクは生まれないね
こういうやつが技術を停滞させる
- 942 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 18:49:37.43 ID:DXKxWv2O.net]
- >>924
だからそういうのは専門家に任せたほうが良くね？
音声合成をやる人は、そういう専門家に任せて
他の人は便利なインターフェースを作るとかさ、
なんでも1人でやるもんじゃないよ？
- 943 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:18:52.92 ID:5OSgw2nY.net]
- 別にそういう原理を知りたくないんなら勉強しなくて良いんじゃない
表面的なものしか作りたくないなら勉強しないことをおすすめします
- 944 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:24:24.23 ID:DXKxWv2O.net]
- >>926
だから作る層が違うって言ってんの
水道局で働いてる人全員が
工事技師じゃないんだよ
- 945 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 19:27:43.29 ID:5OSgw2nY.net]
- >>927
つまり君はそういう層にはなるのを拒む側ってだけだ
- 946 名前：デフォルトの名無しさん mailto:sage [2018/08/31(金) 20:05:55.05 ID:OUCwI4mz.net]
- >>928
その理屈で言えば、君がそういう層になりたいだけでは？
残念だけど、自分がやりたいことと、他人がやってもらいたいこと
っていうのは同じじゃないんだよね
そして給料っていうのは、他人がやって欲しいことをやった対価として
もらえるものなので、いくら自分がすごいことができるって言ったからって
給料は高くならないんだよね。
- 947 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 00:41:52.18 ID:GjC7kJfb.net]
- >>929
作りたいものがあるから勉強する、それだけ
- 948 名前：デフォルトの名無しさん [2018/09/01(土) 09:56:42.06 ID:pu0WuyWZ.net]
- うむ
- 949 名前：デフォルトの名無しさん [2018/09/01(土) 10:48:54.59 ID:iQmzKze8.net]
- 自分一人で作るような小さいアプリとかなら、
全部を知っておかなければいけない、って思いたくなるのもわかる。
が、通常は数学の専門家でも無い人間を数学で信用する事は無いし、
プログラムの専門家でも無い人間をプログラムで信用する事は無い。
付け焼き刃は事故の元。
大きな仕事になればなるほど役割や責任が細分化される。
- 950 名前：デフォルトの名無しさん [2018/09/01(土) 12:24:44.93 ID:rDlJp/s7.net]
- ぼやっとして結局何を言いたいのか良くわからんが
何か良い事を言いってみたい必死さは伝わった
- 951 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 12:52:20.45 ID:mPcVbgud.net]
- え？言いたいことがわからんの？
- 952 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:01:11.42 ID:8oBLXasx.net]
- そりゃあ馬鹿の言ってることは分からんだろ
- 953 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:13:44.90 ID:mPcVbgud.net]
- 言ってることがわからんから、言ってるほうが馬鹿だと思ってるだけじゃないの？
俺に言わせれば、馬鹿だから言ってることがわからないんだと思うが？
- 954 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:42:02.18 ID:8oBLXasx.net]
- 俺に言わせれば世界はお前を中心に回ってないってこと
- 955 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 13:47:09.53 ID:mPcVbgud.net]
- >>937
お前を中心に回ってるといいたいのかな？
- 956 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 14:37:08.16 ID:8oBLXasx.net]
- >>938
>>936
- 957 名前：デフォルトの名無しさん mailto:sage [2018/09/01(土) 14:47:05.92 ID:mPcVbgud.net]
- >>939
俺のレスがどうした？
- 958 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 02:27:34.18 ID:Tt3u8CpR.net]
- アルゴリズム辞典みたいなものを手元に置いときたいんだが、最も支持されてるのってどれ？
・網羅性が高い
・支持されている（売れている）
・日本語版がある
・コード例はあってもなくても良くて、あるとしたら C/C++ か擬似コードで
という条件で
テーマ別に「どれとどれとどれを持っとけばまず問題ない」という言い方でもありがたい
とにかく網羅性を重視してる
- 959 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:04:17.98 ID:OlESf3Ok.net]
- 英語は知らんけど、日本語なら
[改訂新版]C言語による標準アルゴリズム事典 (Software Technology)
奥村 晴彦
amzn.asia/d/bAqY5Be
が網羅性は随一じゃないかな。
改訂だけど初版が1991年で、収録アルゴリズムは増えてないらしいので、
機械学習とかここ25年の新分野は当然入っていない。
- 960 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:32:26.75 ID:/VBaeORw.net]
- 機械学習の何をアルゴリズム辞典に入れるべきだというのか
Amazonレビューかよテメェは
- 961 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 07:36:36.34 ID:5tN3iveh.net]
- >>942
この本はBoyer-Moore法が簡易版しか載っていないし、Aho-Corasick法も載ってないから弱い
- 962 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 08:37:54.35 ID:HF+7qfHp.net]
- より網羅的な対案示してからでないと批判にならないよ。
共立のアルゴリズム辞典が現存すればこっちも挙げてたかもしれん。
BM法に関してはコード例は簡略版のみだが。
個別のアルゴリズムについてどこまで踏み込むかは、
辞典の物理的な性質上取捨があるのはしかたないでしょ。
- 963 名前：デフォルトの名無しさん [2018/09/04(火) 10:34:21.16 ID:gEGTZvcA.net]
- >>943
+1
- 964 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 10:36:29.76 ID:ROt4XEkp.net]
- 名前がついていて解放も明らかになってるアルゴリズムに興味はない
そんなのいくらやっても新しいものは生み出されない
- 965 名前：デフォルトの名無しさん mailto:sage [2018/09/04(火) 14:25:14.21 ID:JAXadswE.net]
- >>947
先輩、かっけぇっす
- 966 名前：デフォルトの名無しさん [2018/09/11(火) 14:44:06.44 ID:O54onciS.net]
- 質問させてください。
マイコンからAD変換で入力したサイン波を配列に格納し、周波数を求めたいと思います。
ゼロクロスの位置を求めれば正確に周波数を求められそうですが、教えてください。
https://i.imgur.com/FC5XP0K.png
- 967 名前：デフォルトの名無しさん mailto:sage [2018/09/11(火) 16:27:37.38 ID:zEn+kcA0.net]
- 質問が不完全だけど、そのためのアルゴリズムを教えてほしいということでよい？
前提として、各周期で確実に2回だけゼロクロスすると保証できるのなら、
前回の値を覚えておいて、今回との積が0以下になったらゼロクロス。
この保証がないのなら十分長く波形をとってFFTしてピークを探す。
- 968 名前：デフォルトの名無しさん [2018/09/11(火) 22:09:31.90 ID:i7axZbyN.net]
- ♀だったらｾｸﾛｽ教えてやる
- 969 名前：デフォルトの名無しさん [2018/09/11(火) 22:11:28.88 ID:4O7I7zcY.net]
- え！？童貞なのにセクロスを！？
- 970 名前：デフォルトの名無しさん [2018/09/12(水) 03:44:12.77 ID:gw3HbkUV.net]
- できらあ！
- 971 名前：デフォルトの名無しさん mailto:sage [2018/09/12(水) 07:05:35.15 ID:Jy3sklaz.net]
- それページ逆だぞ
- 972 名前：デフォルトの名無しさん [2018/11/05(月) 18:00:44.74 ID:ajh0QscM.net]
- 有向グラフの有向閉路を求める問題です。
深さ優先探索を実行したときに、 Backward Edge が存在する。
⇔
有向閉路をもつ
⇒は自明ですが、逆はどう証明するのでしょうか？
- 973 名前：デフォルトの名無しさん mailto:sage [2018/12/03(月) 20:50:16.30 ID:wBSUle4B.net]
- 深さ優先、幅優先探索を理解するのにオススメの本ってありますか？(コードサンプル付きでできればC)
- 974 名前：デフォルトの名無しさん [2018/12/04(火) 09:57:38.19 ID:euG8Im7Y.net]
- https://www.amazon.co.jp/dp/4874084141
- 975 名前：デフォルトの名無しさん [2018/12/04(火) 10:14:50.08 ID:GTmuusXQ.net]
- >>957
全くおすすめできません。その本。
- 976 名前：デフォルトの名無しさん [2018/12/04(火) 10:27:11.51 ID:GTmuusXQ.net]
- >>956
グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野 孝夫
固定リンク: amzn.asia/d/2MetXvf
- 977 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 11:20:17.46 ID:6CbA0WHr.net]
- 馬鹿アスペの推奨ｗ
- 978 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 14:19:52.12 ID:X/ZQLD1J.net]
- 学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)
- 979 名前：デフォルトの名無しさん [2018/12/04(火) 14:28:35.23 ID:GTmuusXQ.net]
- >>956
プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部 有隆
固定リンク: amzn.asia/d/g8qmfS6
↑この本にも、 BFS、DFS共に書いてあります。
解説は非常に雑ですが。
- 980 名前：デフォルトの名無しさん [2018/12/04(火) 14:33:05.75 ID:GTmuusXQ.net]
- >>959
の本には、再帰を使う DFS プログラムが書いてあります。（スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。）
- 981 名前：デフォルトの名無しさん [2018/12/04(火) 14:34:21.14 ID:GTmuusXQ.net]
- >>963
スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。）
- 982 名前：デフォルトの名無しさん mailto:sage [2018/12/04(火) 14:39:02.72 ID:eKuwOju4.net]
- 前置記法（ポーランド記法） + 1 2
後置記法（逆ポーランド記法） 1 2 +
中置記法 1 + 2
確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している
- 983 名前：デフォルトの名無しさん [2018/12/05(水) 13:24:47.73 ID:2sSegHBZ.net]
- shaderって何回書き換えてもメモリ壊れない？
- 984 名前：デフォルトの名無しさん [2018/12/05(水) 21:47:02.62 ID:xYhP2Ga4.net]
- テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど
ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう
- 985 名前：デフォルトの名無しさん [2019/06/19(水) 04:49:26.98 ID:tVNS+22r.net]
- 【出資】松本卓朗 人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/
- 986 名前：デフォルトの名無しさん mailto:sage [2020/01/03(金) 12:48:16.96 ID:LiTO8m+L.net]
- O(n)で中央値を求めるアルゴリズムを思いついた
- 987 名前：デフォルトの名無しさん mailto:sage [2020/01/04(土) 01:21:11.30 ID:buSsFrEd.net]
- クイックセレクトのこと？
- 988 名前：デフォルトの名無しさん [2020/01/13(月) 02:33:48 ID:D6MgPK0q.net]
- こんにちは、初質問させていただきます、グラフアルゴリズム初心者です
・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。
考え方と共に、コーディング例をご教授いただけると幸いです。
浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。
お手数おかけしますが、ご助力いただけると幸いです。
- 989 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 04:31:10.60 ID:6QaMEdT1.net]
- 適当に言うけど、
すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある？
- 990 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 12:21:39.99 ID:jqPh5nAm.net]
- >>971
グラフのサイズが書いてないと答えられないな
- 991 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 13:32:08.60 ID:D6MgPK0q.net]
- >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。
- 992 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 13:32:16.76 ID:D6MgPK0q.net]
- >>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。
- 993 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 17:13:44.37 ID:jqPh5nAm.net]
- >>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる
- 994 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 22:42:08.62 ID:D6MgPK0q.net]
- >>976
ありがとうございます。
つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。
- 995 名前：デフォルトの名無しさん mailto:sage [2020/01/13(月) 23:30:01.64 ID:jqPh5nAm.net]
- >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
- 996 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 13:45:14.74 ID:oHYk5H5Q.net]
- >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
- 997 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 16:39:42.37 ID:Ex9G0OLU.net]
- >>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか
- 998 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 21:49:25 ID:oHYk5H5Q.net]
- >>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。
- 999 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:25:41 ID:Ex9G0OLU.net]
- >>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
- 1000 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:28:15 ID:Ex9G0OLU.net]
- https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな 重みなしだけど
- 1001 名前：デフォルトの名無しさん mailto:sage [2020/01/15(水) 23:56:14 ID:Ex9G0OLU.net]
- https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/
こっちは重み付きのやつ
- 1002 名前：デフォルトの名無しさん mailto:sage [2020/01/18(土) 22:58:37.26 ID:iLU56BHo.net]
- >>983
>>984
ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。
- 1003 名前：デフォルトの名無しさん [2020/01/19(日) 12:55:00.98 ID:VFlG/sWR.net]
- CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
- 1004 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 15:11:46.01 ID:+ZQhvd/Y.net]
- 巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね
- 1005 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 17:27:30.27 ID:/b+J8VIk.net]
- >>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
- 1006 名前：デフォルトの名無しさん mailto:sage [2020/01/20(月) 17:28:22.60 ID:/b+J8VIk.net]
- 途中で送信してしまった
このときの経路をvetorにいれておけばいい
- 1007 名前：デフォルトの名無しさん mailto:sage [2020/01/25(土) 23:49:17 ID:Q85YRMjK.net]
- >>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。
厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。
悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。
- 1008 名前：デフォルトの名無しさん mailto:sage [2020/01/26(日) 01:32:16.02 ID:63DOpTVc.net]
- 言語の基本的な部分はさすがによそでやろうや・・・
- 1009 名前：デフォルトの名無しさん [2020/01/26(日) 13:25:18.52 ID:eN1PAkvI.net]
- >>990
https://ideone.com/pShuim
↑一応動きました。
piという変数に経路を覚えさせています。
- 1010 名前：デフォルトの名無しさん [2020/01/26(日) 13:32:46.65 ID:eN1PAkvI.net]
- >>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
- 1011 名前：デフォルトの名無しさん [2020/01/26(日) 13:47:50.10 ID:eN1PAkvI.net]
- アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？
- 1012 名前：デフォルトの名無しさん mailto:sage [2020/01/26(日) 16:03:48.66 ID:gJO14xRt.net]
- >>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い
- 1013 名前：デフォルトの名無しさん [2020/01/26(日) 16:28:11 ID:eN1PAkvI.net]
- >>995
ありがとうございます。
機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。
- 1014 名前：デフォルトの名無しさん [2020/01/27(月) 12:15:36 ID:Dkceayzl.net]
- DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
- 1015 名前：デフォルトの名無しさん [2020/01/27(月) 17:15:29 ID:Xu7tzl7q.net]
- >>996
+1
- 1016 名前：デフォルトの名無しさん [2020/01/27(月) 17:16:05 ID:Xu7tzl7q.net]
- >>997
-1
- 1017 名前：デフォルトの名無しさん [2020/01/27(月) 17:16:23 ID:Xu7tzl7q.net]
- >>999
+1=1000
- 1018 名前：1001 [Over 1000 Thread .net]
- このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
- 1019 名前：過去ログ ★ [[過去ログ]]
- ■ このスレッドは過去ログ倉庫に格納されています
|
 |
