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

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