Divide and conquer で組み合わせ爆発に立ち向かえ Part 2

転送行列編:http://d.hatena.ne.jp/ita/20120915/p1 の続き

「おぬしらのアイディアはこうじゃな。真ん中のところの状態をi番目の状態に固定して、それで左と右で許される経路の数を数える。それをLi, RiとおけばΣLiRiが求める答え、と」
「じゃあ更に分割して三人で手分けしたらどうなるかの。」

真ん中を二箇所で分割して状態をiとjに固定、そこでLiとRj、それに真ん中で許される経路の数Mijを数え上げる。最終的な答えはΣLiMijRj となるわのう。で、これはな、ベクトルL、行列M、ベクトルRをかけたのと同じ式じゃ。簡単にこう書こう <L|M|R>。
(口調めんどうなんで以下普通)
もっと分割を増やすとどうなるか。

ここで重要なのはiとjではさまれた部分と、jとkではさまれた部分は条件が全く同じということ。なので図で書いた行列Mと行列Nは同じものを使える。最後の答えは<L|M^2|R>。
これを同様に繰り返せば、横にどんどん伸ばせる。一旦行列を計算してしまえば、それをどんどん掛けるだけで4x100でも4x1000でもすぐに計算できてしまう。これが転送行列のアイディア。
一番効率的なのは行列で表す領域の幅を一番狭くして、iとjが隣り合っているときの行列を使う事。4x4グリッドの場合、状態の数は30あるけど、この場合の行列を実際計算すると以下のようになる。

                                                             状態
1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S         
0 1 1 0 1 0 0 0 1 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S     U L 
0 1 1 1 1 1 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S   U   L 
0 0 1 1 1 1 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S   U L   
0 1 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 1 0 0 0 0 0 0 0 S U     L 
0 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U   L   
0 1 0 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 S U U L L 
0 0 0 0 1 1 0 1 1 0 0 0 0 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 S U L     
0 0 0 0 1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 S U L U L 
1 1 1 1 0 0 0 0 0 1 1 1 1 1 1 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0   S       
0 1 1 0 0 0 0 0 0 0 1 1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0   S   U L 
0 1 1 1 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0   S U   L 
0 0 1 1 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0   S U L   
1 1 0 0 0 0 0 0 0 1 1 0 0 1 1 1 1 1 0 0 1 1 0 0 0 0 0 0 1 0     S     
0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0     S U L 
1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 U L S     
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 U L S U L 
1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 0 0 1 0 1 0 1 0       S   
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 0   U L S   
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 0 1 0 1 0 1 0 U   L S   
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 0 1 0 1 0 U L   S   
1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 1 1 1 1 1 1 1 1 1 1 0 1 1         S 
1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 0 0 0 1 1 0 1 0 0 0 1     U L S 
1 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0   U   L S 
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 0 0 0 1 1 1 1 0 0 0   U L   S 
1 0 0 0 0 0 0 1 0 1 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 0 U     L S 
1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 1 1 0 1 0 U   L   S 
0 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 1 1 0 U U L L S 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 1 0 0 0 0 1 1 0 1 1 U L     S 
1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 1 0 0 0 1 U L U L S 

状態の数はグリッドが増えると、どんどん増えるので、行列を格納するメモリが途中で足らなくなる

グリッド 状態数 行列のメモリ
8 1353
9 3610
10 9713 94M
11 26324 692M
12 71799 5.1Gb
13 196938 39Gb
14 542895 294Gb
19 91695540 ?
20 258215664 ?

ちなみに9x9の場合の行列を画像にするとこんな感じ

もっと大きい場合はまっすぐに切らずに途中で曲がって切る、という若干トリッキーな手法を使えばメモリの問題は解消する。
http://arxiv.org/abs/cond-mat/0506341
20x20の場合はまだ計算例なし。計算量的に、19x19の場合の10倍まではいかないと思う。ちなみに19x19の場合は2005年に1000以上のプロセッサで並列計算が行われている。やってる人がいないだけで、いまなら更新は十分可能。