基于八数码游戏的两种搜索策略比较

Comparison of Two Search Strategies Based on Sudoku Game

利用状态空间法描述八数码问题,将其抽象成为一个从起始状态搜索到达目标状态的路径的问题,并在Visual C++6.0环境下,用C++语言实现了其盲目搜索和启发式搜索算法。其中,盲目搜索采用的是宽度搜索和深度搜索,启发式搜索策略采用的是有序搜索。通过比较两种搜索策略的时间复杂度和空间复杂度,在搜索步骤较多的情况下,启发式搜索具有明显的优势,并在此结论的基础上分析了启发式搜索具有优势的原因。

This paper uses state-space method to describe Sudoku problem which is abstracted as a search path problem from it＇s initial state to it＇s target state . In Visual C＋＋ 6.0 environment, the blind search and heuristic search algorithms are realized using C＋＋ language. The blind search adopts the width search strategy and the depth search strategy, the heuristic search strategy adopts order search strategy. By comparing time complexity and space complexity of the two kinds of search strategies, in the complex case, heuristic search has obvious advantage. Also, this paper analyzes the sources of advantages based on the conclusion.