状态空间搜索

扩展释义

状态空间搜索就是将问题求解过程表现为从初始状态到目标状态寻找这个路径的过程。通俗点说，两点之间求一线路，这两点是求解的开始和问题的结果，而这一线路不一定是直线，可以是曲折的。由于求解问题的过程中分枝有很多，主要是求解过程中求解条件的不确定性，不完备性造成的，使得求解的路径很多这就构成了一个图，我们说这个图就是状态空间。问题的求解实际上就是在这个图中找到一条路径可以从开始到结果。这个寻找的过程就是状态空间搜索。 常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。