第五章状态空间搜索策略

第五章状态空间搜索策略S0Sg问题全状态空间问题的搜索空间解路径•主要内容：状态空间的搜索问题5.1搜索的概念及种类5.2盲目搜索5.3启发式搜索5.1搜索的概念及种类搜索的概念：找到从初始事实到问题最终答案的一条推理路线，找到的这条路线是时间和空间复杂度最小的求解路线搜索种类：“盲目搜索”，即系统根据事先确定好的某种固定排序（依次或随机）调用规则。“启发式搜索”，即考虑问题领域可应用的知识，根据具体情况动态地确定规则的排序，优先调用较合适的规则使用。搜索例子：回溯搜索算法BACKTRACK（DATA）•DATA：当前状态。•返回值：–成功：返回从当前状态到目标状态的路径（以规则表的形式表示）•失败：返回FAIL。四皇后问题•皇后问题–在一个4*4的国际象棋棋盘上，一次一个地摆布四枚棋子，摆好后满足每行、每列和对角线上只允许出现一枚棋子，即棋子之间不许相互攻击。QQQQ四皇后问题（续）•综合数据库：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))((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)(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)(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）算符：使问题由一个状态变为另一个状态的操作。（3）状态空间：一个问题的全部状态及一切可用算符构成的集合。一般包括3部分（初始状态集合S，算符集合F，目标状态集合G）（4）问题的求解：从S出发经过一系列的算符运算，到达目标状态。由初始状态到目标状态所用算符的序列构成了问题的一个求解状态空间图：把状态空间的问题求解过程用图的形式表示出来。节点代表状态，弧代表算符5.2.1状态空间图的一般搜索算法几个概念：•扩展：用合适的算符对某个节点进行操作，生成一组后继节点，扩展过程就是求后继节点的过程。•已扩展节点：已经求出了其后继节点的节点。•未扩展节点：尚未求出后继节点的节点。•OPEN表：存放未扩展的节点，记录当前节点及其父节点。•CLOSED表：存放已扩展节点，记录编号、当前节点及其父节点。图2.26的节点（1，1）能生成两个后继节点（2，1）（3，1）状态空间的一般搜索算法一般搜索算法的描述：①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中②建立CLOSED表，且置为空表③判断OPEN表是否为空表，若为空，则问题无解，退出④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表中，将此节点记为节点n⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得到。若不是转⑥⑥扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中⑦对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点，设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。⑧按某一任意方式或某种策略重排OPEN表中节点的顺序⑨转③特例图的一些概念：（1）节点深度：根节点深度=0，其它节点深度=父节点深度+1（2）路径设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。（3）路径的消耗值一条路径的消耗值等于连接这条路径各节点间所有消耗值的总和。用C(ni,nj)表示从ni到nj的路径的消耗值。0123节点类型说明…...…...…...…...…...mkmjmln扩展点n，产生mk：没在OPEN和CLOSED表中出现过mj：在OPEN表中出现过ml：在CLOSED表中出现过S123645将要扩展节点6S126453修改4节点的返回指针S126453将要扩展节点1S12645修改2和4的返回指针5.2无信息图搜索过程——盲目搜索策略5.2.2宽度优先搜索5.2.3深度优先搜索5.2.4代价树的宽度优先5.2.5代价树的深度优先1、定义如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索(breadth-firstsearch)。2、特点这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。5.2.2宽度优先搜索策略3、宽度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：123847655.2.2宽度优先搜索策略23184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目标8234187654宽度优先搜索的性质•当问题有解时，一定能找到解。•当问题为单位消耗值，且问题有解时，一定能找到最优解。•算法与问题无关，具有通用性。•时间效率和空间效率都比较低。1、定义在此搜索中，首先扩展最新产生的(即最深的)节点。深度相等的节点可以任意排列。这种盲目(无信息)搜索叫做深度优先搜索(depth-firstsearch)。2、特点首先，扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考虑另一条替代的路径。3、深度界限为了避免考虑太长的路径(防止搜索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。5.2.3深度优先搜索策略3、深度优先搜索算法(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出（5）如果没有后继节点，则转向上述第(2)步。(6)扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标深度优先搜索的性质•一般不能保证找到最优解。•当深度限制不合理时，可能找不到解。•最坏情况时，搜索空间等同于穷举。1、定义状态空间图中各节点之间有向边的代价是不同的，有向边上标有代价的搜索树成为代价搜索树。2、特点每次从OPEN表中选择一个代价最小的节点，移入CLOSED表。3、C(i,j):从节点i到其后继节点j的连线代价；g（x）:从初始节点到任意节点x的路径代价；g(j)=g(i)+C(i,j).5.2.4代价树的宽度优先搜索4、代价树的宽度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中代价最小的节点（即排在最前端的节点n），移入CLOSED的扩展节点表中。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，将他们的所有后继节点放到OPEN表中，并对每个后继节点j计算其总代价g(j)=g(j)+C(i,j),为每个后继节点指向n节点的指针，然后根据节点的代价大小对OPEN表中的所有节点进行从小到大的排序。(7)转向第(2)步。例子：推销员旅行问题P193ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n父节点A66BA71175CDABACBDE768765gC节点n父节点A66BA71114157578CDDEABCC节点扩展顺序：A，B，C，D，D，E路线：A---C----E代价树的宽度优先搜索每次从OPEN表中的全体节点中选择代价最小的节点移入CLOSED表进行扩展或判断。代价树的深度优先搜索从刚刚扩展的节点的后继节点中选择一个代价最小的节点移入CLOSED表中，并进行扩展或判断。5.2.5代价树的深度优先搜索4、代价树的深度优先搜索算法(1)把起始节点放到OPEN表中，令g(S0)=0。(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把OPEN表中的第一个节点（代价最小的节点n），移入CLOSED表。(4)如果n是目标节点，问题得解，退出。否则继续。(5)判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)。(6)对节点n进行扩展，并将其后继节点按有向边代价（C(i,j)）从小到大排序后放到OPEN表前端，并为每个后继节点设置指向n节点的指针。(7)转向第(2)步。ACBDE768765gC节点n父节点AACBDE768765gC节点n父节点A66BA77CAACBDE768765gC节点n