N数码问题直接解及优化研究

对于N数码问题,一般解法都使用搜索算法,但是由于其搜索空间巨大,虽然已经应用并改进了很多的搜索方法1-4],求解的效率一般仍然很低。对于24数码问题,一般搜索方法通常至少需要十分钟以上5]。更高阶数码搜索时间会呈指数增加,而且往往得不到解。提出N数码问题有解性判定并对有解的问题给出一种直接解法。解法能在很短时间内给出N数码的一个解,不过这个解通常不是最优解。然后再使用搜索算法,以直接解来改变搜索方向,使搜索算法更快收敛于一个较优解。最后通过实验验证算法的有效性。

ON DIRECT SOLUTION OF N-PUZZLE PROBLEM AND ITS OPTIMIZATION

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 more5].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 me...