人工智能原理ch45()53.ppt

《人工智能原理ch45()53.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第四章一般搜索原理知识表示的目的是为了便于计算机求解，是为了解决问题。从问题的描述（表示）到问题的解决，有个求解的过程，也就是搜索过程。在这一过程中采用适当的搜索技术，包括各种规则、过程和算法等推理技术，力求找到问题的解答。本章讨论一些早期的搜索技术或用于解决比较简单问题的搜索原理（启发式搜索、宽度优先、深度优先、有序搜索）。4.1盲目搜索盲目搜索又叫做无信息搜索。一般只适用于求解比较简单的问题。O规则库搜索树：R1R2A.B.R1:如X/12为整，则X/6为整。R2R3R1R4C.D.E..R2:如X/20为整，则X/10为整R3R4R2R3R4SF..G.HIR3:如X/6

2、为整，则X/2为整。R4SR4R4SR4:如X/10为整，则X/5为整。SSS输入数据库：N/12，N/20S=success判断是否N/5这是一个产生式系统的例子。节点用表示。每一个节点对应于一个状态，反映当时数据库的情况。如节点O：N/12，N/20；节点A：N/12，N/20，N/6；节点D：N/12，N/20，N/6，N/2。每条连线对应于一个操作符。棋局对应走步，这里对应于一条产生式规则。该搜索树给出了所有可能的求解证明渠道。抽象地描述：给定初始节点和目标节点，求图中的一条合理路径（所谓合理有的指只要找到就行；有的要求搜索步骤最少或路径最短等等）。就这个例子，我们看一

3、下宽度优先搜索、深度优先搜索是如何进行的。当然，并不是所有问题都可以画出图示的搜索树（深度不深、每条支路都有解且支路不多）。4.1.1宽度优先搜索如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索。也就是说，这种搜索是逐层进行的。在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。宽度优先搜索算法（流程框图）如下：（1）把起始节点放到OPEN表中（如果该起始节点为目标节点，则求得一个解答）。OPENCLOSEDO（2）如果OPEN表是个空表，则没有解，失败退出。否则继续。（3）把第一个节点从OPEN表中移出，并把它放入CLOSED的扩展节点表中

4、。（4）扩展该节点。如果没有后继节点，则转向上述第（2）步。（5）把该节点的所有后继节点放到OPEN表的末端，并提供这些后继节点返回该节点的指针。（6）如果该节点的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向（2）。O规则库搜索树：R1R2A.B.R1:如X/12为整，则X/6为整。R2R3R1R4C.D.E..R2:如X/20为整，则X/10为整R3R4R2R3R4SF..G.HIR3:如X/6为整，则X/2为整。R4SR4R4SR4:如X/10为整，则X/5为整。SSS输入数据库：N/12，N/20S=success判断是否N/5OABOOABCDOABC

5、DESOPEN表CLOSED表OBSR2R4(回溯)宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径。注：1、在OPEN表中已有的节点，新扩展有关节点不放OPEN表中。2、CLOSED表中所放节点位置前后不重要。644.1.2深度优先搜索另一种盲目（无信息）搜索叫做深度优先搜索。在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。节点深度定义如下：(1)起始节点（即根节点）的深度为0。(2)任何其它节点的深度等于其父辈节点深度加1。首先、扩展最深的节点的结果使得搜索沿着状态空间某条单一的路径从起始节点向下进行下去；只有当搜索到达一个没有后裔的状态时，它才考

6、虑另一条替代的路径。对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接收的解答序列的已知深度上限还要深。为了避免考虑太长的路径（防止搜索过程沿着无益的路径扩展下去），往往给出一个节点扩展的最大深度—深度界限。任何节点如果达到了深度界限，那么都将它们作为没有后继节点处理。和宽度优先法不同之处在于：扩展的节点，其后继节点放入OPEN表的前端O规则库搜索树：R1R2A.B.R1:如X/12为整，则X/6为整。R2R3R1R4C.D.E..R2:如X/20为整，则X/10为整R3R4R2R3R4SF..G.HIR3:如X/6为整，则X/2为整。R4SR4R4SR

7、4:如X/10为整，则X/5为整。SSS输入数据库：N/12，N/20S=success判断是否N/5OABOOACDBOACFSDBOPEN表CLOSED表OACSR1R2R4(回溯)三步操作，不是最短。如知道最短2步，深度界限定为2，肯定有解且可找到最短路径。但有些情况下（多数），不限定深度不好。4.2启发式搜索盲目搜索的效率低，耗费过多的计算空间与时间。如果能够找到一种用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大大提高。“启发”（heuristic）是关