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

摘要

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