探索の方法
階層的なデータ構造を表すのに下の図のようなTreeが使われます。Treeはnodeとedgeで構成され、特に起点となるnodeはrootと呼ばれ、あるnodeから別のnodeが生成される時には、上流のnodeはparent node、下流のnodeはchild nodeと呼ばれます。parent nodeからは0個以上のchild nodeが生成できますが、逆にchild nodeにはparent nodeがただ一つ存在します。
箱入娘で盤上のタイルをスライドしてできる状態の遷移はこのTreeで表すことができます。rootは盤面の初期状態で、そのrootをparent nodeとして生成されるchild nodeには、下の図のように初期状態からの最初に可能な1手で変化をした状態を対応させるわけです。
この方法で順にchild nodeを生成しますが、盤面の状態が同一のchild nodeは生成できないと考えます。というのは、そのnode以降の部分木が同じものになってしまうのでそれ以上探索する必要がないからです。その同一性の判定をする際には、タイルの形状のみに注目しすればよく、同じ形状の異なるタイルを区別する必要はありません。実際、重複を排除するようにすると、3段目のlevel2までedgeを伸ばしたときには下のようになることが分かります。
このようにnodeを伸ばしていき、level nで下の図の赤丸で囲ったように解が得られたとすると、Treeの中でそのnodeからparent nodeを緑の線のように辿れば、rootまでの経路が明らかになり、その経路の逆向きで解法の手順を得ることができます。
Treeの中でnodeを走査する方法には、横型探索(breadth-firsr search)と縦型探索(depth-first search)があります。横型探索は、下の図のように、あるlevelのnodeを左から右に走査し、それが終わるとその次のlevelのnodeを左から右に走査します。一方縦型探索は、解が見つかるまでchild nodeを順に作り、それ以上edgeを伸ばせないchild node が生成されたらそのparent nodeに戻って別のchild nodeを生成するという方法を繰り返して走査します。
あるnodeで解に到達したとき、そのlevelの深さが解法迄のステップ数になりますが、それが最小となるnode迄のルートを求めるのが目的なので、上から順番に走査する横型探索がよさそうです。横型探索をおこなうには、下図のようにnodeに探索する順に番号をつけて並べておくとわかりやすくなります。
以上の考察を元に、次にプログラミングのためのデータ構造を考えます。
