Art

J-GLOBAL ID：201102259104562730   Reference number：11A0527717

Fast Search for Optimal Solutions of the Fifteen Puzzle Using Gap Sets

ギャップ集合を用いた15パズルの最適解探索の高速化

Author (2)： YAMAMOTO OSAMI (名城大学 理工学部 情報工学) ,  SATONE HIROSHI (名城大学 理工学研究科 情報工学専攻)
Material： 人工知能学会論文誌(Web)  (TJSAI (Web))
Volume： 26  Issue： 2  Page： 419-426 (J-STAGE)  Publication year： 2011 
JST Material Number： U0128A  ISSN： 1346-8030  Document type： Article
Article type： 原著論文  Country of issue： Japan (JPN)  Language： JAPANESE (JA)

Thesaurus term： problem ,  solution(mathematics) ,  *search problem ,  *optimization method ,  set ,  heuristics ,  evaluation function ,  speedup ,  distance ,  search theory ,  algorithm
Semi thesaurus term： 15パズル ,  Manhattan距離 ,  ギャップ集合 ,  heuristics ,  optimal algorithm ,  optimal solution ,  depth-first search

JST classification (2)： Artificial intelligence  (JE08000Z) ,  Other methods of operations research  (KA03070E)

Reference (8)：

• [Felner 04a] Felner, A., Korf, R. E., and Hannan, S.: Additive pattern database heuristics, Journal of Artificial Intelligence Research, Vol. 22, No. 1, pp. 279-318 (2004)
• [Felner 04b] Felner, A., Meshulam, R., Holte, R., and Kolf, R.: Compressing pattern databases, in AAAI-04, pp. 638-643 (2004)
• [Hannson 92] Hannson, O., Mayer, A., and Yung, M.: Criticizing solutions to relaxed models yields powerful admissible heuristics, Information Sciences, Vol. 63, No. 3, pp. 207-227 (1992)
• [Hart 68] Hart, P. E., Nilsson, N. J., and Raphael, B.: A formal basis for the heuristic determination of minimum cost paths, IEEE Transactions on Systems Science and Cybernetics, Vol. 4, No. 2, pp. 100-107 (1968)
• [Johnson 79] Johnson, W. W. and Story, W. E.: Notes on the ``15'' puzzle, American Journal of Mathematics, Vol. 2, No. 4, pp. 397-404 (1879)

Terms in the title (6)： ギャップ ,  集合 ,  パズル ,  最適解 ,  探索 ,  高速化