- 1 名前：デフォルトの名無しさん mailto:sage [2013/03/03(日) 18:10:11.63 .net]
- 【関連スレ】
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
- 655 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:02:33.27 ID:sBqWnM4N.net]
- >>647
Niklaus Wirth: 「アルゴリズム+データ構造=プログラム」日本コンピュータ協会
浅野哲夫: 「データ構造」近代科学社
桐山清: 「C言語によるデータ構造とプログラム書法」森北出版
近藤嘉雪: 「定本 Cプログラマのためのアルゴリズムとデータ構造」ソフトバンク
渡邊敏正: 「データ構造と基本アルゴリズム」共立出版
のどれにも、AVL木（バランス木）の回転の解説あるよ
- 656 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:19:55.17 ID:woY7u5MP.net]
- 今時Wirth先生の本はないわ。
均衡二分木はあまり実行効率が良くないAVL木中心だし、
多分木派生の二分木は赤黒じゃないし。
しかも言語がPascal。
言語屋さんだけあってコードは綺麗。
- 657 名前：デフォルトの名無しさん mailto:sage [2014/07/04(金) 16:27:00.41 ID:iKaePYIV.net]
- 『アルゴリズム・イントロダクション』読め。
総合版は武器にもなってお得だぞ。
- 658 名前：デフォルトの名無しさん [2014/07/05(土) 10:32:09.33 ID:5deLSK6V.net]
- セジウィックのアルゴリズム本もわかりやすくておすすめ
- 659 名前：デフォルトの名無しさん mailto:sage [2014/07/05(土) 13:44:41.02 ID:R8cFDXwQ.net]
- アルゴリズム・イントロダクション
セジウィック新版
の二択だな。
アルゴリズム・イントロダクションをちら見してみて挫折しないようならこっちやればいい。
この二冊ほどしっかり書けてる本はほとんどない。TAOCPは実装言語が独自すぎて除外。
- 660 名前：612 mailto:sage [2014/07/06(日) 02:00:23.53 ID:+YGfR2l7.net]
- >>645
石畑清のは、AVL木の回転について、図入りの説明がある
ただし、25年前の本で、ソースコードがPascal
- 661 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 03:16:22.62 ID:3qD8tN7V.net]
- 石畑清の本はいいよやっぱり。説明が細かいし。
しかしPascalだから困るという意見が結構多いのが不思議。
アルゴリズムを説明するためのたかが数十行のコード、言語仕様やライブラリに
深く依存しているわけでもないプログラム読むのにそんな苦労するのか？
疑似コードとして読めばいいでしょ。俺もPascal知らんけど充分理解できるよ。
もひとつ言っとくと、石畑清の本、巻末にちゃんとCとLISPのコード例も付録
で載ってるんだよ。ほんとは持ってないんじゃないのお前ら？
コピペしかできない知恵遅れにも安心（笑）
- 662 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 07:43:12.94 ID:ETigXUGg.net]
- Pascalは配列添字が1から始まるから、他の言語に移植するときに、
Off by one エラーに注意しながら書き直す必要がある。
これが面倒。
- 663 名前：デフォルトの名無しさん mailto:sage [2014/07/06(日) 09:25:03.24 ID:PgwRX7N+.net]
- >>662
1オリジンを他のオリジンに直すだけだろう？簡単な線形変換をかますだけなのでは？
ま、2オリジンに書き直すなら多少のぐちゃぐちゃは厭わないが、1オリジンを0オリジンにわざわざ直す必要もない
- 664 名前：デフォルトの名無しさん [2014/07/06(日) 23:35:38.44 ID:I8o/e02M.net]
- 大学のアルゴリズムの講義の教科書が石畑Pascal本だ
- 665 名前：デフォルトの名無しさん mailto:sage [2014/07/07(月) 06:33:10.27 ID:iqLntt6B.net]
- ６６６
- 666 名前：デフォルトの名無しさん mailto:sage [2014/07/07(月) 12:41:09.24 ID:mcdr45lP.net]
- AVL木は挿入や削除で必要になる回転が多いので遅い。
バランスしてるからオーダーは良いが、
オーダーを計算する時に無視する定数部が悪い。
均衡二分木がAVL木しか書いてない本はとてつもなく古い。
- 667 名前：612 [2014/07/07(月) 23:46:14.44 ID:dH0g1YaP.net]
- >>661
漏れは研究家で、本はプログラミング・コンテスト・
チャレンジブックしか持っていない
漏れは立ち読みするから、誰よりも厳しいよw
まず図を載せていない著者を評価しない。
そういう著者はコピペしているだけで、
本当にアルゴリズムを作っていないかも
いかに読者に解かりやすく説明できるか？
まず図を作る段階で、戦いは始まっている
- 668 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 00:19:27.31 ID:WA0uMVhU.net]
- 入門 データ構造とアルゴリズム
www.oreilly.co.jp/books/9784873116341/
＞インド工科大学（IIT）と企業の両方で豊富な経験を持つインド人著者による、
＞実例豊富なデータ構造とアルゴリズムの解説書。
この本の評価どうですか？
- 669 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 03:59:34.21 ID:KMzZlwYF.net]
- 目次を見る限り、インド人ってネタを活かしてるようには見えないな
- 670 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 06:23:28.25 ID:C3Ow5lln.net]
- 漏れは研究家でw
誰よりも厳しいよww
評価しないwww
- 671 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 08:35:30.86 ID:+1SkhcPX.net]
- 朝からニヤリとさせてもらった
さて働こう…
- 672 名前：デフォルトの名無しさん mailto:sage [2014/07/08(火) 20:48:31.13 ID:KjaCWqA1.net]
- >>666
不正確だ
挿入で必要な木の回転は、ただの一回だけ、問題は削除だね。これは AVL も赤黒木も同じ
削除が頻繁におこなわれるのなら、左右のバランスのゆるい赤黒木がいいね
- 673 名前：デフォルトの名無しさん mailto:sage [2014/07/09(水) 00:42:28.78 ID:nWprtmY/.net]
- インド人嘘つかない
- 674 名前：デフォルトの名無しさん [2014/07/09(水) 23:39:21.70 ID:8efLPFpl.net]
- アルゴリズムの名著にはPascalで書かれた本も多いし、Pascalもひと通り勉強したほうがいいんだろうか？
- 675 名前：デフォルトの名無しさん mailto:sage [2014/07/09(水) 23:51:22.77 ID:9Qxa4e89.net]
- pascalはCというかPL/I系統の言語が出来るなら読むのはそんなに難しくない。
- 676 名前：デフォルトの名無しさん mailto:sage [2014/07/10(木) 13:54:07.94 ID:iLbfPtwr.net]
- CがPL/I系統？
ていうかPascalないしAlgolは、いちいち勉強なぞしなくとも読むのにそうは苦労しないだろ。
Algolには名前呼びとか変な機能があるが、普通はそういうトラップは回避して説明に使うから。
- 677 名前：デフォルトの名無しさん [2014/07/16(水) 08:34:15.83 ID:uBdPgdk4.net]
- qiita.com/kenokabe/items/13ea8d2da6adce1b3b9a
関数型プログラミングとオブジェクト指向の抜き差しならない関係について整理して考える
お、これはなかなか優秀な人が現れたな。わかりやすい良エントリ。
- 678 名前：デフォルトの名無しさん mailto:sage [2014/07/16(水) 09:49:46.76 ID:VblCYr0v.net]
- >>677
スレ違いです。こちらへどうぞ。
【毛の壁】脱アルゴリズム宣言【FXST】
peace.2ch.net/test/read.cgi/tech/1403215505/
- 679 名前：デフォルトの名無しさん mailto:sage [2014/07/16(水) 23:55:51.33 ID:FEyT2AKy.net]
- アルゴリズムを学ぼう (アスキー書籍)
川中 真耶
www.amazon.co.jp/dp/B00JGI5H2I/
Amazonのレビューでも評価低いけど、この本意外に良書やね。
もっとレベルが低いのかと思ってたけど、二分木だとAVL木の回転とかまで
ちゃんと説明している。
ただ、レビューでも触れられているけど、ストーリー仕立てにする意味が
ほとんどないというか、単純につまらない。
こういうのが受けると思ったんだろうけど、キャラクターにも魅力がない。
Kindle版だと安いから買って読む価値はある。
- 680 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 00:43:35.51 ID:YW/aq4b0.net]
- アルゴリズムを学ぼう サポートページ
https://sites.google.com/site/adtalgo/home
- 681 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 10:13:30.44 ID:S7UqHs8v.net]
- >>679-681
【これは】重大な誤り【ひどい】
１つ本当にひどい誤りを含んでおりました。本当に申し訳ありません。恥ずかしくて夜も寝られません。
P. 33
O(aN) = O(eN)
この文章の記述は大嘘です。デタラメです。
指数の底を変えることは出来ません。
そもそも数式の展開も誤っています。
指数の場合も同様で〜〜となる。の文を削除。
わろ・・・えない
- 682 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 18:39:54.82 ID:FWtSwDTq.net]
- あまり話題にならないけど丸善から出ている黄色い表紙の装丁のアルゴリズム本でオススメある？
お前らには難しくくて縁のない本が多い？
- 683 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 19:43:15.82 ID:8B88F9S3.net]
- |￣｀`''- ､
| ｀ﾞ''ｰ- ､ ＿＿＿＿＿＿__
| ,. -‐ ''´￣￣｀ヽ､＿ /
|, - '´￣ ｀ヽ、 /
／ ｀ヽ､ヽ /
_/ ヽヽ/
／ / / / / / ヽﾊ
く / /! | 〃 _/__ l| | | | | | | ||ヽ
＼l// / | /|'´ ∧ || | |ｰ､|| | | l | ヽ
/ハ/ | | ヽ/ ヽ | ヽ | || /|ヽ/! |/ | ヽ
/ | ||ヽ { ,r===､ ＼| _!V |// // .! |
| || |l |ヽ!'´￣｀ﾞ , ==ミ､ /イ川 |─┘
| ﾊ|| || | """ ┌---┐ ｀ / // |
V !ヽ ト! ヽ､ | ! / //| /
ヽ! ＼ハ` ､ ヽ､__ノ ,.イ/ // | /
┌/）/）/）/）/）/）/）/）/）/）lｰ/ ` ー‐┬ '´ レ//l/ |/
|（/（/（/（/（/（/（/（/（/（/│|| |＼ 〃
r'´￣ヽ. | | ト / ＼
/ ￣｀ｱ | | | ⌒/ 入
〉 ￣二) 知ってるが | | | ／ ／/ ヽ
〈! ,. -' | | ヽ∠-----', '´ ',
| ＼| | .お前の態度が | |<二Z二￣ ／ ',
| | | _r'---| [ ｀`ヽ､ ',
| | | 気に入らない >-､__ [ ヽ !
＼.| l. ヽ､ [ ヽ |
ヽ| ＼ r' ヽ､ |
- 684 名前：デフォルトの名無しさん mailto:sage [2014/07/20(日) 22:33:37.10 ID:3rueaPG+.net]
- そう言わず教えろよ
- 685 名前：デフォルトの名無しさん mailto:sage [2014/07/21(月) 20:25:53.74 ID:Ecx8KQMM.net]
- 本ばかり読んでないで実践しろよ
- 686 名前：デフォルトの名無しさん mailto:sage [2014/07/23(水) 01:29:55.54 ID:dHvcLkvH.net]
- 結城浩の「Java言語で学ぶデザインパターン入門」ってオリジナルと増補改訂版って
買い直した方がいいぐらい違いが大きいんですか？
- 687 名前：デフォルトの名無しさん mailto:sage [2014/07/23(水) 08:13:43.33 ID:Qr1azPSk.net]
- Cookieを使わずにユーザーを追跡する仕組みが普及しつつある
it.slashdot.jp/story/14/07/22/0613210/
- 688 名前：デフォルトの名無しさん mailto:sage [2014/07/24(木) 22:18:02.88 ID:wzSFtnz7.net]
- GoFは言語が未熟だった時代の名残のようなもの
現代的なほとんどの言語（特に動的型付言語）では、多くのパターンが適用できない
（適用しても、バッドパターンにしかならない）
Javaなどの一部の古めかしい静的型付言語では、まだ頼る余地は残っていたが
そのJavaでさえも関数型の要素を取り入れ、設計が大幅に変わってきている
GoF自体の改定でもなければ、改めて学ぶ価値はない
- 689 名前：デフォルトの名無しさん mailto:sage [2014/07/24(木) 22:53:43.17 ID:GcACTNu8.net]
- なんだ本人が来たのか（笑）
- 690 名前：デフォルトの名無しさん mailto:sage [2014/07/29(火) 17:13:50.87 ID:qGOKoo8w.net]
- 突然ですが質問させてください
重みなし無向グラフの場合、ダイクストラ法より反復深化の方が計算量少なくて済むんですか？
- 691 名前：デフォルトの名無しさん mailto:sage [2014/08/19(火) 13:41:16.96 ID:46ZruSDn.net]
- アルゴリズムとプログラミングをビジュアルで一挙に理解できる「VisuAlgo」
gigazine.net/news/20140819-visualgo/
- 692 名前：デフォルトの名無しさん mailto:sage [2014/08/31(日) 09:31:36.46 ID:TsfChlj7.net]
- 「アルゴリズムを学ぼう」は続の方が面白いな。
- 693 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 13:15:21.81 ID:bjSSfYoR.net]
- qiita.com/kenokabe/items/821ce4020644372b648c
＞「アルゴリズム」とは「バズワード」であり、「一般的に命令型プログラミング
＞パラダイムを指し示す」のであり、その他の使用は一般的ではない、ということ
＞です。
勉強になるな。このページ。
- 694 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 15:45:42.81 ID:FbNt5hSi.net]
- >>693
どこらへんが？
- 695 名前：デフォルトの名無しさん mailto:sage [2014/09/14(日) 16:00:30.06 ID:r0J72yK/.net]
- >>693 毛の壁は隔離スレから出るんじゃねぇよ
peace.2ch.net/test/read.cgi/tech/1403215505/l50
- 696 名前：デフォルトの名無しさん mailto:sage [2014/09/16(火) 02:48:17.06 ID:BRRsQsEe.net]
- そんな意地悪言うなよ。
- 697 名前：デフォルトの名無しさん mailto:sage [2014/10/07(火) 20:54:36.34 ID:3NSGj8n/.net]
- 死ねゴミ共がw
- 698 名前：デフォルトの名無しさん mailto:sage [2014/10/13(月) 00:56:00.10 ID:hQ/UKOA3L]
- なぜか放置されてる合法ハーブのサイト
www.unitepopulaire.org/
unepsefalliance.org/
www.love-salvia.com/
xn--ccke7d0a7en7a6d6eqb4l.com/
www.esodam.org/
herb-patio.jp/
xn--edkpew5hb5jf4159d0glkskyw0ckwox9v.com/
- 699 名前：デフォルトの名無しさん [2014/10/24(金) 21:39:41.30 ID:VyYUZ4Z5.net]
- カリー化とは何でしょうか？
- 700 名前：デフォルトの名無しさん mailto:sage [2014/10/24(金) 21:46:02.67 ID:zvGM4ELq.net]
- 「大抵のものはカレー味にしとけば失敗しない」という理論
- 701 名前：デフォルトの名無しさん [2014/10/24(金) 21:54:38.69 ID:VyYUZ4Z5.net]
- なるほど深いですね
- 702 名前：デフォルトの名無しさん mailto:sage [2014/11/25(火) 23:14:09.49 ID:ghl2SNY1.net]
- は？
- 703 名前：デフォルトの名無しさん mailto:sage [2014/11/26(水) 16:03:51.97 ID:cap+vDqw.net]
- ねんまつ
- 704 名前：デフォルトの名無しさん [2015/02/04(水) 10:21:19.15 ID:QfhTV/If.net]
- 1うんこ
- 705 名前：デフォルトの名無しさん mailto:sage [2015/02/21(土) 15:18:37.61 ID:Bqyo/mYz.net]
- 「オブジェクト指向のこころ」って原題とは何も関係ない変な題名で誤解されているけど、実はデザインパターンの良書だよね
結城本みたいなトイプログラムじゃなくてちゃんと仕事に活かせるコードや考え方が載ってる
もっと評価されるべき本だと思う
- 706 名前：デフォルトの名無しさん mailto:sage [2015/02/21(土) 17:25:01.22 ID:Qj5PkULS.net]
- まるち
- 707 名前：デフォルトの名無しさん [2015/03/16(月) 00:54:31.01 ID:pKR+yvmi.net]
- アルゴリズム！重要度を増していく、今までも、そしてこれからも
- 708 名前：デフォルトの名無しさん mailto:sage [2015/03/16(月) 01:07:48.91 ID:EXoRrBXi.net]
- 増しません、基本ではあるが
- 709 名前：デフォルトの名無しさん mailto:sage [2015/03/16(月) 06:58:50.72 ID:dto99C0o.net]
- 関数型が来る！とかと同じようなアレだな
- 710 名前：デフォルトの名無しさん mailto:sage [2015/03/19(木) 20:04:29.25 ID:rGfQi3lS.net]
- グーグル・アルゴリズム
アマゾン・アルゴリズム
アルゴリズム体操
- 711 名前：デフォルトの名無しさん [2015/03/23(月) 20:17:07.02 ID:v5lqXW2+.net]
- >>662
あんたなあ･･･ ハァ。
線形代数の教科書の行列、ベクトルは全部、添字１からだろ。
それをC言語では０から始めなければならないから「１つズレ」の
バグがでるんだろう。
あんたの言ってることは本末転倒だ。この田分け！
唯一の例外がFFT。唯一、添字が一定成分に対応した0から始まるから
- 712 名前：デフォルトの名無しさん mailto:sage [2015/03/23(月) 23:50:39.23 ID:VDUQlxD5.net]
- >>711
おらの教科書では自然数は 0, 1, 2, ....
- 713 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 00:52:58.38 ID:MX5B1wfa.net]
- 自然数の定義の話題は宗教戦争に発展するのでNG
- 714 名前：デフォルトの名無しさん [2015/03/24(火) 01:10:04.30 ID:Ve+M57ZM.net]
- 自然数が初等的算術を展開するのに必要十分な集合じゃないと困るでしょ。
算術の基礎になれないような集合に「『自然』数」なる名称を与えて特別視する理由がない。
で、0なしの{1,2,...}ではペアノ算術のモデルすら構成できないんだから、
自然数に0入ってなきゃ困ります。
- 715 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 02:16:41.68 ID:qocM3p7p.net]
- そういや空集合もあらゆる集合の部分集合だもんな
自然数にもゼロが会った方が自然な気はするな
- 716 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 03:17:40.76 ID:O1VRnX3O.net]
- 正直そういうことはどうでもいい
ただ正の整数と同じ意味なら言葉が勿体無いから０も入れればいいじゃん
- 717 名前：デフォルトの名無しさん mailto:sage [2015/03/24(火) 12:37:46.16 ID:c6mpFC05.net]
- なに、実は >>711 が田和けであることを示せばいいだけの話
- 718 名前：662 mailto:sage [2015/03/24(火) 20:19:23.88 ID:aWlBWbGCG]
- アセンブリ言語を使ったこともない奴がデカイ面できるようになったんだな。
2chも本格的に終わってるわ。
などどscで書いてみる。
- 719 名前：あ mailto:sage [2015/04/04(土) 09:36:37.38 ID:zehumhhz.net]
- 1〜6の整数がランダムに並んでいる時、これを最小手順で並べ替える
アルゴリズム知ってる人、思いつく人いたら教えてほしい
隣で比較する基礎の解放ではなく最小手順
5,6,3,2,4,1 → 1,2,3,4,5,6 にする最小手順
- 720 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 09:42:25.65 ID:QuAhdSHj.net]
- ソート自体不要
結果として1,2,3,4,5,6を返せばいいｗ
- 721 名前：あ mailto:sage [2015/04/04(土) 09:46:00.61 ID:zehumhhz.net]
- それだと6回かかるでしょ
- 722 名前：あ mailto:sage [2015/04/04(土) 09:49:01.47 ID:zehumhhz.net]
- あ、ごめん。ついwを付けられて
上では1-6って書いたけど、0-99の100個の数字を最小回数でソートしないと
いけない問題に今ぶつかってて。誰か賢い人いたら助かるなーって思って書いてみた
- 723 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 10:00:43.23 ID:QuAhdSHj.net]
- >>721
1,2,3,4,5,6と決まった数字がランダムに並んでだけだよね？
どうランダムに並んでようが、ソート結果は常に1,2,3,4,5,6になるんだから、
最初からその結果を用意しておいて、どういう並びであってもそれを１回返せばいい
ということ。
宿題の意図としては求めてないだろうから無視していいけどね。
- 724 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 10:12:22.71 ID:8tbUo2zR.net]
- ソートのアルゴリズムなんてググればいくらでも解説されてるでしょ
ttp://www.it-shikaku.jp/top30.php?hidari=02-02-02.php&migi=km02-02.php
それじゃ何か足りないの？
- 725 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 11:37:48.38 ID:9IYCOCMd.net]
- >>719
sleepsort
- 726 名前：あ mailto:sage [2015/04/04(土) 16:50:06.49 ID:zehumhhz.net]
- >>724
ありがとう、平均回数も乗ってるこのページ凄い役だった
とりあえず、これでやってみる。>>725 何、これ初めて見たｗ
みなさん、ご協力本当に感謝します。
- 727 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:12:22.13 ID:vj4bzuy0.net]
- sleep sort は、bucket sort とみなすべきだろうし、1,2,3,45,6を返すっていうのもそうだよね。
質問者の質問の意味は、最小 sorting network を求めろってこと？
- 728 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:26:57.58 ID:w5ibkrLo.net]
- 最小置換手順が欲しいと推測
- 729 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 21:55:13.09 ID:vj4bzuy0.net]
- ああ、なるほど。そしたら最長増加部分列求めりゃ良いね。
- 730 名前：デフォルトの名無しさん mailto:sage [2015/04/04(土) 22:21:32.50 ID:bg9jdXhF.net]
- て、手順としてどのようなオペレーションが許容されるかで変わりますね。当たり前だけど。一手順で、隣接のスワップしか許さないのか、任意の場所のスワップを許すのか、任意の繋ぎ変えを許すのか、任意の一つの数字を任意の場所に入れることを許すのか。
- 731 名前：デフォルトの名無しさん mailto:sage [2015/05/16(土) 22:03:28.98 ID:y/t4uXt/.net]
- 日本人はスマホとかコンビニとか省略するのが好きだけど
検索アルゴリズム的にはスマートホン、コンビニエンスストアの方が１０倍早く検索できるんだよな。
記憶力をよくしたかったら、省略するのをやめましょうね。
- 732 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 05:07:39.56 ID:M9Jld2yx.net]
- ア････
あ･思い出した
ア､はいいよね
- 733 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 06:49:06.78 ID:MQbFTiCx.net]
- >>731
面白い脳味噌してるなコイツ
- 734 名前：デフォルトの名無しさん mailto:sage [2015/05/17(日) 12:03:39.74 ID:Cq+Owzl6.net]
- >>731
理屈が分からないのですが、もう少し詳しく説明していただけませんか。
同趣旨のことを解説したネット上の記事を紹介していただけるだけでも構いません。
- 735 名前：デフォルトの名無しさん mailto:sage [2015/05/18(月) 10:30:22.61 ID:DlA37DUd.net]
- でかい方が見つけやすいでしょ
- 736 名前：デフォルトの名無しさん mailto:sage [2015/05/18(月) 20:00:18.97 ID:qgceviCB.net]
- >>735
それでは曖昧すぎて説明になっていないんじゃないかな。
どのようなデータ構造に対してどのようなアルゴリズムで検索するときに、
検索対象「スマホ」よりも検索対象「スマートホン」の方が10倍早いと言っているのか。
こういうのを話す場でしょ、ここは。
まぁ元々が曖昧だから、>>731以外だれも説明できないとは思うが。
- 737 名前：デフォルトの名無しさん mailto:sage [2015/05/30(土) 23:11:38.07 ID:GbYkPqTc.net]
- >>731
は収録数の少ないシソーラス辞書しか持っていないらしい
- 738 名前：デフォルトの名無しさん [2015/07/30(木) 16:31:15.15 ID:gNKRMuak.net]
- A スター アルゴリズムの計算について質問をしたいのですがいいでしょうか？
- 739 名前：デフォルトの名無しさん mailto:sage [2015/07/30(木) 19:32:45.75 ID:StheyCIu.net]
- 別に断る必要は無い
解る者が居れば答えるし、そうじゃなければ放置されるだけ
- 740 名前：デフォルトの名無しさん mailto:sage [2015/07/30(木) 20:18:42.09 ID:oAGEjgo8.net]
- ｇｇｒｋｓ ↓
- 741 名前：デフォルトの名無しさん [2015/07/31(金) 14:17:38.86 ID:qB8zjiMb.net]
- 開始地点と到着地点を入れ替えても同じサイズの経路が出来ます。
そしてそれは地図を斜めに線分したものに対象である。
そのときの計測時間が余りにも違うのですが、これは何が主な原因でしょうか？
ttp://gmdev.xrea.jp/st/up/1090.png
ttp://gmdev.xrea.jp/st/up/1091.png
- 742 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 15:24:20.10 ID:qnWPb5RQ.net]
- >>741
左上から順に探索してるから開始位置によって処理時間違うとかかな？
マップを上下/左右反転して同じコース走らせてみたらもう少し詳しくわかるかも
- 743 名前：デフォルトの名無しさん [2015/07/31(金) 18:33:06.81 ID:qB8zjiMb.net]
- 上下反転でも上記と同じような動きになってしまいました。
ttp://gmdev.xrea.jp/st/up/1092.png
ttp://gmdev.xrea.jp/st/up/1093.png
左右はまだ試していませんが多分同じ結果になるかと。
一応補足として、# of calclation は
while (!openList.isEmpty()) {
count++; ....
です。
上下反転したときの経路は元と違って同じですし。
しかし、この四つの中で違うのは時間だけでほかは経路サイズも、#も一緒っていう。
Ａ＊って元々こんな特性なんでしょうか？
- 744 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 19:02:30.87 ID:km5orOmS.net]
- >>743
これ斜め移動できるっぽいのに何で真ん中通らないの？
- 745 名前：デフォルトの名無しさん [2015/07/31(金) 19:13:51.36 ID:qB8zjiMb.net]
- 一応、壁に阻まれている設定なので、斜め移動は可能ですが、そのような経路は取らない様にしています。
家の隅を思い浮かべてもらえればいいかと思います。
- 746 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 22:14:18.76 ID:pNhxtvtu.net]
- てきとーだけど、
時間が掛かる方はスタート位置から全方向に探索し始めるけど、
もう一方は限定されてるから、その辺の違い？
- 747 名前：デフォルトの名無しさん mailto:sage [2015/07/31(金) 22:43:26.98 ID:rVmFBF2u.net]
- 探索木の根元（付近）がよく茂ってるか否かか
- 748 名前：デフォルトの名無しさん mailto:sage [2015/08/01(土) 00:40:27.40 ID:hEjnOg+p.net]
- オープンリストとか見られるようにしたらどう探索してるか一瞬でわかるよね
- 749 名前：デフォルトの名無しさん mailto:sage [2015/08/02(日) 19:09:42.88 ID:vmnF+S0U.net]
- スタート位置からの経路が多いかどうかかなあ
もっと単純なマップから少しずつ複雑化して試してみたら？
□□□□□□□
□□□□□□□
Ａ□□□□□Ｂ
□□□□□□□
□□□□□□□
↓
□□□□□□□
□□□■□□□
Ａ□□■□□Ｂ
□□□■□□□
□□□□□□□
↓
□□□□□□□
□■■■□□□
Ａ□□■□□Ｂ
□■■■□□□
□□□□□□□
こんな感じで
- 750 名前：デフォルトの名無しさん [2015/08/03(月) 16:26:23.97 ID:JJqkNluJ.net]
- 遅くなってすみません。
オープンリストをみて見ると、探査時間が遅いほうが根元（付近）がよく茂っていました。
原因が判明してスッキリしました。ありがとうございます。
一応これでＡ＊の実装は終了しようと思います。最適化は時間かかるし、ほかのアルゴリズムも組んでみたいので。
>>749
一本道の迷路で試したところ、経路の大きさが9と探査のとき、時間が半端なくかかってしまいました。
多分複雑なマップはＡ＊には向いていないのかもしれません。
同じ経路探査として、こんなのを見つけたのですが、ゲームに使うとしたらこっちのほうが面白そう。
ttp://codezine.jp/article/detail/94
てか、
- 751 名前：デフォルトの名無しさん mailto:sage [2015/08/03(月) 19:33:29.19 ID:MJUDpxg+.net]
- 深さ優先・幅優先探索で、
キャッシュに乗りやすいなどの、
メモリ特性が異なるのかも
キャッシュ的には、直前に使ったアドレスを、
繰り返し使って、廃棄する方が、
使用メモリも少なくて、速いのだろう
- 752 名前：デフォルトの名無しさん mailto:sage [2015/08/03(月) 20:24:42.14 ID:t5WJQOuJ.net]
- A*は複雑な迷路より広くて何も無い方が苦手だと思うけど
- 753 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 02:23:14.81 ID:TrY1gttZ.net]
- 何も無かったら一直線にゴールに向かうだけでしょ。
- 754 名前：デフォルトの名無しさん mailto:age [2015/08/04(火) 05:58:48.09 ID:r3CWXwbp.net]
- 迷路ジェネレーター
jsdo.it/jagarikin/bNMK
- 755 名前：デフォルトの名無しさん mailto:sage [2015/08/04(火) 07:41:15.54 ID:Ryo/DS3S.net]
- どうやって一直線に向えるんだｗ
人間は目で見てゴールまでの経路を探索するからそれが分かるんだけどさ。
こういうアルゴリズムは、例えるなら一歩先しか見えない状態で、
進める全方向に枝葉を伸ばして探索していくから、
何も無いとパターンが増えて時間が掛かるんだよ。
ちなみに。ゲームで使われるてるし、カーナビとかグーグル地図のルートだとか、
ネットのサーバーまでのパケットが通る通信経路とかの探索で使われている。
|
 |
