曲がった迷路その23 - 完成判断のアルゴリズム

思いもしない問題が隠れてるかもしれんけど、気分的にはあともうちょっとで実装に入れると言う感じ。

失敗回数の上限を設定する

K個の壁を作ったときαK回以上失敗したらそこで終わりにする。αは適当な定数。これは確実に終われるので停止条件としてはいい。

しかし、αが小さいと可能性のあるところも残して終わることになって、すかすかの迷路になるだろうし、大きいと探索にばかり時間を費やすことになる。失敗回数はひとつの目安だけど、これだけではいまいち。

ポテンシャルの低いところを探索する

これは確実だけど

• ポテンシャルを全面走査する必要がある
• ポテンシャルは壁を作るたびに変化するので、それを繰り返すことになる
• 低いところが見つかったとしても、そこに近い壁を探すという作業が必要になる

ということで壁を作るたびにこれをやっていたのでは話にならない。

しかしこっちは作業時間がポテンシャル関数の定義域の大きさだけで決まっていて、失敗回数による判断のようにあるときははやいけどあるときは時間がかかるというようなことはない。

二つを合成する

ということがとりあえずはいいだろう。つまり

1. 失敗回数がある回数Qを超えるまでランダムに壁を作り続ける
2. 超えたら、ポテンシャルの低いところを探して、その近傍に壁を作る
3. 低いところがなくなったら終わり

としよう。

そしてQは

とする。つまりポテンシャル探索の時間の方が、ひとつの壁をランダムに作る時間より短くなったら切り替えるということ。それぞれの時間は実測する。ただし、ポテンシャル探索の時間はその広さ（迷路の大きさ）に依存するので簡単な式を作って迷路の大きさを決めたときに値が決まるようにする。ポテンシャル探索は線形時間でできるだろうから

になる。ここでM×Nはスペックルパターンを作るときのFFTサイズ、δは壁の長さ分布の最尤値である。

ポテンシャル探索のアルゴリズム

こういう切り替えアルゴリズムを使うとすると、ポテンシャル探索に要する時間が短いと迷路が早く出来上がるということになる。もちろん全体の効率は壁をひとつ作る時間で決まるけど、終了判断のはやさはこっちで決まる。

ということで効率的なポテンシャル探索を考える。
今回使っているスペックルパターンのポテンシャルは

• なだらかで、格子点だけ走査しても大きな誤差はない
• 値は変化するが増える（高くなる）だけ

である。ということでポテンシャルは、もとの格子点のバイキュービック補間なので格子点の値の極小値の近くにある。

ということで停止アルゴリズムが失敗回数から切り替わったとき、一回ポテンシャルの格子点を走査して、閾値以下の格子点の位置を全部覚えておく。そして新しい壁はそこから距離βσ以下の既存の壁を探して、もしあればそこから始めることにする。βは1より大きい適当な定数でσは前計算した壁長さのレイリー分布のσ。閾値以下の格子点が複数あればそこからランダムに選ぶ。

そして新しい壁ができてポテンシャルの値が増えて閾値を超えれば候補から外す。候補がなくなれば終わり、ということになる。走査は1回でいいけど、毎回閾値を超えたかどうかを判断する必要がある。また、対象になった格子点だけでなくその近傍の値も変化している可能性があるので閾値チェックは候補全部に対して行う必要がある。さっきのQの値があまり小さいとこのやり方は効率が悪くなってしまうけど、失敗回数が多いと言うことは候補になる格子点の数も少ないと考えていいだろう。