袋小路の研究
非固定タイプは判定が困難です。代表的なもので、袋小路があります。

パターンマッチングやサブ探索などが考えられますが、多くを判定しようとすると、コストが膨大になります。

明治大論文でサブ探索が提案されています。一押ごとに閉空間の発生を調べ、それを回復できるかどうかを探索する、という方法です。実験結果を見ると、ある程度の成功を収めています。

もちろん完全にはチェックできません。サブ探索のバッファが足りなくなることもしばしばです。といっても当時のことですので、今のメモリ量では変わってくるかも知れません。

世間でも袋小路の研究はまだまだ進んでおらず、これから研究を始める方にはいい題材だと思います。
[PR]
by sokoban | 2004-11-22 00:06 | 解説


<< パターンマッチング 複数チェック >>