著者

小田原 大 金子 知適 川合 慧

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告ゲーム情報学(GI) (ISSN:09196072)

巻号頁・発行日

vol.2004, no.64, pp.33-40, 2004-06-18

---

コンピュータパズルの倉庫番のソルバにおける課題は、手詰りの局面を効率良く検出することであり、特に袋小路の判定は難しい問題として知られている。既存の手法では判定に再帰的な探索を必要とするため、判定の効率が悪い。本稿では、袋小路を含めた「手詰り」状態の一般的な判定方法を提案し、それを探索に組合せることを提案する。具体的には問題を区域に分割し、ユニットと呼ばれる各区域の状態の組合せによって効率的に手詰りの状態を判定する。実際に倉庫番の問題に適用したところ、既存の手法では判定が難しい局面に対しても手詰りと判定することに成功した。A new method of detecting deadlock states is proposed. We define unit as a part of a map, and decompose a map into units. Each unit has gateways. The keeper can enter the unit through some gateways depending on status of other areas. We judge whether the entire state is a deadlock or not by using combination of local status of units. As a result, we could express a lot of deadlocks and showed ways of applying it to effective search.