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

DOI Web Site Web Site 参考文献2件

書誌事項

タイトル別名
  • Construction of Pattern Databases for Solving Hakoiri-Musume Type Sliding-Block Puzzles and Evaluation of Their Efficiencies
  • ハコイリ ムスメガタ スライディングブロックパズル ノ タメ ノ パターンデータベース ノ コウチク ト ソノ セイノウ ヒョウカ

この論文をさがす

抄録

<p>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.</p>

収録刊行物

参考文献 (2)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ