曲がった迷路その19 - 壁解放端の位置の決定

それほど大きな問題はない。どんどん片付けよう。

壁の解放端の位置決定のアルゴリズム

まえに書いたように、新しい壁を作るときは

1. 壁の長さLを確率分布に従って決める
2. 壁の連結端からLの位置のなかでもっともポテンシャルの値の小さいところを探す
3. その値が閾値より小さければ解放端をそこに置く
4. 閾値より大きければ壁の配置は失敗として連結端の位置を選び直すところに戻る

とする。

　ここで一番問題になるのはポテンシャルの値の谷を探すところである。半径Lの円周上でのポテンシャルの最小値の探索になる。ちろんその谷が、必ず最小値である（単なる極小値ではない）ことを保証する必要はない。

　ポテンシャルは2次元だけど円周上での探索なので実質的に1次元の最小化問題である。 ポテンシャルをV(x,y)とすると

という1変数関数f(t)の最小値を求めればいい、ということになる。この関数は連続かつなだらか（微分可能）で、2πを周期に持つ。今のうちに微係数を求めておくと、

となる。ここでvは円周にそった方向の単位ベクトルで

である。

今回の場合の典型的なf(t)の形は図-25のようなものだろう。

1次元の最小化のアルゴリズムは2次元やそれ以上に比べてずっと簡単なことはすぐわかる。

　1次元の最小化には黄金分割法やはさみうち法などがある。どちらも最小点を含む区間を縮めていって最小値を求める方法で、多次元の場合と違って探索の過程でよそへさまよい出てしまうことがないので簡単なアルゴリズムになっている。

　黄金分割法は1回の繰り返しで区間を0.618倍（〜2/(1+√5)）にする。はさみうち法は区間を半分にするが微係数を必要とする。

　はさみうち法はすぐ思いつくやりかただけど微係数の計算が重いわりには区間の縮小率は黄金分割法に比べればちょっとまし（1回に区間を半分にする）という程度なので、普通あまり使われない。

　はさみうち法に使うつもりで、こないだバイキュービック補間をした関数のグラディエントまで計算したけど、いずれにせよ現実的にはバイキュービック補間した関数のグラディエントの安定性には問題があって1次元最小化には向いていない。2次元以上の場合、どうしてもグラディエントの値が必要で、安定性に注意しながら使うということはある。

　とりあえず、使わないけどはさみうち法について簡単にさらってから、黄金分割法をまとめるつもりにしてる。