書誌事項
- タイトル別名
-
- Fast Search for Optimal Solutions of the Fifteen Puzzle Using Gap Sets
抄録
The fifteen puzzle is a sliding puzzle which has fifteen pieces on which numbers from 1 to 15 are printed. Using the IDA* algorithm with an admissible evaluation function, we can obtain an optimal solution of the puzzle. The performance of the algorithm depends on the evaluation function. The most simple evaluation function is the Manhattan evaluation function, whose value is the sum of the Manhattan distances from the positions of the corresponding pieces in the goal configuration. In this paper, we propose an evaluation function whose values are greater than or equal to that of the Manhattan evaluation function. Our evaluation function refers an approximated database of the gap-2n set. The database is computed beforehand like pattern databases, but it is completely different from pattern databases. The belongingness of a configuration of pieces to the set has to be checked by the database. Using an evaluation function based on the gap-8 set, we were able to reduce the number of search nodes to about 2.5×10-4 times in average with the IDA* algorithm compared with the Manhattan evaluation function. We also show that combining an evaluation function by gap-8 set and an evaluation function by additive pattern databases of disjoint seven and eight pieces, we were able to reduce the number of search nodes by about 53 compared with the evaluation function only by the additive pattern databases.
収録刊行物
-
- 人工知能学会論文誌
-
人工知能学会論文誌 26 (2), 419-426, 2011
一般社団法人 人工知能学会
- Tweet
詳細情報 詳細情報について
-
- CRID
- 1390282680085309952
-
- NII論文ID
- 130000455472
-
- ISSN
- 13468030
- 13460714
-
- 本文言語コード
- ja
-
- データソース種別
-
- JaLC
- Crossref
- CiNii Articles
-
- 抄録ライセンスフラグ
- 使用不可