迷路を隣接行列で攻略（part2）

実はpart2というほどの更新もない。
……が、前回の書き方がちょっと言葉足らずだったので追加。

前回のpart1（http://d.hatena.ne.jp/g940425/20100625/1277480570）で、「迷路を解く」ということについて、
「最低で何回の移動（何手で）でゴールまで辿りつけるのかを求める」こと、できれば「ゴールまでの道筋を出力する」ことだと定義しました。
で、その目的を達する為に、計算をサボるための計算法をいろいろ考えてたわけです。

でも、あの書き方だと、もうすこし楽に行ける……というか、実は行列の定義自体を

ｎ手で辿りつける：１
ｎ手で辿りつけない：０

として

つまり隣接行列だけでなくその冪乗もブール値となるようにできれば、メモリも省略できるし計算も速くすることができる。つまり、行列の積の定義をちょっと変えるわけです。

すると、上の定義を実現するような行列の乗算を定義できればいいが、そんなもの

と定義してやれば何のことはない。

さらに実際にプログラミングするときの話をすれば、論理和ならどこかでtrueが確認された時点でループを切ってもいい。

しかも、こうするとが1ならも必ず1なので、が0だったところだけ調べりゃいいから、さらに計算量は縮まるわけです。

このように、ブール値行列を使えば簡単に解くことができる。

で、それをわかった上で、もしコーディングするとしたら（勿論するつもりだが）俺は普通に隣接行列の「通常の」冪乗によって求める方法で行きたいと思っています。
だからまあ、「迷路を解く」の定義に「最短手順がいくつあるかを出力する」ことを加えとくべきかな。

まあそんなことだ。そもそも、この「迷路を解いてみよう」企画は隣接行列使いたいだけなので、あんまり迷路を解くことそのものに特化したプログラミングにするのもなんかなあと思うこともあったりなかったり。

……まあいいや。そんな感じのミニ更新。それじゃ（´Д`）ﾉｼ