摘要
对于N数码问题,一般解法都使用搜索算法,但是由于其搜索空间巨大,虽然已经应用并改进了很多的搜索方法[1-4],求解的效率一般仍然很低。对于24数码问题,一般搜索方法通常至少需要十分钟以上[5]。更高阶数码搜索时间会呈指数增加,而且往往得不到解。提出N数码问题有解性判定并对有解的问题给出一种直接解法。解法能在很短时间内给出N数码的一个解,不过这个解通常不是最优解。然后再使用搜索算法,以直接解来改变搜索方向,使搜索算法更快收敛于一个较优解。最后通过实验验证算法的有效性。
N-puzzle problem is usually solved by search method,but it has huge search space,though a lot of search methods have been employed and improved ,the solution efficiency is yet very low.For 24-puzzle,normal search methods typically require at least 10 minutes or more[5].Higher-order puzzle＇s search time will increase exponentially,but often cannot get solutions.This article proposes the solvability determination of N-puzzle problem first and then a direct solving method for solvable problems is given.This method almost immediately gives a solution to N-puzzle problem,however it is usually not the optimal one.The search method is used later together with direct solution for changing the search direct,let search method converges to a better solution faster.At last,the effectiveness of the method is proved through experiment.
出处
《计算机应用与软件》
CSCD
2010年第5期266-268,277,共4页
Computer Applications and Software
关键词
数码问题
有解性
直接解法
搜索算法
N-puzzle problem Solvability Direct solution Search method
