迷路を隣接行列で攻略(part1)
更新空いたなあ……(´・ω・)
まあいいや。のんびりいきまっせ。
以前(ブログには書いてねえけど)迷路を解くプログラムを書いたことがあるんですが。深さ優先探索だったしそんなに速度も出ない。
じゃあ幅優先探索で……
でもいいんだけど、ちょっと今日は行列使って解いてみようかと思います。数学カテ全く更新してないし。
さて、例えば上のような迷路を考えたときに、
これを数理的に扱う為には、
「どのブロックからどのブロックへ動けるのか」
を
0:動ける
1:動けない(壁がある)
でモデル化すればいいわけです。
つまりブロックiからブロックjへ動けるかどうかを
で表せばいいんです。
隣接行列とは、上のように各成分を定めた行列のことです。
これを使って迷路解いてみようぜ、ってことです。
速さとかは関係なし。面白そうだからやるだけです。
ちなみに上の迷路の隣接行列は
となる。カオス。
で、「解く」ということについてですが。
普通、道順を示すことを「解く」というわけですが、今回はまだ道順を表示させる手続きをしっかり考えていません。(できるとは思うけど)
で、じゃあ何を考えるのかというと、最低で何回の移動(何手で)でゴールまで辿りつけるのかを求めます。
次の事実を利用します
は
iからjまでn手で行く道の数を示す。
証明は楽です。
n=1の場合は定義から明らか。
n-1まで成り立つと仮定すると、
(n手でiからjまでたどり着く道の数)=(n-1手でiからkまでたどり着く道の数)×(1手でkからjまでたどり着く道の数)
なので、仮定を使えば
(n手でiからjまでたどり着く道の数)=
=
以上。終わり。
さて、スタートがi、ゴールがjなら、となる最小のnを求めりゃいいですね。
でも、まあこれは数学の話だけども最終的にはプログラムで解きたいから、行列の掛け算を真面目にやるのは勘弁願いたいわけです。普通に考えてn=(ブロックの数)としてn×n行列の掛け算ですので、計算量はです。
なので、いくつか計算をサボる為の補題を示します。
まず、隣接行列が0と1しか成分に持ってないので、成分は掛け算しなくていいでしょう。
隣接行列の成分が1かどうかがわかればそれでいい。
さらに一回の移動で一マス進むので、移動回数が奇数か偶数かで
行けるマスが半々なはず。
奇数回目の移動後は奇数番目のセルにいるので
次の移動(偶数回目)では奇数番目のマスからしか移動してきません。
なので、奇数番目のマスからの移動のみ計算すればいいってことです。
偶数回目の時も同様。
(nは「移動回数+1」であることに注意。)
また、もっと単純に「奇(偶)数回目の移動後は奇(偶)数番目のセルにいる」より、
なので、行列の約半分が0ということも言えます。
7/28追記:上の二つは誤りですね^^;行けるマスが半々とかいう議論はあってますが、セル番号での判定はできませんでした。失礼。
しかも、「iからjへ行く道筋の数」=「jからiへ行く道筋の数」なので、
は対称行列。
です。当然。
さて。
これで、結構計算が不要になります。
詳しい証明は省きますが、補題一つにつき計算を約半分づつに減らせており、
大体8分の1で済みます。
以上で数学的な側面の証明は終わり。
隣接行列をジョルダン標準形にでも直せればもっと楽なんだろうけど、
残念ながら固有値を求めるアルゴリズムがわからず断念。
これらをプログラミング(Javaで)する方法は考えてはあるんですが、
なにぶん大学生なもんで試験が……
ちょっと今は書いてる暇ないです。
では今回はこれで。
実質初めて数学カテ書いたしまともな記述になってるかワカンネ。
(´・ω・)ノシ