- 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
- 844 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 06:11:43.36 ID:+JtpRhMz.net]
- そうだね。そもそもソフトウェアは他の製品と違って
完全に同じものを複製するのに技術がいらないからね
コピーすればいいだけだし。
その点、何かを作る職人とはぜんぜん違うよね
そいういう寸分違わないものを作り出す職人は不要な業界
- 845 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 09:02:23.96 ID:XlZUepQP.net]
- >>825
そして、今は鉄道以外のほぼすべてのタイヤの接地面はゴムです。
そういうところもオブジェクト指向と、似てますね。
- 846 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 09:20:35.56 ID:hOelEibu.net]
- 以上、内容無し
- 847 名前：デフォルトの名無しさん [2018/07/22(日) 13:32:55.77 ID:snsF+l1o.net]
- >>826
この論理は完全にお花畑。
完全無欠のライブラリがありそれが唯一無二なら
つつっつき回すだけでいいだろうさ。
だけど現実はほぼ似たような機能で構文が違う、
それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
それに加わりローカルで作られた野良ライブラリがある。
当然人によってそれらの使い方の認識に齟齬が生まれる。
信用できるのは、自身の即興のデータ構造定義能力と、
アルゴリズム構築能力だけだ。
- 848 名前：デフォルトの名無しさん [2018/07/22(日) 13:34:08.83 ID:LiIRy0eu.net]
- 今必要なのは解読ではなくて解脱
- 849 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:02:08.11 ID:+JtpRhMz.net]
- >>831
> だけど現実はほぼ似たような機能で構文が違う、
> それに加え実行環境もバージョンも違うライブラリたちが乱立してるんだぜ、
乱立しているからなんだっていうんだろう？
乱立してるから自分で作れってことにはならないよな？
何が言いたいんだろう
> それに加わりローカルで作られた野良ライブラリがある。
自分自身で作成したもの = 他人から見れば野良ライブラリだからね
野良ライブラリは作るべきじゃないね
だから乱立されている中のどれかを使うってことになるわけだけど
そういう結論を言いたかったんだよね？
- 850 名前：デフォルトの名無しさん [2018/07/22(日) 14:02:42.93 ID:YGqHpPTt.net]
- >>831
データ構造作るだけだと付加価値が低いというか
ただの作業員でしかなくない？
新しい仮想通貨作るとかだったらすごいけど
- 851 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:06:57.17 ID:+JtpRhMz.net]
- まあ言えるのは、データ構造やアルゴリズムを作るだけの仕事なんて無いってことだな
やりたいからといって、それで金がもらえるわけじゃない
金を出す方がやってもらいたいことをやって金が出る
似たようなものを自作して、乱立させたって
そんなものに金を出す人はいない
- 852 名前：デフォルトの名無しさん [2018/07/22(日) 14:18:22.79 ID:LiIRy0eu.net]
- >>835
うむ
>>834
やったことないやつには判らんよ
- 853 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 14:24:06.48 ID:t9f4aq96.net]
- 座禅だな
- 854 名前：デフォルトの名無しさん [2018/07/22(日) 17:42:32.79 ID:bmpyz9fo.net]
- >>827
いや、ちょっと違う
プログラマという職業が、車輪を一から設計できる職人群と
それを再利用する専門家へと二極化していくというお話だよ
この二極化は以前から言われていたことだけど、
それを天下のMITが言い切って行動に移したことに>>826の意義がある
- 855 名前： mailto:sage [2018/07/22(日) 18:20:24.01 ID:+jM3tBOE.net]
- >>838
「職人」と「専門家」が逆ではないですか？
- 856 名前：デフォルトの名無しさん [2018/07/22(日) 19:59:44.17 ID:bmpyz9fo.net]
- いや、逆ではないよ
MITは計算機工学に特化しているわけでもなく、
機械工学、ロボティクス、生産工学、データ解析といった
あらゆる工学分野の専門家を養成し輩出している
そういった(計算機工学を除く)大半の「専門家」の卵達にとって、
優先すべきは(旧コースでSchemを使って学んでいた)計算機の動作原理ではなく、
計算機の利用方法である、という趣旨
彼ら「専門家」は決して計算機工学の専門家ではないが、
それぞれの分野に特化した高度な専門技術を有し、
与えられた問題を解決する道具として計算機を効果的に活用できる
- 857 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 20:38:21.89 ID:woAlzZC1.net]
- 役割が細分化したからそのニーズに応じたという話？
- 858 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 21:07:14.12 ID:+JtpRhMz.net]
- どんな仕事でも、その道の研究者ってのはいるだろう。
例えば数学者とかな。だけど世の中で必要とされてるのは
塾の数学の先生だったりするわけさ
もっとも大学に行った人の殆どは、大学で専攻していたものとは
関係のない仕事をしているわけだけどな
- 859 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 21:23:40.76 ID:MHyGLJ0L.net]
- 数学とコンピュータを一緒にするなよｗ
- 860 名前：デフォルトの名無しさん [2018/07/22(日) 23:03:00.98 ID:snsF+l1o.net]
- たとえばjsでオブジェクト構造をサーバに送りたいとする。
たったこれだけのことなのに邪魔くさい余計な機能が多すぎる。
わざわざ専用のクラスからインスタンス作って
専用の構文使ったりhttpヘッダー設定したりだ。
それでいてサーバ側では糞みたいな細かい仕様認識の違いでリクエストの内容が空だったりする。
サーバ側のコンフィグ見直したりjs側のコード見直したりするわけだ。
ログからライブラリのコード追っていくと大抵
過剰に技法使われてるから自ずと疑うべき探索
範囲は広くなる。
書き方はjQueryベースやangular typescriptなんかが混在してきて文法のちょっとした勘違いなんてのも生まれてくる。
だったらそんなライブラリ鼻っから信用しなけりゃいい。
ライブラリのインスタンスを介さずに多少原始的だが
文字列、数値 for文if文だけで大抵の問題は解決できる。
自力でJSON文字列に情報をぶち込んで送信してやれば、必ずサーバ側で取得できる。
サーバ側も下手なライブラリにパースさせないで自力でパースした方が慣れれば断然こちらの方が早い。
自力で作ったアルゴリズムは信用できるから
関数化しておいてまた似たような問題があったときに
使える。
俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
自分で作ったもの以外はそりゃ不便だろうよ。
- 861 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:31:00.85 ID:8Bgo+1zG.net]
- > たとえばjsでオブジェクト構造をサーバに送りたいとする。
https://api.jquery.com/jquery.post/
$.post( "test.php", { name: "John", time: "2pm" } );
こうだね。で？
- 862 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:37:38.62 ID:zgYMpfBL.net]
- それjqueryやんw
- 863 名前：デフォルトの名無しさん mailto:sage [2018/07/22(日) 23:58:50.05 ID:8Bgo+1zG.net]
- はい。このように他人の成果を利用して
目的を達成するのが今は重要って話です。
- 864 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 00:05:17.20 ID:jaGQY9G3.net]
- >>844
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
とりあえずお前が自力で作ったライブラリは
鼻っから信用しててないよ
- 865 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 00:19:04.74 ID:jaGQY9G3.net]
- >>844
> 俺が使うための自作ツールは他人は使わなくていいよ、どうせ価値観が違うんだからな。
> 自分で作ったもの以外はそりゃ不便だろうよ。
価値観の問題じゃない。単にお前が作ったコードに
バグがあるから使えないだけ。使わないんじゃない。使えない。
反論するならバグがない証拠を出すこと
テストコードをかけという話ね。
> だったらそんなライブラリ鼻っから信用しなけりゃいい。
お前が書いたコードは鼻っから信用できない。するしないじゃない。できない。
- 866 名前：デフォルトの名無しさん [2018/07/23(月) 06:43:27.98 ID:LtlhEJ9n.net]
- みなさんお気づきだろうか
>>844と>>849は同じことを言っている
- 867 名前：デフォルトの名無しさん [2018/07/23(月) 07:32:08.19 ID:LtlhEJ9n.net]
- jQueryはブラウザの差異を吸収するからね
同等のもの作ろうとしたら大変だよ
自前のコードを実装するのが汎用ライブラリを使うよりも早いとするなら
自前のコードは汎用ライブラリよりも機能が少ないものになる
要件がシンプルなら自作するのは効率が良いかもしれないね
システムをユーザのニーズに合わせてたら要件が複雑になり自作するメリットが得られない
ユーザがシステムの都合を忖度するならうまくいく
開発者にとっては桃源郷
開発者の幸せか、ユーザの幸せか
ぼくらはその選択を迫られてるんだ
- 868 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 09:47:19.69 ID:nk4BkCBO.net]
- 役所が作る神エクセルなんてのはユーザがシステムの都合に合わせてる典型例じゃないか、自作コードに拘るのは神エクセルを作るのと変わらぬよ
- 869 名前：デフォルトの名無しさん [2018/07/23(月) 11:01:38.63 ID:eU1p7hr8.net]
- >>842
自己紹介ですね
- 870 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 12:24:24.98 ID:jaGQY9G3.net]
- >>851
> 要件がシンプルなら自作するのは効率が良いかもしれないね
それは正しくない。要件はシンプルでも実装が大変なことがある。
そもそも「ライブラリの一機能の独自実装」などという要件は
実際には発生しない。これらは単に道具
要件を実装するのに、道具を使うか使わないかの問題
シンプルな要件でも、道具は使ったほうが効率は良いよ
もちろん道具を使えない人であれば、道具を使えるようになるまで時間が
かかるけど、それは素人がプロに速度でかなわないという人間の問題にすぎない
そう道具を使えないなら素人なんだよ。
- 871 名前：デフォルトの名無しさん [2018/07/23(月) 12:29:27.63 ID:aoV6LMU9.net]
- >>850
ヒント：バカは皆がオンリーワン
- 872 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 12:36:13.41 ID:jaGQY9G3.net]
- >>850
同じことは言ってないな
>>844はよくわからないのはライブラリのせいだ
自分で作れば、そのライブラリよりもわかりやすくなるはずだ
って机上の空論を言ってるだけ
- 873 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 13:54:17.34 ID:wSAPNw7p.net]
- PGの愚痴
- 874 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 15:02:52.51 ID:EWSlu15m.net]
- りんごをむくのにピーラーを使うのもいいが、一度ナイフで剥くのを試すのも重要だし、かじってみるのもいい。
道具が解決する問題がなんなのか、体験することは、多くの人にとって有益だと思う（経験主義者）
- 875 名前：デフォルトの名無しさん mailto:sage [2018/07/23(月) 15:32:18.18 ID:1W7qAEKf.net]
- そこでピーラーを作るのは大変だとか見当違いの所に流れていくやつがいる。
ピーラー（ライブラリ）を使うか、ナイフを使うかだ
ライブラリ？中見たけどわけのわからないことをしてる
理解できない。ナイフのほうが単純だ。ナイフなら作れる。
なぜか作る話になってしまっている。
- 876 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:38:29.17 ID:nk4BkCBO.net]
- 例え話では本質から遠ざかるばかりよ
- 877 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:39:54.99 ID:nk4BkCBO.net]
- 例え話は物事を理解してなくてもそれらしく見せるから知ったか振りが捗りますなあ
- 878 名前：デフォルトの名無しさん mailto:age [2018/07/23(月) 15:41:15.55 ID:nk4BkCBO.net]
- ワシも神エクセルとか言ってた
- 879 名前：デフォルトの名無しさん mailto:sage [2018/07/24(火) 18:13:24.95 ID:Ce588Hp1.net]
- 全部やれ
- 880 名前：デフォルトの名無しさん [2018/07/24(火) 18:20:36.91 ID:WBO96fmU.net]
- 最後までやれ
- 881 名前：デフォルトの名無しさん mailto:sage [2018/07/24(火) 20:40:39.40 ID:6SRwrowy.net]
- 例えがドラゴンボールではないからだろ
- 882 名前：デフォルトの名無しさん [2018/07/27(金) 22:10:24.05 ID:jesqHVAc.net]
- MVC, DAO, O/Rマッピングの発展形として、
俺は「R/Rマッピング(リクエスト/リレーショナルマッピング)」を
提唱したい。
そもそもDB上のカラムと本当に対応付けたいのは画面上のname属性
なんだよなぁ。
オブジェクトを必ず介する必要はない。
(処理が込み入ってきたら定義してもいい程度。)
まず前提として、DBのカラム名とHTML上のname属性を
必ず同じキーにすることを前提とする。(HTML上に関係ない
キーがあっても問題はない。)
その前提の上でDBのカラム名一覧を先に取得しておき、
カラム名リストと、受信したname属性のキーをマッチングして、
マッチングした時にそのキーから取得した値をSQLに突っ込んで
クエリを行う。
こうすることによって、プログラミング言語処理の中で
具体的な「項目名」をほとんど登場させずに処理することができる。
自分でやったらすごく便利だった。
こうなるとそもそもモデルとかDAOとかいらなくね?
ってなって来たよ。
項目数がどんなに二十, 三十と並んでいようがダラダラと羅列しない。
特別な処理を入れたいときだけその項目のカラム名を使って
ifで分岐して日付変換とかをおこなう。
その特別な処理も日付,範囲系、選択肢系などパターンを押さえれば、
めちゃめちゃ簡素化できる。
- 883 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:35:03.11 ID:d6sXPNYF.net]
- あ、はい、4行ぐらいしか読んでないけど、
そのリクエストに含まれる名前 = オブジェクトのフィールド名なんだから
あんたが言ってるリクエスト = オブジェクトってこと
あとはストレージをなんにするかの話。
ODBMS（オブジェクトデータベース）を使えばそのまま読み書きできる
だけど、なんやかんやでリレーショナルデータベースを使わないといかんから
O/Rマッピングが必要になる
- 884 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:38:45.06 ID:d6sXPNYF.net]
- >>886
あとRailsでも勉強しようね
普通は画面のname属性 = データーベースのフィールド名になってるから
（もちろん必要なら対応してないものも作れるけど）
- 885 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 22:58:52.80 ID:HpMLTKup.net]
- 二層CRUDオモチャ
昔から誰もが一回は考えるアイデアだよ
画面起点だとどうしてもアプリケーションロジックの居場所がないから簡単に作れてもアプリとしての価値が無い
DB起点だとSQLにアプリケーションロジックを埋め込んんで最低限のアプリの体裁は保てるけど保守性が最悪で使い物にならない
という理由から廃れた
なので今はオブジェクト指向の言語でモデルを書いてモデルから画面やDBを生成して微調整しようってのがスタンダード
これなら労力をかけずに豊かな振る舞いを持つアプリケーションを作れるしロジックがモデルに集まるから保守性も高い
- 886 名前：デフォルトの名無しさん [2018/07/27(金) 23:43:33.59 ID:jesqHVAc.net]
- >>869
モデルを作るとしても処理が複雑になる部分だけ
部分的でいいんじゃないか？
全ての要素に対して網羅的にモデルつくって
セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
気がするんだが。
なにせ機能を複製する時にこれらのずらずら並んだモデルオブジェクト名や
キーの名前をを置換しなけりゃならない。
ならない。
- 887 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:51:45.25 ID:d6sXPNYF.net]
- > セッター/ゲッター定義して...ってのは肥大化して馬鹿げてる
それはJavaだけ
Javaが馬鹿げているだけ
- 888 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:52:00.90 ID:d6sXPNYF.net]
- だからいい加減Railsとかを勉強しろと
- 889 名前：デフォルトの名無しさん mailto:sage [2018/07/27(金) 23:55:06.84 ID:h+bQHJad.net]
- .NET Coreにしとけ
- 890 名前：デフォルトの名無しさん [2018/07/28(土) 02:15:45.58 ID:kGN2HSKI.net]
- >>859
さてリンゴをむくか、
ピーラーがないと剥けないから探すか、
あれ、どこにしまったかな？
この引き出しにもこの棚にもない。
道具だらけで見つからない。
店に買いに行こう、たくさんのピーラーが並
んでいてどれを選ぼうか？
ようやく買ってきて構築しているけど、
どうや刃が付け替え式で色々な刃が付け替えられる
ようだ。
刃を買い忘れたからまた買いに行くか…
はぁはぁ…すごい刃を買ったぞ！今構築中だ。
おや？この刃はリンゴを剥く用途には対応して
ないようだ。もう疲れたしこれ無理だろ。
ピーラーが無いから俺にはリンゴを剥くのは
無理だ。前は引き出しにあったからむけたけど
今はできなくなった。
一方、いつも愛用のナイフで剥いてるならそう
はならない。
いつもポッケに入れているからなくさないし、
最悪自作で調達できる。
使い慣れてるからピーラー使うやつと遜色ないスピードで剥けるし形も綺麗に剥ける。
- 891 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 02:38:56.80 ID:Wq9fNSFf.net]
- Rails なんか、全自動！
DB の表の構造が定義された、メタテーブルを参照して、
表の列名なども自動的に取得する
- 892 名前： mailto:sage [2018/07/28(土) 03:14:15.05 ID:AqK1vkX7.net]
- >>873
Windows 上で構築できますか？
- 893 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 07:06:05.64 ID:rUA3L/4N.net]
- >>870
それでずらずら並んで嫌だというなら、おまえのやり方だと画面定義もずらずらならぶし、テーブル定義やSQLがずらずら並んで更にわけわからなくなるだろ
- 894 名前：デフォルトの名無しさん mailto:sage [2018/07/28(土) 09:41:18.41 ID:Z4XsBwkZ.net]
- >>876
できる
- 895 名前： mailto:sage [2018/08/11(土) 11:14:19.06 ID:vW2Ha+vq.net]
- >>878
やりかたは？
- 896 名前：デフォルトの名無しさん mailto:sage [2018/08/11(土) 11:16:30.51 ID:CORkkjHt.net]
- >>879
住民税納めてる？
- 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 名前：過去ログ ★ [[過去ログ]]
- ■ このスレッドは過去ログ倉庫に格納されています
|
 |
