カテゴリ:解説( 4 )
袋小路の研究
非固定タイプは判定が困難です。代表的なもので、袋小路があります。

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

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

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

世間でも袋小路の研究はまだまだ進んでおらず、これから研究を始める方にはいい題材だと思います。
[PR]
by sokoban | 2004-11-22 00:06 | 解説
凡例
キャラクタの意味を示しておきます。

荷物・・・・・・・日
ゴール・・・・・・十
番人(人)・・・・大
壁・・・・・・・・■
スペース・・・・・-
ゴールと荷物・・・田
番人と荷物・・・・木

以上は、基本キャラです。今後、説明用の専用キャラが出てきますが、それは後日。
[PR]
by sokoban | 2004-11-14 00:40 | 解説
死に手の分類
死に手の例はまだまだありますが、ちょっと休憩。

種類をいくつか示しました。実は、このように単純に分類できるわけではありません。荷物がひとつか複数か、ゴールが関係するかしないか、人の位置が関係するかしないか・・・など、いろんな切り口があります。

荷物がひとつで成立する死に手は、チェックが簡単です。その荷物だけを押してみて、ゴールに到達できないことを確認するだけです。

荷物が複数で成立する死に手のチェックが困難なのです。いろんな工夫が必要になってきます。そのへんについては順次解説していきます。
[PR]
by sokoban | 2004-11-13 21:43 | 解説
はじめ
AI(人工知能)の研究ページです。
倉庫番を題材にし、ソルバーを中心として進めていきます。
[PR]
by sokoban | 2004-11-13 00:32 | 解説