俯瞰可能迷路の代数的構造（Semi-Ring）による数学的モデル化と成功経路導出アルゴリズム

摘要

伝統的な俯瞰可能迷路は，階層的選択問題の代表的なものであるが，これまでのところ数学的モデル化の試みはほとんどされず，深さ優先（幅優先）探索問題等の例題として取り上げられる程度にとどまっていた．本研究では，この迷路問題に対し，理論的アプローチの可能性を追求するため，数学的定式化を試み，分岐点の局所的連結状況の表現としてエッジ行列を提案する．分岐点の連結を表現するものとして，一般には無向グラフが考えられるが，この隣接行列では，各分岐点での選択の指針が得られない．エッジ行列による表現では，各分岐点での選択動作を文字列の連鎖を内演算とする半環（Semi-Ring）によりモデル化でき，迷路の成功経路をこの演算から導き出すことが可能となる．本論文は，この数学的モデル化と成功経路導出アルゴリズム，及び，そのプログラムの実行結果を報告したものである．