最速経路導出アルゴリズムの骨格と乱択足立法

マイクロマウスにおいて2次走行の時間を短縮するためには最速経路導出アルゴリズムの効率化が必要である.  

なんか論文のアブストみたいですね.  今回はこの最速経路導出アルゴリズムについて考察してみたいと思います.  考察と言ってもまずは, 具体的にアルゴリズムの実装方法やアイデアを論じるわけではなくて, プログラムでいう抽象クラスとしてどんな形になるのかな？という考察です.  そして, 考察の後に今実装しようとしているアルゴリズムのアイデアを書いてみます.

まず, 最速経路を定義しておきましょう.  

• 最速経路とは迷路の壁情報と加速度, 最高速度, 各ターンにかかる時間を決めたときに, 考え得る全ての経路のうちマウスが最速タイムでゴールできる経路である.  

よく言われることですが, 加減速とターンがあるマイクロマウスにおいて, 最短経路 ≠ 最速経路なのです.  

じゃあ, 全ての経路をみたら最速経路出るんじゃね?　ってなりますが, マイコンの限られた計算資源と競技時間ではこれは不可能です.  そのため, 実際は

• 最速そうに思える経路を現実的な時間で出すアルゴリズム

を実装することになります.  足立法は上の要件を満たす代表的なアルゴリズムです.

上の定義で重要なのは現実的な時間という文言です.  また書いてませんが現実的メモリ量でという条件も隠れています.  つまり, 使っていい資源は

• メモリ資源（RAM 今のマイコンだとRAMは256kBだから200kBは使える）
• 時間資源 : CPUの計算速度で決まる (競技時間を考えると10秒から長くても1分くらい)

となります.

足立法は実際かなり優秀なアルゴリズムです.  特にいいところは迷路サイズを固定したときに実行時間の上限が評価できることです.  つまり, 固定された時間でまあまあいい経路を出すことができます.  さらに足立法はポテンシャルマップの重みづけのルールをいじると別のまあまあいい経路を出すこともできます.  

さて, 本題です.  単なる足立法だとなかなか最速経路は出せないことは周知の事実だと思います.  そこで, 足立法のようなアルゴリズムの後にさらに別のアルゴリズムで経路を探すことにしましょう.  足立法でまあまあいい経路が出せることは担保できているので, 続くアルゴリズムは10秒くらいで計算を打ち止めします.  

　　Alg1:　固定時間でまあまあいい経路を探すアルゴリズム 

       　　                          +

　　Alg2:　時間を消費してよりよい経路を探し続けるアルゴリズム

 Alg1は足立法をベースにポテンシャルマップの更新方法を変えたものを数通り用意すればいいと思います.  問題はAlg2にはどのようなアルゴリズムをもってくるかです.  経路の全数探索に近いものは幅優先探索を使っても深さ優先探索を使っても適切な枝刈りが必要です.  それに実装がどうしても複雑になりそう...(つくるのがメンドクサイ)

やっぱり, 実装やアイデアはシンプルな方がいいです.  そこでこんなアルゴリズムを実装してみようと思います.  

   ////アイデア////

足立法ベースでポテンシャルの更新に乱数を使用.

      普通の足立法

                        1

                      1 0 1  ← 周りのポテンシャルは+1(定数)で固定

                        1   

       乱数を使った足立法

                          2

                     4   0  3   ←周りのポテンシャルは乱数で決定

                          1  

//////////////////

乱数を使ってポテンシャルを更新する足立法を乱択足立法と呼ぶことにします.  乱択足立法一回あたりにかかる計算時間は疑似乱数の生成が高速ならば足立法とほとんど変わりません.  乱択足立法は呼ぶ毎に違う経路を出すと思われるので, 時間資源が許す限りこれを回します.  その中ででてきた最速経路を出力にします.

まだ, このアルゴリズムは構想しかしておらず実装はしていません.  なのでちゃんといい経路が出てくるかはわかりません.  難しそうなのは乱数でポテンシャルの更新をするときのさじ加減になるのではないでしょうか.  どんな塩梅で重みをランダム化するかがポイントだと思います.  また, ちょっと工夫すると遺伝的アルゴリズムにもできる気がします.(各マスでのポテンシャルの更新のしかたが遺伝子)

結構前に経路導出に乱数を使うってアイデアはあったのですが, いかんせん時間がなくてずっと妄想の域を脱していませんでした.  使いものになるかは微妙ですが結構簡単に作れて面白そうなのでやってみます.  探索問題に乱数を使うというアイデア自体は全く奇抜なものではありませんし, 良くある手法だと思います.  確率的アルゴリズムって結構面白いですよ.  (データ構造だとブルームフィルタとか, 素数判定だとミラーラビン判定法とか..., 乱択クイックソートとか有名?)  

To　doを書いておきます.

////作りたいものたちとTo do/////

1. ランダム迷路生成ソフト
2. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すと最速経路を出力するソフト
3. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すとまあまあ最適な経路を定数時間で出力するソフト
4. 迷路の壁情報と加速度,最高速度,各ターンにかかる時間を渡すと局所最適な経路を現実的な時間で出力するソフト

最終的には1.で作った迷路に対し2.と3. and 4.の結果を比較するのがやりたいことです.