资源描述：
《人工智能 一般搜索原理---盲目搜索课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、人工智能及其应用第六讲一般搜索原理--盲目搜索搜索:从问题表示到问题解决的求解过程.一.盲目搜索:人为给定搜索顺序的无信息搜索.1.宽度优先搜索2.深度优先搜索3.等代价搜索二.启发式搜索:根据检测到的信息决定搜索顺序的有信息搜索.1.有序搜索,2.A算法,3.A*算法第六讲一般搜索原理--盲目搜索一.盲目搜索1.宽度优先搜索以接近起始节点的程度依次扩展节点的搜索,搜索过程是逐层进行的,在下一层的任意一个节点进行搜索之前,必须完成本层的所有节点的搜索.设:OPEN表:未扩展节点表CLOSED表:已扩展节点表第六讲一般搜索
2、原理--盲目搜索算法(1)把起始节点放到OPEN表中,若该节点为一目标节点,则得一个解,退出.(2)如果OPEN表是一个空表,则没有解,失败退出.否则继续.(3)把第一个节点N从OPEN表中移出到CLOSED表中.(4)扩展节点N.如果没有后继节点,则goto(2).(5)把N的所有后继节点放到OPEN表末端,并提供从这些后继节点回到N的指针.(6)如果N的任一后继节点是目标,则成功退出,否则,goto(2).第六讲一般搜索原理--盲目搜索SLOMFPQNF宽度优先搜索示意图第六讲一般搜索原理--盲目搜索例如:八数码难题
3、28314765283147652318476528316475283164752814376528314576283164752318476523184765283714658321476528314765宽度优先搜索示意图2.深度优先搜索扩展最新产生的节点,搜索沿着状态空间某条单一的路径从起始节点向下搜索,结果使得只有搜索到一个没有后裔的状态时,才考虑另一条替代的路径.问题:当搜索深度很深时,需要控制.第六讲一般搜索原理--盲目搜索第六讲一般搜索原理--盲目搜索算法(1)把起始节点放到OPEN表中,若该节点为一目标节
4、点,则求得一个解,退出.(2)如果OPEN表是一个空表,则没有解,失败退出.否则继续.(3)把第一个节点N从OPEN表中移出到CLOSED表中.(4)如果节点N的深度等于最大深度,则goto(2).(5)扩展节点N.把N的所有后继节点放到OPEN表前端,并提供从这些后继节点回到N的指针.如果没有后继节点,则goto(2).(6)如果N的任一后继节点是目标,则成功退出,否则,goto(2).SLOMFPQNF深度优先搜索示意图第六讲一般搜索原理--盲目搜索第六讲一般搜索原理--盲目搜索2831476528314765231
5、8476528316475283164752814376528314576283164752318476523184765283714658321476528314765深度优先搜索示意图第六讲一般搜索原理--盲目搜索3.等代价搜索在搜索过程中要求具有最小代价路径的搜索.利用宽度优先搜索路径,通过计算最小代价,可得到等代价搜索算法.设:C(i,j)为节点i到其后继节点j的代价;g(i)为起始节点s到任一节点i的路径代价.第六讲一般搜索原理--盲目搜索算法(1)把起始节点放到OPEN表中,若该节点为一目标节点,则求得一个解
6、,退出.否则,令g(s)=0.(2)如果OPEN表是一个空表,则没有解,失败退出.否则继续.(3)把第一个节点i,其g(i)为最小,从OPEN表中移出到CLOSED表中.(4)扩展节点i.如果没有后继节点,则goto(2).(5)把i的所有后继节点j,计算g(j)=g(i)+C(i,j),放到OPEN表末端,并提供从这些后继节点回到i的指针.(6)如果i的任一后继节点是目标,则成功退出,否则,goto(2).第六讲一般搜索原理--盲目搜索283147652831476523184765283164752831647528
7、14376528314576283164752318476523184765283714658321476528314765等代价搜索示意图542137624376第六讲一般搜索原理--盲目搜索总结1.OPEN表中的数据结构:宽度优先搜索采用队列;深度优先搜索采用栈;等代价搜索采用g(i)的递增次序.2.宽度优先搜索是各对节点之间的代价相等,所以,宽度优先搜索是等代价搜索的一种特殊形式.3.用于解决简单问题.
