/ プログラム/ 発表一覧/ 著者一覧企業展示一覧/ jsai2014ホーム /

4L1-1 ギャップ集合を用いた箱入り娘型スライディングブロックパズルの最適解の探索

*セッションの無断動画配信はご遠慮下さい。

Tweet #jsai2014 このエントリーをはてなブックマークに追加

05月15日(Thu) 09:00〜10:40 L会場( 和室-ひめぎんホール別館 第16会議室)
4L1 「ゲーム・エンターテイメント」

演題番号4L1-1
題目ギャップ集合を用いた箱入り娘型スライディングブロックパズルの最適解の探索
著者加藤 貴之(名城大学理工学研究科情報工学専攻)
山本 修身(名城大学理工学部情報工学科)
時間05月15日(Thu) 09:00〜09:20
概要箱入り娘型パズルは,複数の形状のコマを持ち,特定のコマを特定の位置に移動させるスライド式パズルであり,サイズが4x5に固定されたパズルの一般化である.このパズルの最適解を得るためにパターンデータベース(PDB)を構築し,そのギャップ集合(GS)を作成した.サイズ6x7のランダムに生成されたパズルについて幅優先探索と比べてPDBにより約1000倍程度,さらにGSにより2倍程度高速化することができた.
論文PDFファイル