再上一篇:1. 3  本书的结构
上一篇:1. 4  习题
主页
下一篇:2. 2  启发函数
再下一篇:2. 3  * 搜索算法
文章列表

第 2 章  启发式搜索方法

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

启发式搜索方法依靠任务无关信息来简化搜索进程。在很多情况下,问题求解可视为

系统化地构造或查找解答的过程。因此,在人工智能领域中,开发出了用于计算机问题求

解的各种不同搜索算法[117]。尽管在某些情况下并非十分有效,迷宫、定理证明、国际象棋

等问题都可以由计算机程序给出解答。一般来说,搜索过程包括检查搜索空间、估价可能

有解的各种不同路径、记录已经搜索到的各个路径。

为简化搜索并减少搜索过程中时有出现的大量可选路径,从与待解问题有关的信息

中所得到的启发知识或“经验法则”可用来确定搜索的方向。精心选择的启发信息可在很

大程度上加大找出解答的机会,且在同时减少求解所需的时间。这一章统观启发式搜索方

法并着重介绍A* 算法。

在如图2.1所示的3 3九宫格棋盘上,摆放着8个将牌,上面不重复地刻着从1到8

这8个数码。棋盘上余下一个空格使得其相邻将牌可以移动到它上面。设法找到一个将

牌移动序列,用最少次数的移动将给定的起始布局转换为给定的终止布局,这就是8数码

问题。实际上,记录空格的移动比记录将牌的移动方便得多。 %

1 2 3 1 2 3 1 2 3 1 2 3

8 4 5 右移 8 4 5 上移 8 4 左移 8 4

7 6 7 6 7 6 5 7 6 5

起始布局 n1 n2 终止布局

图 2.1  8数码问题

在求取最小移动次数时,可用对各个布局的评价作为代价函数,从而把8数码问题变

成一个最小代价问题。代价函数可被分为两项: 一项是至今已经付出的代价; 另一项则

是基于启发信息估计出的到达目标尚需付出的代价。在代价函数中引入适当选择的启发

信息(见2.2节),计算机搜索程序能够有效地解决8数码问题。

2. 1  图搜索算法

图是构造搜索空间、开展搜索过程的便利工具。

定义2.1  图 G= (V,E)是一个二元组,其中V= {v1,v2,…,vn}是节点的有限集,

E= {(vi,vj) V× V}是连结V中节点的连线集。

一个图可为有向图亦可为无向图。有向图的连线是有方向性的,因而从vi到vj 的连

线(vi,vj)与从vj 到vi的连线(vj,vi)是不同的。但在无向图中,连线(vi,vj)与(vj,vi)是相

同的。图2.2是有向图G= ({v1,v2,v3,v4,v5},{(v1,v2),(v1,v4),(v2,v5),(v3,v2),(v3,

v4),(v4,v3)}的图示。

#第6页-

定义2.2  在有向图G= (V,E)中,若vi,vj∈V且(vi,vj)∈E,亦即存在连线(vi,vj),则节点vj 是节点vi的子节点或称后辈节点。同样,vi是vj 的父节点或称前辈节点。

定义2.3  树是一类除根节点外的每个节点都只有一个父节点的图。

如果我们从图2.2所示有向图中去掉两根连线(v3,v2)和(v3,v4),则所余下的就是一个树。在搜索过程中,树被用来记录已展开的路径。

图 2.2  有向图示例 图2.3  回溯示例

多数情况下,有待考察的图是一个有向图,通常还有唯一的一个起始节点。搜索过程不断生成后辈节点并把它们加入图中。这一过程被称为节点展开。搜索持续进行,直到它找到属于终止节点集的任一节点。以图的形式记录搜索过程的一个重要原因是为了便于回溯。回溯使得搜索过程得以废弃任何失败的路径,从而重新开拓一条崭新的路径。以图2.3所示搜索图为例,如果搜索过程到达节点B 但它却似乎无助于求解,则搜索过程可以回溯到父节点A并从节点C继续。

一个路径是否有助于求解通常决定于代价函数。它对一个节点的评价基于至今已经花费的代价和其通往目标节点的可能性。代价函数可与图中的连线一起被用来表达搜索过程中从一个节点到另一个节点的代价。

定义2.4  cost(vi,vj)是节点vi与节点vj 间连线的代价。

定义2.5  节点序列v1→v2→…→vk 是从节点v1到节点vk的长度为k的路径。其中对于j= 1,2,…,k- 1,有vj+ 1为vj 的子节点。

一条路径的代价也就是从起始节点经由如下公式列出的中间节点到达目标节点的路径上所有连线代价之和,即

k- 1

cost(n1 →…→nk) = ∑cost(nj,nj+ 1) (2.1)

j=1

因此,要评价节点n,我们可以建立一个代价函数f(n),并使其包含两个组成部分: 其一是从起始节点到n的实际代价; 其二是从n到终止节点的代价估值。下面给出的基于f (n)的图搜索过程Graph-Search试图找到一个从起始节点到终止节点的最小代价路径。

Graph-Search算法

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

输出: 图G和树T。

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

#第7页-

CLOSE 为空集。

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

(3) 从 OPEN 中取出第一个节点 n, 并使 OPEN ←OPEN-{n}, CLOSED←CLOSED∪{n}。

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

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

(6) 将M中既不在OPEN 中也不在CLOSED 中的节点放入OPEN。

(7) 给每个M 中既不在OPEN 中也不在CLOSED 中的节点设置一个指向其父节点的逆向指针。

(8) 调整M中那些同时也在OPEN 或CLOSED 中的节点的逆向指针。

(9) 调整M和CLOSED 中每个节点的后继节点的逆向指针。

(10) 依据评价函数值重新安排OPEN 中的节点。

(11) 回到LOOP。

上述算法中所用的逆向指针就构成了解树T,而回溯则是通过将节点分别放入OPEN 和CLOSED两集合中而实现的。如果一个节点尚未被展开,亦即它的子节点还未被生成,则将它放入OPEN; 否则,一个已被展开的节点将被放入CLOSED。图2.4示范出一个执行Graph-Search算法历经3次循环的例子。

循环1

步骤(1): 最初OPEN= {s},CLOSED 为空集。见图2.4(a)。

步骤(3): s被展开,OPEN 为空集,CLOSED= {s}。

步骤(5): 假定展开s生成3个子节点,M= {a,b,c}。见图2.4(b)。

步骤(6): OPEN= {a,b,c}。

步骤(7): 设置逆向指针。见图2.4(c)。

循环2

步骤(3): 假定a 被选来扩展,OPEN= {b,c},CLOSED= {s,a}。

步骤(5): 假定扩展a 生成三个子节点,M= {b,d,e},见图2.4(d)。

步骤(6): OPEN= {b,c,d,e}。

步骤(7): 设置逆向指针。见图2.4(e)。注意b在此之前已有逆向指针指向s,这种情况下不作调整。

循环3

步骤(3): 假定b被选来扩展,OPEN= {c,d,e},CLOSED= {s,a,b}。

步骤(5): 假定扩展b生成一个子节点,M= {e}。见图2.4(f)。

步骤(6): OPEN= {c,d,e}。

步骤(7): 设置逆向指针。见图2.4(g)。注意e在此之前已有反向指针指向a,这种情况下要调整为指向b。

#第8页-

图2.4  搜索图

图2.5  宽度优先搜索 图 2.6  深度优先搜索(深度限制= 2)

搜索的成功取决于选择下一个被扩展节点的选取,也受Graph-Search 算法中步骤(10)的控制。这一步骤依据代价函数值来决定OPEN 中节点的顺序。如果代价函数只考虑从起始节点到当前节点的代价,这一搜索称为无信息搜索。这一情况通常意味着无法获取从当前节点到终止节点可能代价的有关附加信息。另外,如果连线的代价是一个常数,例如1,则代价函数可被定义为搜索树的深度。在此前提下,如果OPEN 中的节点是按代价函数值由小到大排序,就得到宽度优先搜索。宽度优先搜索遍历搜索整个搜索空间。如

#第9页-

果OPEN 中的节点是按代价函数值由大到小排序,就得到深度优先搜索。图2.5和2.6显示出宽度优先搜索与深度优先搜索的不同。