3.3-启发式搜索(2).ppt

人工智能丁世飞*人工智能第3章搜索策略√(2)*(A算法)图搜索算法只记录状态空间中那些被搜索过的状态,它们组成一个搜索图G。搜索图G由两种节点组成:Open节点:一个节点称为Open,如果该节点已经生成,而且启发式函数值h(x)已经计算出来,但是它没有扩展。这些节点也称为未考察节点。Closed节点:一个节点称为Closed,如果该节点已经扩展并生成了其子节点。Closed节点是已经考察过的节点。人工智能丁世飞*这样,可以给出两个数据结构OPEN和CLOSED表,分别存放了Open节点和Closed节点。节点x总的费用函数f(x)是g(x)和h(x)之和。生成费用g(x)可以比较容易地得到,如:如果节点x是从初始节点经过m步得到,则g(x)应该和m成正比(或者就是m)。如何计算h(x)呢?h(x)只是一个预测值。(A算法)人工智能丁世飞*ProcedureGraph-SearchBegin建立一个只含有初始节点S0的搜索图G,把S0放入OPEN表;计算f(S0)=g(S0)+h(S0);假定初始时CLOSED表为空。WhileOPEN表不空doBegin从OPEN表中取出f值最小的节点(第一节点),。Ifn是目标,则停止;返回n,并根据n的反向指针指出的从初始节点到n的路径。ElsedoBegin(1)生成n的子节点集合{mi},把mI作为n的后继节点加入到G中,并计算f(mi)。(2)Ifmi未曾在G中出现过(即未曾在OPEN和CLOSED表中出现过),then将它们配上刚计算过的f值,设置返回到n的指针,并把它们放入OPEN表中。图搜索算法(A算法)(P78:)人工智能丁世飞*(3)Ifmi已经在OPEN表中,则该节点一定有多个父节点,在这种情况下,计算当前的路径g值,并和原有路径的g值相比较:若前者大于后者,则不做任何更改;如果前者小于后者,则将OPEN表中该节点的f值更改为刚计算的F值,返回指针更改为n。(4)Ifmi已经存在于CLOSED表中,,,则将表中该节点的g、f值及返回指针进行类似(3)步的修改,并要考虑修改表中通过该节点的后继节点的g、f值及返回指针。(5)按f值从小到大的次序,对OPEN表中的节点进行重新排序。EndIf;EndElse;EndWhile;*上述图搜索算法生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树),图G中的每一个节点也在树T上。搜索树是由返回指针来确定的。G中的每一个节点(除了初始节点S0)都有一个指向G中一个父辈节点的指针。该父辈节点就是树中那个节点的唯一父辈节点。算法中(3)、(4)步保证对每一个扩展的新节点,其返回指针的指向是已经产生的路径中代价最小的。这可用下图来说明。图搜索算法说明人工智能丁世飞*设搜索算法已生成如下图(a)所示的搜索图和搜索树(带返回指针的部分)。图中实心圆点表示在CLOSED表中的节点,空心圆点表示在OPEN表中还未扩展的节点。下图(a)是扩展节点1之前的搜索图和搜索树,而(b)是扩展节点1之后的搜索图和搜索树。节点1扩展之前节点1扩展之后人工智能丁世飞*节点1扩展之前节点1扩展之后同时要考虑修改节点2的后继节点4的返回指针和g(4)的值,将节点4指向节点2,并把原来指向节点6的指针断开。当节点1扩展时,产生节点2。而节点2是CLOSED表中的节点,节点2的新g(2)值为2(设相邻两节点之间的代价均为1),而原来g(2)值为4,故将节点2的指针指向节点1,将原来指向节点3的指针断开。人工智能丁世飞*例1:水壶问题给定4L和3L的水壶各一个,水壶上没有刻度,可以向水壶中加水。如何在4L的壶中准确地得到2L水?这里:用(x,y)—4L壶里的水有xL,3L壶里的水有yL,n表示搜索空间中的任一节点。则给出下面的启发式函数:人工智能丁世飞*h(n)=2 如果0<x<4并且0<y<3=4 如果0<x<4或者0<y<3 =8 如果x=0并且y=3 或者x=4并且y=0 =10 如果x=0并且y=0 或者x=4并且y=3假定g(n)表示搜索树中搜索的深度,则根据图搜索策略得下图的搜索空间。例1:水壶问题