文献

J-GLOBAL ID：201102259104562730   整理番号：11A0527717

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

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

著者 (2件)： 山本修身 (名城大学 理工学部 情報工学) ,  佐藤根寛 (名城大学 理工学研究科 情報工学専攻)
資料名： 人工知能学会論文誌(Web)  (TJSAI (Web))
巻： 26  号： 2  ページ： 419-426 (J-STAGE)  発行年： 2011年 
JST資料番号： U0128A  ISSN： 1346-8030  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 15パズルでは4×4に仕切られた枠に1~15の番号が書かれたコマが置かれ,一箇所ある空所に隣り合ったコマをずらして位置を変える操作を繰り返し,ゴール状態の配置に変化させる。本論文では,発見的探索手法を用いて与えられた配置からゴール状態まで遷移させるコマの動きを探索する場合に,最短手順数を超えないなるべく大きな値をとる評価関数によって15パズルの最適解探索の高速化を図った。まず,最短手順数の下界は0を含む偶数をマンハッタン距離関数に足し加えれば得られることを示した。次に,任意の正の整数nとするとき,ゴール配置までの最短手順数とマンハッタン距離関数の差が高々2nの配置をすべて集めたギャップ2n集合G_2nを深さ優先探索を用いて計算し,G₀,G₂,...,G_2nを用いて許容的な評価関数を実現する。一方,G₀の要素数は9千万弱であり,正確なギャップ集合を列挙することは不可能なのでギャップ8集合までを近似的に求めることで評価関数を構成した。ランダムに生成した300種類の配置のゴール状態までの最小手順をIDA^*アルゴリズムで求めたところ,マンハッタン距離関数を用いた場合の4000分の1程度の探索ノード数に削減でき,パターンデータベースによる方法との併用可能性が確かめられた。

シソーラス用語： 問題 ,  解 ,  *探索問題 ,  *最適化手法 ,  集合 ,  発見的方法 ,  評価関数 ,  高速化 ,  距離 ,  探索理論 ,  アルゴリズム
準シソーラス用語： 15パズル ,  Manhattan距離 ,  ギャップ集合 ,  ヒューリスティクス ,  最適アルゴリズム ,  最適解 ,  深さ優先探索

分類 (2件)： 人工知能  (JE08000Z) ,  その他のオペレーションズリサーチの手法  (KA03070E)

引用文献 (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)

タイトルに関連する用語 (6件)： ギャップ ,  集合 ,  パズル ,  最適解 ,  探索 ,  高速化