人工智能与专家系统（GIS）ppt课件.ppt

《人工智能与专家系统（GIS）ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章问题求解策略5.1搜索基本原理5.2图搜索策略5.3盲目搜索5.4启发式搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。宽度优先搜索和深度优先搜索，均属于盲目搜索方法。其共同缺点是节点排序的盲目性，由于不采用领域专门知识去指导排序，往往会搜索了大量无关的状态节点后才碰到解答，所以称为盲目搜索。5.3盲目搜索①宽度优先搜索宽度优先搜索（breadth-firstsearch）的定义：如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索（breadth-firs

2、tsearch）。这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。宽度优先搜索示意图宽度优先搜索搜索树上的所有节点都标记它们所对应的状态描述，每个节点旁边的数字表示节点扩展的顺序（按顺时针方向移动空格）。图中最后一个节点是目标节点。八数码问题的宽度优先搜索②等代价搜索宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法。OPEN表与CLOSED表示例OPEN--作为存放待扩展节点的表；　CL

3、OSE--作为存放已被扩展节点的表；等代价搜索方法以g（i）的递增顺序扩展其节点，其算法如下：（1）把起始节点Ｓ放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求得一个解；否则令g（S）=0。（2）如果OPEN是个空表，则没有解而失败退出。（3）从OPEN表中选择一个节点i，使其g（i）为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点i（要是有目标节点的话）；否则，就从中选一个作为节点i。把节点i从OPEN表移至扩展节点表CLOSED中。（4）如果节点i为目标节点，则求得一个解

4、。（5）扩展节点i。如果没有后继节点，则转向第（2）步。（6）对于节点i的每个后继节点j，计算g（j）=g（i）+c（i,j），把所有后继节点j放进OPEN表。提供回到节点i的指针。（7）转向第（2）步。等代价搜索算法框图③深度优先搜索③深度优先搜索分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的（即最深的）节点。深度相等的节点可以任意排列。定义节点的深度如下：（1）起始节点（即根节点）的深度为0。（2）任何其它节点的深度等于其父辈节点深度加上1。按深度优先搜索生成的八数码难题搜

5、索树，深度界限为5。把要求解的问题的具体领域的知识加进搜索算法中，控制搜索过程，以提高算法效率的搜索方法，称为启发式搜索。注：1）这里搜索的对象(常称状态)往往是边搜索边生成，因此在考虑这种搜索的复杂性时，必须将搜索对象的生成和评估的代价计算在内。5.4启发式搜索注：2)根据启发性信息(特定领域的知识信息)，在生成搜索树时可考虑种种可能的选择：a)下一步展开哪个节点？b)是部分展开还是全部展开？c)使用哪个规则(算子)？d)怎样决定舍弃还是保留新生成的节点？e)怎样决定舍弃还是保留一棵子树？f)怎样决

6、定停止或继续搜索？g)如何定义启发函数(估值函数)？h)如何决定搜索方向？启发式搜索启发信息与估价函数启发信息按运用的方式可分为：（1）陈述性启发信息（2）过程性启发信息（3）控制性启发信息按其用途划分,启发性信息可分为以下三类：(1)用于扩展节点的选择,即用于决定应先扩展哪一个节点,以免盲目扩展。(2)用于生成节点的选择,即用于决定应生成哪些后续节点,以免盲目地生成过多无用节点。(3)用于删除节点的选择,即用于决定应删除哪些无用节点,以免造成进一步的时空浪费。估价函数一个比较灵活的方法是应用

7、某些准则来重新排列每一步OPEN表中所有节点的顺序。然后，搜索就可能沿某个被认为是最有希望的边缘区段向外扩展。应用这种排序过程，需要某些估算节点“希望”的量度。用来估算节点希望程度的量度，叫做估价函数（evaluationfunction）。1、基本思想a)对于每个在搜索过程中遇到的新状态，计算一个估计值，根据估计值的大小，确定下一步将从哪一个状态开始继续前进。b)一般以估计值小者作为较优的状态，以此实现最佳优先搜索。c)计算状态估计值的函数是确定的，但每个状态的估计值的大小与初始状态到该路径有关。有

8、序搜索算法2、算法1)建立一个空的状态序列SS2)建立一个空的状态库SB3)定义一个估值函数f4)若初始状态为S0,则定义初始状态S0(0,f(0))为当前新状态5)将当前新状态按估计值从小到大的顺序插入到SS中，若新状态为目标状态，则将相应状态插入到具有相同估计值的状态的最前面；否则将相应状态插入到具有相同估计值的状态的最后面有序搜索算法6)若在SS或SB中原有一个状态与当前新状态共一个状态，则删去原有状态7)若新状态在SS的最前面，则转11)8)若某