Zenn
🌐

「お姉さん問題」を今更追ってみる

2024/05/27に公開
計算
tech

https://www.youtube.com/watch?v=Q4gTV4r0zRs&t=16s
2013年頃に話題になったこの動画をふと思い出していくつか気になることがあったので、その後をなんとなく調べてみたくなった。

そもそもこの動画で主題になっている問題の概要としては、(n+1)\times(n+1) の格子上で左上隅から右下隅へ同じ格子点を2度通らずに行くパターンがいくつ存在するか数えよう、ということになる。n \times n ではなく (n+1)\times(n+1) という書き方をしているのはちょっと違和感があるが、最も単純な1個の正方形の時を考えると分かりやすい。1\times1としたくなるが、pathを考えるうえでは 2\times2 の格子点が存在するからである。n\times n の正方形は見た感じの直感として数えやすいが、本質的にはたまたまそこにあるだけの「穴」で問題自体には何も関与していないのだ。

名前

さてこの問題を調査するうえで最初に必要になるのは「ちゃんとした名前」である。「おねえさん問題」で検索しても結局は動画の紹介blogしか見つからないし、海外の論文なんかが見つかることはありえないので。
で、いろいろ調査した結果「Self-avoiding walk problem」という呼び方があるっぽい。略称は SAW。他にももう少し上位概念っぽい「s-t 経路探索」とかがキーワードになるかもしれない。s-t の s と t は source と target。ちなみにどちらも一般的なグラフ上で定義できる問題なので、「正方形グリッドグラフにおける」「on a square grid graph」などがつく事がある。

気になること

その1: 今の世界記録

そして改めて「気になること」その1、11年経った今の計算記録を調べてみた。結論から言うとこの動画が話題になった2013年に計算された n=26 が今でも最大っぽい。出典はOEIS。

その2: 計算方法

「気になること」その2。計算方法について。これについては理解が不十分なのでちょいちょい想像したことをあたかも事実のように書いていたり、嘘を書いているかもしれないので、何かの参考にしたい人はできれば一次ソースに当たってほしい。

この問題に対する解法としては順番に探索する方法もあるとは思うが、歴史的なメインストリームに乗る手法に沿う方向だけ書いてみる。
大元の基本的考え方としては左上から各edgeについて「使う」「使わない」の2択を選択するBinary Decision Diagram (BDD) と呼ばれる形で幅優先探索を行い、途中分岐ができたり独立したpathがあったりするなど「ありえない状態」に対して枝刈りを行う。最後のedgeの採用/不採用を決めたあとに結局最後までちゃんと1本でつながっていればOKな状態としてカウントしていく。
ただこの基本のままでは時間的、空間的コストがデカすぎるのでちょいちょい工夫がされて記録が伸びている。

具体的に紹介する工夫の最初は Knuth 大先生が著書「The Art of Computer Programming」で紹介した……のかどうか未確認であるが頻繁に引用に出てくる Simpath algorithm だ。Simpath は問題の名前の1例にある Simple Path の略なので分かりやすい。
Simpath では基本的に格子点単位で幅優先探索を行い、edge を使う/使わないの分岐をする。その際に mate と呼ばれる配列で状態管理をしていて、探索している最前線にある格子点が

  • path の途中なのか
  • path の端点で、反対側がどれなのか
  • path に含まれていないのか

ということを保持している。この形で管理すると探索済みの領域が具体的にどのような状態になっているのかの情報を保持しなくていい上に複数の状態を纏めた形で処理できるので時間、空間の両面で大きな進歩を遂げたようだ。

また、ZDD (Zero-suppressed binary Decision Diagram) と言われるデータ構造で状態を大きく縮退させることに成功した。ZDDは元ネタの動画を作成した当時北海道大学の湊教授が開発したデータ構造で…という事を含めて解説がググれば多々出てくると思うので説明は省略。

問題の特性を利用した効率化

次はおねえさん問題の特性を生かした効率化を紹介する。
まず探索順序としては全体としては上から下、同じ行では左から右に探索ノードを進める。そうすると探索中のノードはほぼ横1列に n+1 個並ぶ(纏めて frontier と呼ぶ)ので、mate で管理する対象が増減しないので固定長配列で状態管理ができる。

さらに mate に記録する内容は path の反対の id とするのではなく (、)、*、o の4種類に限定しても同じだけの情報量を持つことができる。
ここで ( は path の反対側がより右側にある、) だと同様に左側にある状態、* (参考元論文では●)は少し面倒だけど、分岐させようとする edge に繋がっていて path の途中になっている状態、そして o はその他の状態である。
すると元々は 1-2 byte 使っていた mate の 1 要素が 2bit に圧縮できるので、IDを振るだけなら n\leq32 であれば 64bit のレジスタサイズで収まる。さらに * は frontier のうち分岐検討中の格子点という決まった 1 箇所にしかないので情報保持する必要がない外、残りの ( ) o もきっちり対応している必要があるので状態のパターン数がぐっと削減できる。ちなみに s に繋がっている path は ) で ( ) の対応からはズレる。

発展案

上記のような方法で frontier 状態には最小完全ハッシュを割り当てられる。ここで j 列目の格子点から右に伸びるかもしれないことを考えた時、探索済みのエリアがどうあっても(何行目の処理をしているかにかかわらず) 1 つの frontier の状態、つまり 1 つの ID からの遷移先 ID (高々2つ)は具体的に決まる。
この状態遷移を (N_n+N_{n-1})\times(N_n+N_{n-1}) の行列で考えてみる。ここで N_n は論文で定義されている frontier のパターン数だ。1 遷移の行列だけでは 1 行に高々 2 個の 1 があるだけの疎行列だが、これを j=\{0,1,2,\cdots,n\} と掛け合わせるとおそらく各要素はあまり大きくない密行列が出来上がることと思われる。これは1行分 frontier を進めた場合の状態数遷移なので、これを n 回かけると「おねえさん問題」の答えを得ることができる……と考えている。

その3: 応用先(ナンバーリンク)

ちょっと話題は逸れて Simpath などの応用先の話。ナンバーリンクの解答プログラムが作れるということなのでまだ調べる。

参考文献

Discussion