文献

J-GLOBAL ID：201702228290997580   整理番号：17A1366937

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

Construction of Pattern Databases for Solving Hakoiri-Musume Type Sliding-Block Puzzles and Evaluation of Their Efficiencies

著者 (2件)： 山本修身 (名城大学理工学部情報工学科) ,  加藤貴之 ((株) システムリサーチ)
資料名： 電気学会論文誌 C  (IEEJ Transactions on Electronics, Information and Systems)
巻： 137  号： 9  ページ： 1286-1295(J-STAGE)  発行年： 2017年 
JST資料番号： S0810A  ISSN： 0385-4221  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

抄録/ポイント： 本論文では,箱入り娘型スライディングブロックパズルを定義し,適当なパターンデータベースを用いる事により,IDA*探索アルゴリズムやA*探索アルゴリズムでこのパズルを解く為の許容的評価関数を構築し,パズルの最適解の計算効率について調査した。この評価関数をIDA*探索アルゴリズムやA*探索アルゴリズムに適用した結果,幅優先探索に比して100~10000倍程度の探索の高速化を実現した。また,いくつかのパターンデータベースについては,幅優先探索による探索やマンハッタン距離に基づく評価関数よりも高速に計算できた。

シソーラス用語： *モード ,  *ブロック ,  *娯楽 ,  *型 ,  *データベース ,  *性能評価 ,  アルゴリズム ,  評価関数 ,  解 ,  効率 ,  探索理論
準シソーラス用語： *スライディングモード ,  *パズル ,  *パターン ,  A*アルゴリズム ,  探索アルゴリズム ,  最適解 ,  計算効率 ,  幅優先探索

著者キーワード (10件)： 箱入り娘パズル ,  IDA^*探索アルゴリズム ,  A^*探索アルゴリズム ,  緩和問題 ,  パターンデータベース ,  Hakoiri-Musume puzzle ,  IDA^* search algorithm ,  A^* search algorithm ,  relaxation problem ,  pattern database

分類 (3件)： 検索技術  (AC06020S) ,  データベースシステム  (JD03030U) ,  その他の情報処理  (JE15050M)

引用文献 (15件)：

• (1) R. E. Korf and A. Felner: “Disjoint pattern database heuristics”, Artificial Intelligence, Vol. 134, No. 1, pp. 9-22 (2002)
• (2) R. E. Korf: “Depth-first iterative-deepening: An optimal admissible tree search”, Artificial Intelligence, Vol. 27, No. 1, pp. 97-109 (1985)
• (3) P. E. Hart, N. J. Nilsson, and B. Raphael: “A formal basis for the heuristic determination of minimum cost paths”, Systems Science and Cybernetics, IEEE Transactions on, Vol. 4, No. 2, pp. 100-107 (1968)
• (4) Wikipedia: Admissible heuristic-Wikipedia, The Free Encyclopedia (2017)
• (5) Wikipedia: Klotsuki-Wikipedia, The Free Encyclopedia (2014)

タイトルに関連する用語 (5件)： スライディングブロック ,  パズル ,  データベース ,  構築 ,  性能評価