迷路問題を解く

　朝日新聞の土曜版のパズル欄に、迷路のパズルが載ることがあり、挑戦している。そのパズルをより単純化したモデルで示せば、下図のような構成となっている。

Ｓ

Ａ・	・Ｃ・ ・	・Ｂ・ ・	・Ｄ
Ｄ・	・  ・Ｅ・ ・	・ ・Ａ・ ・	・Ｆ
Ｆ・	・  ・Ｄ・	・  ・Ｂ・	・Ａ

　　　　　　　　　　　　　　　Ｇ

　問題は、左端のＳからスタートし、いずれかの経路を通って右端のゴールＧまで行くものである。ただし、３種類の記号しか通れない。道は上図の横棒または縦棒がある限り上下左右に進めるが、斜めには行けない。同じところを２回以上通るのも禁止である。

　実際のパズルは、記号群が７行８列の行列を構成しており、スタートは左端の７箇所のいずれかであり、ゴールは右端の７箇所のいずれかとされているので、スタートとゴールが決まっている問題より難度は高くなる。しかし、経路探索のスタート地点として７箇所を試行する問題となるので、基本的には、スタートとゴールが決まっている問題に帰着される。

　コンピュータを用いてこの迷路問題を解くことが可能である。行列Ｘ（ｉ，ｊ）（例えば、１?ｉ?７，１?ｊ?８）の各要素にその記号を設定する。また、ｋ，ｌ，ｓを要素とする構造データＹ（ｎ）［ｋ，ｌ，ｓ］（例えば、１?ｎ?２８）の領域を用意する。Ｙ（ｎ）は、探索された経路を構成する行列要素の履歴であり、（ｋ，ｌ）は行列要素の位置を示す（ｉ，ｊ）である。ｓは、その行列要素のステータスを示す４ビットの情報であり、隣接する左右上下の行列要素への進行可否を示す情報である。ビット１は探索済みまたは探索不可を示し、ビット０は探索可能な方向を示す。また、１次元の配列Ｚ（ｎ）の領域を用意する。各Ｚ（ｎ）は、各Ｙ（ｎ）に対応し、探索経路を構成する記号のシーケンスであり、仮に決めた３種類の記号のいずれかが格納される。

　プログラム・ロジックの概略は、次のようなものである。まずスタートとなる行の左端の行列要素Ｘ（ｉ，１）の値（記号）をＺ（１）に格納し、その位置情報をＹ（１）［ｉ，１，ｓ］に格納し、次のＸ（ｉ，２）に進む。Ｘ（ｉ，２）では、その位置情報をＹ（２）［ｉ，２，ｓ］に格納し、Ｘ（ｉ，２）の値をＺ（２）に格納し、ｓ情報をセットする。ｓ情報の左ビットを１、ｉ＝１なら上ビットを１にセットする。次にあらかじめ決められた方向（たとえば上方向）にある隣の行列要素Ｘ（ｉ，ｊ）に進む。この３番目の行列要素についても、Ｚ（３）にその行列要素の値を格納する。次に、３番目の行列要素の位置情報をＹ（３）［ｉ，ｊ，ｓ］に格納する。また許される進行方向の隣接する行列要素が登録した３種類の記号に含まれるか否か判定し、含まれない行列要素の方向ビットを１、２番目の行列要素の方向を示すｓ情報の方向ビットを１にセットし、許される進行方向の隣接する行列要素の方向を示す方向ビットを１にセットし、進行が許される４番目の行列要素の処理に進む。４番目以後の各行列要素の処理は、３番目の行列要素の処理と同様である。このようにして、最先端の行列要素の進行方向がなくなったら、経路履歴情報を逆にたどり、まだ探索していない方向をもつ行列要素が見つかったとき、その行列要素より先の経路履歴Ｙ（ｎ）［ｋ，ｌ，ｓ］の内容をすべて削除し、対応する記号の履歴Ｚ（ｎ）の内容をすべて削除し、見つかった行列要素から新たな探索方向へ探索を開始する。このようにして、探索開始してから２番目の行列要素から出発するすべての経路が試行されてもゴールに到着しないとき、経路履歴Ｙ（ｎ）［ｋ，ｌ，ｓ］と記号履歴Ｚ（ｎ）の内容をすべて削除し、他の行の左端の行列要素Ｘ（ｉ，１）から経路探索を繰り返す。

　上記のプログラミングは、非常に労力を要するので、行列の規模が７行８列程度であれば、直感的に試行錯誤をして正解を見つける方が早い。行列の規模がより大きくなったとき、プログラム・ロジックの変更はごく僅かで済むが、各行列要素Ｘ（ｉ，ｊ）に値を設定するための入力データ量は、行列の行数×列数の量となる。

　上記のような迷路問題は、数学の言葉で言えば、組合せ論の中の集合被覆問題というものに属するのであろう。スタートからゴールまでの正解となる経路が全体集合であり、ルールを満足する部分集合を正しい順序に配列して全体集合を被覆するという問題である。全体集合は、３種類の記号から構成されるが、上記問題では、どのような３種類かも隠されている上に、正解となる全体集合の部分集合でない関係のない部分集合も混在してパズル回答者を迷わすという趣向となっている。類似の問題として、全体集合が、Ａ－Ｂ－Ｃ－Ａ－Ｂ－Ｃ－・・・のように記号の順序性が決まっていて、Ｃ－Ｂ－Ａ，Ｃ－Ａ－Ｂ，・・・のように決まった順序性に反するような部分集合を迷路部分に混在させている問題もある。いずれにしても、人間もコンピュータも、試行錯誤により部分集合と部分集合をつなぎ合わせて正解の全体集合となるような経路を見つけ出さねばならない。

　元々の単純な迷路問題として、入口から出口まで正解となる経路と、この経路から枝分かれして行き止まりとなる複数の迷路を設けたものがある。この問題も、集合被覆問題であり、問題は、正解の経路を構成する複数の部分集合と、正しい経路から枝分かれした関係のない部分集合とが混在したものとみなすことができる。粘菌の小片をこのような迷路内にほぼ一様に多数置くとする。これら小片は伸展し、隣の小片と出会うと細胞融合して一体となる。こうして、粘菌が一様に迷路内の全面を占めるようになる。次に、入口と出口に餌を置く。粘菌は、餌に集まろうとするので、行き止まりのある迷路内の粘菌の量は少なくなっていき、迷路内で行き止まりになっている部分から撤退する。このように、粘菌は、容易に正しい経路を見つけて餌に到達することが知られている。粘菌は単細胞生物であるから、迷路一杯に広がった粘菌は、部分集合と部分集合をつなぎ合わせるという試行錯誤をすることなく、モノリシックに正しい経路の全体を把握するのだろうか。

　ところで、先ほどの行列タイプの迷路問題に戻り、なるべく試行錯誤をしないで効率的に正解の経路を見つける方法があるだろうか。行列の各行の方向に３種類の記号が４個以上なるべく多く連続している記号のシーケンスを見つけて、そのシーケンスを部分集合として閉曲線で囲む。次に、各部分集合をその中に含まれる３種類の記号ごとに分類して、タイプ１（Ｔ１），Ｔ２，．．．などのタイプ別識別子を付加する。このような行方向シーケンス群を行テンプレートと呼ぶことにしよう。列方向についても、同様のシーケンスを見つけ、各シーケンスを部分集合として閉曲線で囲み、タイプ別識別子を付加し、列テンプレートを作成する。次に、行テンプレートおよび列テンプレートの各々について、同一タイプのシーケンスが２個以上あるようなシーケンスに注目しよう。このような同一タイプの記号で構成され主軸となり得るシーケンスが少なくとも１組はあるであろう。次に、行テンプレートの各組の主軸シーケンスを試行錯誤的に列方向又は行方向の同一タイプの少なくとも１つの記号から成るシーケンスでつないで、スタートからゴールまで全体集合を構成できるか否か調べる。行テンプレートについてこのような試行が成功しなければ、列テンプレートの各組についても同様の試行を行う。もし行列の列数＞行数であれば、確率的にみて、行テンプレートが列テンプレートより優先する。行数＞列数であれば、その逆の優先順序となる。

　この方法は、ルールを満足するできるだけサイズの大きな部分集合を候補として抽出するものであり、組合せ論において「欲張りアルゴリズム」として知られている。この方法は、試してみる価値はあるが、必ずしも成功するとは限らないものと心得たい。