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

(いきなり答え知りたい人はこちらを http://arxiv.org/abs/cond-mat/0506341)
ガキ「おねえさーん！だめだ！組み合わせ爆発に殺されてしまうよ！そうだ、僕たちが手伝うよ！」
お姉さん「それはありがたいわ。でもどう手分けすればいいかなぁ・・・。そうだ、じゃあこの4x4のマスを点線のところで分割して、お姉さんはその左側の経路をいろいろ書くから、ガキ君はそれぞれの絵で右側を補間する方法をいろいろ列挙していってくれる？」

「うん、わかったよ」
「さー左側をばんばん描くわよー。でもマスが減ったのはいいけど、若干トリッキーね。どんな経路が許されるのかな。途中で線が終わってるのはダメね。スタートから出た線が必ず点線を通過して右へ出ないといけない、と。あと別の繋がってない線があってもいいけど、これも途中で終わっちゃダメと。右から入ったら必ずまた右から出ること。あとループになっててもダメね。」

スタートに繋がった線（赤）が右に出る
右から入ったら必ずまた右から出る。
ループは禁止

「ガキ君、こんなのでもOK?」
「うん、補間できたよ」

「じゃあ２つ切れ端があってもOK?」
「大丈夫みたいだよ」

「よーし、だいたい分かった。どんどん描くぞー」
さらさらさら「はい、ガキ君、おねがい」さらさらさら「はい、ガキ君、おねがい」さらさらさら「はい、ガキ君、おねがい」・・・

「お姉さーん、面白いことに気がついたよ。さっきもらったこの二枚の絵だけど、左側の絵はちょっと違っても、右側でどうすれば補間できるかは全く同じなんだよ。」

「あら、ほんとだ。この緑でかこった点線のところが同じなら、左は関係ないってことね。じゃあ同じのをまとめてしまえば相当楽になるね」
「うん。お姉さんの方で、この緑のところに合うような左側のパターンをまず全部調べてその数だけ教えてよ。僕は右の方を補間する方法を数えるから。それを掛け算すれば、パターンの数が分かっちゃうよ！」
「よーし、かなり速くなりそうね。がんばるぞー」

〜〜〜
〜〜〜
「お姉さーん、ごめん。うまくいかないのがあった」

「左側の２つなんだけど、破線のところは同じでも、繋がり方が違ってるんだ。ある補間の方法は、上の方はOKなんだけど、下の方はループができちゃってダメだよ。」
「ふーむ、破線のところで線がどうなってるか以外に、どれとどれが繋がってるかの区別も必要なのね。こんなふうに区別してみましょうか」

「これで全部で何通りあるかちょっと数えてみようかな・・・」

「線が交差するのはダメだから、それを除くと３０通り。思ったより少ないわね。」
「じゃあこの３０通りについて、右と左を補間する方法を数えて掛けて、最後に全部足せば終わりだね！」

「ふぉっふぉっふぉ。おぬしら中々スジがよいの。特別に、ワシの秘奥義、「転送行列」を伝授しようかの。」
「あ、あなたは Lars Onsager 先生！」
「知っているのか雷電」
（つづく）

Lars Onsager
天才的閃きで固体物理の数々の難問を解決しノーベル物理学賞を受賞。業績は多岐に渡るが物理の物性系の院生にとっては二次元Isingモデルの厳密解が最初に接する業績であろう。転送行列を用いた彼のオリジナルの解は難解で万人が理解できるものではない。ある者は「めんどいなぁ。数値シミュレーションなら三次元もできるし見た目も面白いじゃん」と三次元の世界へ旅立ち、ある者は「二次元萌え〜！厳密解は俺の嫁！」と二次元へ旅立つという。　　民明書房刊『物理超人列伝』

注

元々の科学館の展示ではグラフ理論一般に適用可能なＺＤＤという手法が紹介されているようです。こちらで実際のコードが紹介されています。http://handasse.blogspot.com/2012/09/blog-post.html
一方、今回の例のような規則的な格子では転送行列という手法が適用可能で、より高速に計算できます。物理の世界では主に規則的な格子を扱うのでこれはポピュラーな手法です。また計算する場合は行列ベクトル積がホットスポットになるので１０００プロセッサでの並列計算でも１０００倍に近い高速化を達成できます。
情報系ならグラフ理論、物理の人は転送行列を詳しく勉強するのがいいかも

奥儀の書 "Self-avoiding walks crossing a square" http://arxiv.org/abs/cond-mat/0506341