状态空间搜索策略教材.ppt

《状态空间搜索策略教材.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索空间解路径主要内容：状态空间的搜索问题5.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.1搜索的概念及种类搜索的概念：找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线搜索种类：“盲目搜索”，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。“启发式搜索”，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。搜索例子：回溯搜索算法BACKTRACK（DATA）DATA：当前状态。返回值：成功

2、：返回从当前状态到目标状态的路径（以规则表的形式表示）失败：返回FAIL。四皇后问题皇后问题在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。四皇后问题（续）综合数据库：DATA=L(表），L的元素属于{ij}，1≤i,j≤4。DATA非空，其表元素表示棋子所在的行和列规则集：if1≤i≤4且在i-1行上有一个皇后then在第ij位置放上皇后。搜索策略固定次序：R11,R12,R13,…,R21,R22,R44()()Q((1,1))()QQ((1,1))

3、((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)

4、(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(

5、3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))5.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.2.1状态空间图的一般搜索算法5.2.2宽度优先搜索策略5.2.3深度优先搜索策略5.2.4代价树的宽度优先搜索策略5.2.5代价树的深度优先搜索策略5.2盲目搜索策略5.2.1状态空间图的一般搜索算法状态空间表示法：用来表示问题及其搜索过程的一种方法。(P62)主要构成：（1）状态，描述问题求解过程中不同时刻状况的数据结构；（2）算符：使问题

6、由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解状态空间图：把状态空间的问题求解过程用图的形式表示出来。节点代表状态，弧代表算符5.2.1状态空间图的一般搜索算法几个概念：扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。已扩展节点：已经求出了其后继节点的节点。未扩展节点：尚未求出

7、后继节点的节点。OPEN表：存放未扩展的节点，记录当前节点及其父节点。CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）状态空间的一般搜索算法一般搜索算法的描述：建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中建立CLOSED表，且置为空表判断OPEN表是否为空表，若为空，则问题无解，退出选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是

8、沿着n到S0的路径得到。若不是转⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的