箱入り娘型スライディングブロックパズルのためのパターンデータベースの構築とその性能評価

カテゴリ: 論文誌(論文単位)

グループ名: 【C】電子・情報・システム部門

発行日: 2017/09/01

タイトル(英語): Construction of Pattern Databases for Solving Hakoiri-Musume Type Sliding-Block Puzzles and Evaluation of Their Efficiencies

著者名: 山本　修身（名城大学理工学部情報工学科），加藤　貴之（(株) システムリサーチ）

著者名(英語): Osami Yamamoto (Meijo University, Faculty of Science and Technology, Department of Information Engineering), Takayuki Kato (System Research Co., Ltd.)

キーワード: 箱入り娘パズル，IDA*探索アルゴリズム，A*探索アルゴリズム，緩和問題，パターンデータベース　　Hakoiri-Musume puzzle，IDA* search algorithm，A* search algorithm，relaxation problem，pattern database

要約(英語): This paper describes pattern databases for solving Hakoiri-Musume type puzzles using the A* algorithm and the IDA* algorithm. Although the original Hakoiri-Musume puzzle is not very hard to solve even on a small PC, it is not easy to solve extended versions of the puzzle, particularly, to obtain the optimal solutions of the puzzles. The puzzles have multiple goal states and are completely different from the sliding puzzles whose all pieces are distinguished such as the fifteen puzzle. In this paper, we defined relaxation problems of the puzzles and constructed pattern databases of the problems. Using the evaluation functions derived from the databases, we were able to obtain the optimal solutions of the puzzle of size 6 × 7 from randomly generated initial patterns about 100 to 10,000 times faster than the ordinary breadth-first search algorithm. For some of our pattern databases, the sum of the construction time of the database and the search time using the database was less than the running time of the ordinary breadth-first search algorithm.

本誌: 電気学会論文誌C（電子・情報・システム部門誌） Vol.137 No.9 （2017） 特集：知能メカトロニクス分野と連携する知覚情報技術

本誌掲載ページ: 1286-1295 p

原稿種別: 論文／日本語

電子版へのリンク: https://www.jstage.jst.go.jp/article/ieejeiss/137/9/137_1286/_article/-char/ja/