N2-1パズルのスケールダウン解法

飯田　栄治  國藤　進  下平　博  木村　正行  

誌名
電子情報通信学会論文誌 D   Vol.J81-D1   No.6   pp.604-614
発行日: 1998/06/25
Online ISSN: 
DOI: 
Print ISSN: 0915-1915
論文種別: 特集論文 (計算量理論とアルゴリズム論文小特集)
専門分野: 
キーワード: 
15パズル,  24パズル,  N2-1パズル,  実時間探索,  問題解決,  

本文: PDF(684.8KB)>>
論文を購入



あらまし: 
N2-1パズルの最適解を求める問題は，探索木を作り最小長さの解を発見する問題である．この問題クラスは，NP完全に属するので，高性能の計算機を用いても容易に解を求めることができない．我々は，従来の方式とは全く異なる準最適解を得るための解法を提案する．我々の方式の特徴は，探索に頼るのではなく，パズルを1サイズ小さいパズルに置き換えていく過程を機械的に繰り返すことにある．この利点としては，探索木の生成を必要としないので，使用するメモリと計算時間が飛躍的に節約できることである．結論として，我々の方式が，N2-1パズルに対し多項式時間で準最適解を求めることができることを示すと共に，近年，注目されている実時間探索(一定の深さの探索を繰り返しながら，目標とする状態へ向けて探索していく方法)と比較を行い，そのような探索アルゴリズム等の性能評価に関して良い比較材料を提供できる可能性があることを示す．