通过八数码问题比较搜索算法的性能

Performance comparison of search algorithms based on eight puzzle problem

搜索算法的核心在于搜索策略的制定。一般的搜索算法采用无信息指导的搜索策略,如深度优先搜索(DFS)和宽度优先搜索(BFS),还有一些搜索算法采用了启发式信息指导的搜索策略,如A*算法。不同的搜索策略会使得搜索算法的性能有很大的差异。使用以上3种搜索算法实现八数码问题的求解,分析和比较三者所表现出来的性能,同时指出3种搜索算法的特点和应用范围,最后给出分析结论以指导开发和使用更加高效的搜索策略。

The essential ofsearch algorithms is the establishment ofsearch strategies. Traditional search algorithms use strategies without information guidance, such as the depth-first search （DFS） and the breadth-first search （BFS）. Modem search algorithms use strategies with the guidance of information, which are called heuristic search algorithms, e.g. the A＊ algorithm, different search strategies will make the performance of the algorithms varies considerably. With the using of DFS, BFS and A^＊ algorithm to solve the eight puzzle problem, the performance of these algorithms is analyzed, and simultaneously indicates the feature of them, while at last show the analytic conclusion on the purpose of giving the direction to develop and use more efficient search strategies.