パターンデータベースを利用した箱入り娘型スライディングパズルの最適解の探索

この論文をさがす

抄録

箱入り娘型パズルは,複数の形状のコマを持ち,特定のコマを特定の位置に移動させることを目的とするスライディングパズルであり,サイズ4x5に固定されたパズルの一般化である.このパズルの最適解を効率的に得るためにいくつかのコマを分解し,2段階に分けて部分パターンへ写像することによりパターンデータベースを構築した.サイズ6x7のパズルについてこのパターンデータベースを用いることで幅優先探索と比べて計算時間を約1000倍程度高速化をすることができた.

収録刊行物

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ