再上一篇:1. 4  习题
上一篇: 第 2 章  启发式搜索方法
主页
下一篇:2. 3  * 搜索算法
再下一篇:2. 4  习题
文章列表

2. 2  启发函数

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

启发式方法,或更一般地,经验规则,是指引搜索方向以有效求取到达目标节点路径的原则或规则。一般来说,所用的启发知识在很大程度上取决于待解问题和节点表示。例如,可用于求解前述8数码问题的一个很好的启发信息就是不在最终位置上的离家将牌个数, 记为 Misplaced(n)。对于图 2. 1 所示初始将牌布局, 将牌 4, 5, 6 离家, 因而Misplaced(n)= 3。

在图搜索中,启发知识的数值表示为从当前节点到目标节点的代价。它构成了如下代价函数的一部分:

f(n) = g(n) + h(n) (2.2)其中,g(n)是从起始节点到当前节点n代价的最小估值,h(n)为从当前节点n到终止节点代价的估值。显然,g(n)可用至今已被展开的从起始节点到当前节点n的所用路径中的最小代价来近似。然而,从n到任一目标节点的路径都是未知的。为此,无法精确确定h(n)而只能对其加以估算。在此我们规定目标节点的启发函数值为零,即对于n∈{ti},h(n)= 0。

在无法获取启发知识亦即对于所有节点n都有着h(n)= 0的情况下,启发式搜索退化为宽度优先搜索。当其启发函数具有 f (n)= g(n)+ h(n)这一特殊形式时,Graph-Search算法成为A 算法。

A算法

输入: 起始节点s和一组终止节点{ti}。

输出: 图G和树T。

(1) 初始化。以起始节点s构造图G和集合OPEN,G←{s},OPEN←{s},且令集合CLOSE 为空集。

(2) LOOP: 若OPEN 为空集,算法以失败结束。

(3) 从OPEN 中取出具有最小f(n)值的节点n,并使OPEN←OPEN{n},CLOSED←CLOSED∪{n}。

(4) 若n∈{ti},算法以成功结束。

(5) 展开n且令M为n的子节点且不为其前辈节点的节点集。将M 加入G。

(6) 对每一个节点m∈M:

①如果m| OPEN 且m| CLOSED,将m放入OPEN。估计h(m)并计算f(m)=g(m)+ h(m),其中g(m)= g(n)+ cost(n,m)。

② 如果m∈OPEN 或m∈CLOSED,将其逆向指针调整到给出最小g(m)值的路径。

③ 如果m 的逆向指针被调整且m 在CLOSED中,将其重新加入OPEN。

#第10页-

(7) 回到LOOP。

函数g(n),h(n)和f (n)在最小代价路径上的值可基于下列定义得到。

定义2.6  g* (n)是从s到n的所有路径中的最小代价。

定义2.7  * ( )是从 到一个目标节点的所有路径中的最小代价。

h n n

由g* (n)和h* (n)的定义可得

f* (n) = g* (n) + h* (n) (2.3)其中 * ( )是从起始节点经过节点 到达一个目标节点的所有路径中的最小代价。

f n n

下面用图2.7给出的实例示范g* 和h* 的计算方法。

有向图G= (V,E)中,

V= {a,b,c,d,e,i,j,k,l}

E= {(s,a),(s,b),(s,c),(a,d),(b,d),(b,e),(c,e),

(d,i),(d,j),(d,k),(e,j),(e,k),(e,l)}

连线的代价由函数cost 给出,且起始节点为s,目标节点为

{j,k}。

计算 * , * 和 * 的过程可归纳如下:

g h f

(1) 从起始节点开始计算g* 。显然,g* (s)= 0。

(2) 对其它任一节点n,计算从s到n的每条路径的代 * * *

图2.7  计算g ,h 和f价,而g* (n)是其中的最小值。

① 从 到 只有一条路径,所以 * ( )= ( → )= ( , )= 1。

s a g a g s a cost s a

② 从s到d 存在两条路径,即s→a→d 和s→b→d。g(s→a→d)= cost(s,a)+ cost(a,) = 1+ 4= 5 而 ( → → ) = ( , ) + ( , ) = 2+ 2= 4, 所以 * ( ) =d g s a d cost s b cost b d g dmin{5,4}= 4。

③ 从s到j 存在4条路径,它们的代价分别为

g(s→a→d →j) = 1+ 4+ 3= 8

g(s→b→d →j) = 2+ 2+ 3= 7

g(s→b→e→j) = 2+ 1+ 1= 4

g(s→c→e→j) = 3+ 3+ 1= 7

因此,g* (j)= min{8,7,4,7}= 4。

(3) 从目标节点开始计算h* ,可得h* (j)= h* (k)= 0。

(4) 对其它任一节点 ,计算从 到 或 的每条路径的代价,而 * ( )是其中的最

n n j k h n

小值。例如,由b通往终止节点的路径及其代价可为

①b→d→j,h(b→d→j)= cost(b,d)+ cost(d,j)= 2+ 3= 5;

②b→d→k,h(b→d→k)= cost(b,d)+ cost(d,k)= 2+ 1= 3;

③b→e→j,h(b→e→j)= cost(b,e)+ cost(e,j)= 1+ 1= 2;

④b→e→k,h(b→e→k)= cost(b,e)+ cost(e,k)= 1+ 3= 4。

因此, * ( )= {5,3,2,4}= 2。

h d min

一旦得到g* (n)和h* (n),f* (n)可由f* (n)= g* (n)+ h* (n)求得。

对于图2.7所示有向图,s→b→e→j 是从s到目标节点之一j 的最小代价路径,且代

#第11页-

价为4。值得注意的是,在最小代价路径上的每个节点的f* 值都等于最小代价。当然,在实际求解过程中,图的结构在我们展开它之前是未知的。因此,g* 只能基于至今已被展开的路径计算,而 * 则根本无法得知。

h