ここのアルゴリズムを考える †
ここの穴掘り法について考えていきましょう。
- 速い！でも102行ここには敵いません；； -- Charlotte 2005-05-28 11:36:15 (土) New!
- 現在回答待ち。そしてソースにフルコメント化。＠＠； -- kz3 2005-05-28 14:14:45 (土)
- おお！ で、この雑談リンクがないです；； -- Charlotte 2005-05-28 14:17:30 (土)
- あ、迷路のコメントからリンク貼ってますよ^^; -- kz3 2005-05-28 14:18:36 (土)
- あっ。貼ってました。。。解決後に雑談に移動します。 -- Charlotte 2005-05-28 14:20:42 (土)
- 雑談はpukiwiki公式のようにしたいと考えております。 -- Charlotte 2005-05-28 14:24:11 (土)
- ページ構成の事と思ってよろしいですか？どのようになさってもＯＫです＾＾--kz3 2005-05-28 14:30:34 (土)
- どうもです。 -- Charlotte 2005-05-28 14:31:26 (土)
- 回答は夜になると、おもわれ。 -- Charlotte 2005-05-28 14:35:50 (土)
- 全てを完全に理解するのは、いつになるか分かりませぬ･･･；； -- kz3 2005-05-28 14:38:08 (土)
- だいたいならわかるような・・・。う〜ｍ -- Charlotte 2005-05-28 14:40:07 (土)
- ようするに、ただログとって戻るからすごい速いわけですよね。 -- Charlotte 2005-05-28 14:46:25 (土)
- そうなんですよ、僕だって一応ログは取ってるんですが、ログ取りの方法が違うのかな･･･ -- kz3 2005-05-28 14:49:54 (土)
- あと僕はソース見やすくするために2次元配列使ってるから遅いのかも･･･ -- kz3 2005-05-28 14:54:49 (土)
- ふ、分かってきた＾＾； -- kz3 2005-05-28 14:57:19 (土)
- 進むたびにログをとってる模様 -- Charlotte 2005-05-28 15:04:46 (土)
- b,bb,hantメンバ（構造体じゃないけど）の意味完全理解b -- kz3 2005-05-28 15:06:56 (土)
- hantは４方向に進むためかな？ -- Charlotte 2005-05-28 15:19:43 (土)
- その通り！ -- kz3 2005-05-28 15:21:10 (土)
- backはスタックですね。progがスタックポインタで進むとどんどん上書き。 -- kz3 2005-05-28 15:26:54 (土)
- うむうｍ、これ思いつくのはすごいですねw -- Charlotte 2005-05-28 15:28:18 (土)
- って変数メンバ＝ソース ∴ソース無断公開かな･･･；； -- kz3 2005-05-28 15:28:27 (土)
- 僕のログ取りはマップに直に記録していますよね。 -- kz3 2005-05-28 15:29:35 (土)
- 概要はつかめた。ひとまず、僕のソースも2次元配列→1次元配列に直してみます -- kz3 2005-05-28 15:33:02 (土)
- 変数メンバ=ソース う〜んそこら辺微妙ですよね。 -- Charlotte 2005-05-28 15:43:35 (土)
- データ構造変更完了。正常動作確認。早くなったかは･･･疑問；； -- kz3 2005-05-28 16:13:48 (土)
- 変更版はどこにUPしたらいいでしょう？ -- kz3 2005-05-28 16:17:49 (土)
- ver.1とかつけてさいUPまたは上書き（消さないといけない）でお願いします。 -- Charlotte 2005-05-28 16:21:47 (土)
- 棒倒し法の要領でやってみると速いかもしれない -- Charlotte 2005-05-28 16:50:41 (土)
- 戻りすぎのせいで完成に満たないようです；； -- Charlotte 2005-05-28 16:52:53 (土)
- 戻りすぎ！？バグですか！？デバッグだ･･･orz -- kz3 2005-05-28 16:56:01 (土)
- デバッグ完了しました！！ver2.1にします。バグとりなのでね＾＾ -- kz3 2005-05-28 18:25:50 (土)
- 偶数座標はぜったいに掘らないといけないから･･･。 -- Charlotte 2005-05-28 16:55:22 (土)
- 迷路如きがこんなに難しいとは。こうなったら最短ソースを目指すw -- Charlotte 2005-05-28 17:00:30 (土)
- ここの管理人さんから許可が出たので、「解読」の方にレスをつけていきます＾＾ -- kz3 2005-05-29 08:44:00 (日)
- メンバの名前が微妙に変わってる；；--kz3 &now
- ログ取りの仕方は違えど、戻って行ける方向を選択して行ければ進む、全く行けなければ戻るの繰り返しですね。 -- kz3 2005-05-28 16:35:24 (土)
- どこで差が出てくるのかという事も分かりました。 -- kz3 2005-05-28 16:35:45 (土)
- 自分がいうのもどうかと思いますが、戻りすぎている所があるような。。 -- Charlotte
2005-05-28 16:42:25 (土)
えぇ！！？ではver3では戻った時に赤く塗ってみようかな！--kz3 2005-05-28 16:48:56 (土)- ver3（婆さん）だって、プッ--kz3 2005-05-28 16:48:56 (土)
- がは！！！--Charlotte
- ver2.11としました。--kz3 2005-05-28 19:16:55 (土)
- 計算量（仮）
進路方向を決定するのに、あちらは固定テーブルを参照するだけなので、多くてもループは４回。 これが全ルートだと、ループ回数は２３０４×４＝９２１６回。 対して僕は一旦進むと方向テーブルを再構築します。 再構築の際に4回ループします。 よって僕の場合、多くてループ２６０１回×４×４＝４１６１６回。
- ４倍違うんですね＾＾；
- ルートのかずが２３０４と２６０１で違うのは実はあちらはSize99で外周部分もメモリに含まれているので実質迷路を構成するのは48*48マップ。
- 対する僕はSize51で51*51マップ。外周部分は画面描画で表現しています。
- Size48でやってみようかな。＾＾；
- 結局、方向テーブルを固定か、再構築の為に４回ループするかで、完成までの時間に影響してきますね？ -- kz3 2005-05-28 18:43:54 (土)
- 解読した結果私のアルゴリズムと、revyさん（ ここの管理人さんでありソースの作者です）のアルゴリズムでどうしてここまで速度に差が出るのか、それは２つあることが分かりました。
- 進路決定の方法
- kz3 ：毎回乱数で進路を決める
- revyさん：固定テーブル
- 足跡の記録の仕方
- kz3 ：マップ（迷路を表現するデータ構造）に直接記録
- revyさん：足跡はスタックで管理
- えっと･･･この後どしよっか；；
- まずはrevyさんから。最新版meiro2_.asについて書いていきます。
revyさんの進路決定方法はhantという変数がポイントです。
（本来ならhantは"4!*4"の全96の要素をもっていなければならないのですが、めんどいので省略しました。）
meiro2_.asからの抜粋でした。ここで"96の要素"が本来必要という部分ですが･･･
これは私は64の間違えじゃないかなぁと思ったりしています^^;
撤回。96でした；；ごめんなさい、revyさん。 「何故96なのか、何が96なのか」はい。
４方向について進める方向をランダムで探しますがこれは１６２４通りあります。
これをrevyさんは固定テーブルとして４パターン作っています。１つのパターンの０〜３の４要素が移動量を表しています。ので･･･
1 2 3 4
hant.0 = -SIZE, -1, 1, SIZE ;方向テーブルの初期化 hant.4 = SIZE, -SIZE, -1, 1 hant.8 = 1, SIZE, -SIZE, -1 hant.12= -1, 1, SIZE, -SIZE
２４パターン×４要素＝９６要素
要素は配列のサイズということです。
これを手で書いていくのは大変ということで、４パターンにしたと言う訳ですね。
さてこのテーブルをどうやって使うのか。の部分で方向を決定していますが、進める方向が決まるのに、平均２回方向テーブルを参照するだけで決まります。
1 2 3 4 5 6
rnd dir, 4 ;”だいたいの”方向決定 go = 0 ;二マス先が壁かどうかの判定（後の行で使用） repeat 4 tdir = dir*4+cnt ;真の方向決定 hori2 = hant.tdir*2+hito ;2マス先 hori1 = hant.tdir+hito ;1マス先 - そしてkz3の方向決定アルゴリズムは･･･
私のはまるっきりランダムです。
ですが、まるっきりランダムでは一旦進めないと判断したルートを何度も選択してしまう可能性があります。
そこで私は重複しない乱数を使っています。
重複しない乱数はこちら?
私はwayという配列を方向決定テーブルとして使っています。
revyさん同様repeat 4で進めるルートが見つかればループを抜けるので平均２回方向テーブルを参照しますが、revyさんと違うのは進む度に方向テーブルを更新します。（＝固定ではない）
この方向テーブル更新にテーブル内をrevyさんより４回余計にループしています。
仮に迷路本体の大きさが５０の時を考えると･･･
1 2 3
;kz3付加コメント:SIZE-3/2が迷路本体なので50*50=2500 rest = (SIZE-3/2)*(SIZE-3/2) ;残りのマス dim back, rest ;ログrevyさん方向テーブル平均参照回数：2500*2=5000回 kz3方向テーブル平均参照回数：2500*6=15000回
３倍遅いんですね･･･。
revyさんの穴掘り法が早いのはまさにこれです。
これがあるからプログラム＝アルゴリズム＋データ構造と言われるのです。
revyさんも私も（２次元マップから１次元マップに変更しました）迷路を表現するデータ構造はそれぞれ
1 2 3 4 5 6 7 8 | |
やっている事は同じです。が、足跡の記録方法が大きく違います。
まずはrevyさんの足跡の記録方法から。
進むたびに１つ前の位置（の値）をスタックに積みます。
戻る時はスタックから１つ前の位置（の値）を取り出します。
上の９行目の人バックで人が元の位置に戻るのですが、スタック参照で一発で戻っていますね。
対するkz3はというと･･･
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 | |
進んだ場合、どの方向から来たのかをその場所に記録します。
戻る時はその場所に記録された来た方向をたどっていきます。
ここで、左に戻るためには４回比較しなければなりません･･･。
- 書きすぎました･･･；；すみません。ページ構成よろしくお願いしますm_ _m
- これだから簡潔にまとめる技術が必要なんですよね；； -- kz3 2005-05-29 12:28:47 (日)
- すごくいいと思いますけどね・・・うん -- Charlotte 2005-05-29 12:30:23 (日)
- こうなるともう雑談ではないので、迷路のほうに移動したいと思います。 -- Charlotte 2005-05-29 12:57:26 (日)
- ありがとうございますm_ _m -- kz3 2005-05-29 13:08:10 (日)
- これより速いのは無理なんですかね。 -- Charlotte 2005-05-29 13:10:43 (日)
- 早くする方法を思いつきました（ぇ -- kz3 2005-05-29 13:15:04 (日)
- ログをスタックにしてより早いものに書き換えてみます＾＾； -- kz3 2005-05-29 13:17:18 (日)
- 高速化は前途多難でした；； 簡単に可能なのは、=1と比較するところを&1とすることでしょうか･･･ -- kz3 2005-06-01 10:48:28 (水)
Last-modified: 2007-04-08 (日) 02:38:46 (2436d)