资源描述：
《状态空间的各种搜索.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、状态空间的各种搜索一.概述广度优先搜索法：以接近起始节点的程度依次扩展节点，即对下一层节点搜索前，必须先搜索完本层所有节点深度优先搜索法：首先扩展最新产生的节点，每层只对一个节点进行扩展，除非搜索失败或已达到预先约定的最大深度，才会退回去搜索原来忽略节点二.广度优先搜索1.定义:树上节点的扩展是沿着深度的“断层”进行的,即要对下一深度的任一节点进行搜索扩展之前,先要对当前(层)深度的每一个节点进行搜索,这种搜索能保证找到步数最少二.广度优先搜索2.算法:(1)把初始节点放入待扩展节点的open表中
2、,此表开始只有起始节点,其结构为队结构(先进先出),节点是先产生先扩展(2)如表open空(即待扩展节点已全部扩展完),失败退出(3)把open表中队列前的节点取出,按合适的途径扩展全部子节点,并把新产生的子节点依次加入open表后,同时提供子节点返回父节点指针,若无子节点返回(2)(4)如果有任一子节点为目标节点,则找到一个解,打印路径,退出返回(2)二.广度优先搜索例1有一个瓶中装有80ml化学溶液,实验中需要把它精确地平分成两份,没有量具,只有两杯子容量分别为50ml和30ml,编程求将溶液
3、平分的过程.三.深度优先搜索首先扩展最新产生的节点,使搜索沿着状态空间某条单一路径从起始节点向下进行,只有搜索到没有子节点产生时,才考虑另一条替换路径,且替换路径应先选与原路径差异最小的.为避免路径太长,防止搜索过程沿无益路径扩展下去,往往给出节点扩展最大深度.如任何节点达到深度界限,可作为没有子节点的节点处理,不再深入搜索下去.三.深度优先搜索例2.8数码问题作业完成8数码问题已知:给定的源状态,求出要求的目标态深优可用栈来存储节点,每生成一个节点就放入栈中(除了已经达到限定深度的节点外,因达到
4、限定深度节点无需再扩展),每次我们选栈顶节点再进行扩展,直至找到目标节点为止.扩展顺序扩展前栈内节点标号选取扩展节点标号11122,3,4,5532,3,4,6,7742,3,4,6,8852,3,4,6662,3,4,111172,3,4482,3,14,151592,3,14,1616102,3,17,1818三.深度优先搜索三.深度优先搜索深优搜索算法:(1)从初始节点开始,将待扩展节点依次放到open中(后进先出)(2)如表open空,即所有待扩展节点已全部扩展完毕,则失败退出(3)取op
5、en表中最新加入的节点,即栈顶节点出栈,按适当规则扩展所有子节点,同时记录这些节点的父指针,并将这些节点依次放入open表中.若无子节点,返回(2)(4)如某一子节点为目标节点,则求得解.沿指针所示,打印路径.若只需要一个解,则退出.否则返回(2)继续搜索新的目标节点.讨论:例3:在m*m(m<=7)的盘上玩一种游戏,在盘上放m*m-1块编号的方块,初始状态是在盘的左上角从最小编号放起,即1,2,…,m*m-2,m*m-1,按升序排列,先放完第一行,再放第二行,而目标状态是在盘上左上角从m*m-1
6、开始放起,即m*m-1,m*m-2,…,3,2,1,按降序排列,并使底下右角处保持空.三.深度优先搜索三.深度优先搜索例如:m=4123415141312567811109891011127654131415321初始状态目标状态任务:输入一个m值,从初始状态向目标状态转换,一次移动是把与空格相邻的方块移到空格,要求以最小步数实现这种转换,并显示移动过程.三.深度优先搜索例4:开连环锁问题.有一把锁,在它的锁销上有N个环,如果让这N个环都拆下来锁就被打开.但拆环和装环必须遵循下列规则(1)第一个环
7、可以随意装拆(2)第二个环只有在第一个环已装上时才可装拆(3)第N个环只有在第N-1个环已装上,且第N-2个,第N-3个,…,第1个环均已拆下时才可装拆试编程描述把锁打开的过程.解题思路:深优或者递归深优:设N=4(1).初态1，环都装上(2).由1可有两种：拆第2环获状态2；拆第1环获状态3(3).用栈存放，1态先送栈,2态再送,后送3态.深优规定每次选栈顶节点扩展,故先扩展3态(4).拆第3环得4压栈(或装第1环,则回复1态,删去)(5).装第1环得5压栈(6).拆第2环得6压栈(7).拆第1
8、环得7压栈(8).7态无法再扩展成目标态,故7态出栈,6态为栈顶,依次5,4,3出栈(9).2态为栈顶获8态(10).扩展成9态->10态->11态->12态->13态->14态->15态->16态三.深度优先搜索四.等代价搜索在等代价搜索中,每一节点之间的连线上都有两节点间代价值.若题目要求解最小代价路径时,可使用等代价搜索法.它沿着等代价路径断层进行扩展.其特殊情况是所有连线上的代价都相同,等代价搜索为宽度优先搜索.四.等代价搜索设定:i节点到j节点代价为m(i,j)起始节点为
