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以上のプロセッサで並列計算が行われている。やってる人がいないだけで、いまなら更新は十分可能。