计算机3搜索推理技术1

3搜索推理技术

搜索策略

•3.2盲目搜索

＞从问题表示到问题的解决，有一个求解的过程。常见的AI

问题求解技术有两种，即“搜索”(Search)和“推理”

(Reasoning)方法。

＞搜索是AI研究的一个重要课题，几乎所有的AI问题都可以

被归结为搜索问题。各种搜索技术的研究是AI初期(1956

-1970)的“热门”课题。虽然现在已有不少成熟的搜索

技术出现于AI手册和各种AI书籍中，并在一些知识系统种

得到广泛应用。但搜索效率的提高仍然是现在和今后AI研

究者关心的一个重要问题。

＞问题求解的第二种方法是逻辑推理。通过构造一个逻辑系

统，由它可以从已有的断言(公理)推导出新的断言。并

用逻辑形式语言描述的一组公理来表达问题域。用这种方

法来解决问题就是通过推理来积聚越来越多的断言，直到

获得向题的解答。

＞虽然问题求解可通过搜索方法，也可用逻辑推理，但二者

的侧重点是不一样的。前者着重于寻求问题解答的过程，

而后者强调前提(初始)问题空间(公理集合)与问题解

答间连接的逻辑正确性。或者简单地讲，搜索着重于发现

(Discovery)，而推理弓星调证明(Proof)。

3.1图搜索策略

•3.1.1问题求解的过程

•3.1.2图搜索的一般过程

3

3.L1问题求解的过程

1.问题的表示：主要采用状态空间法（状态空间图）和问

题归约法（与或图）。

2,问题的求解：通过在图（“状态空间图“或“与或图”）中

进行搜索，寻找一条路径的方法.

•一般搜索：从初始节点出发,扩展节点，并沿子节点

推进，继续扩展选择的子节点,直到找到通向目标结

点的路径，或找到解树为止。

＞肓目搜索:是按预定的控制策略进行搜索，在搜索过

程中获得的中间信息并不改变控制策略。

＞启发式搜索：是在搜索过程中加入了与问题有关的

启发性信息，缩小问题的搜索范围，指导搜索朝着

最有希望的方向前进，以尽快地找到问题的（最优

）解。

4

•例：从某王姓家族的四代中找王A的后代且其寿

命为X的人。

王A：寿命47,有儿子王B1、王B3、王B2

王B1：寿命77,有儿子王C1、王C2

王B3：寿命52,有儿子王D1

王B2：寿命65,有儿子王E1、王E2

王F1：寿命32

王G1：寿命96

王C2：寿命87,有儿子王F1

王D1：寿命77,没有儿子

王E1：寿命57,有儿子王G1

王E2：寿命92,有儿子王H1

王C1：寿命27,没有儿子

王H1：寿命51

若X=57,

•如果是一个N代的家族表中找其寿命为X的人，

我们最可能用的手工方法是从家族表的开始往

下，例中还要求所找的人是某人的后代，就比

较复杂了。如果用图来表示，就很容易了。图

中把姓氏省去，每个成员的后代按例子中给出

名字的先后顺序。

3.L2图搜索的一般过程（续）

•图搜索策略可看作一种在图中寻找路径的方

法。初始节点和目标节点分别代表初始数据

库和满足终止条件的数据库。求得把一个数

据库变换为另一数据库的规则序列问题就等

价于求得图中的一条路径问题。研究图搜索

的一般策略，能够给出图搜索过程的一般步

骤。

6

3.L2图搜索的一般过程(续)

•数据结构：

>OPEN：未扩展节点表

>CLOSED：已扩展节点表

•算法过程

>(1)建立一个只含有起始节点S的搜索图G,把S放到一个叫

作OPEN的未扩展节点表中；

>(2)建立一个叫做CLOSED的已扩展节点表,其初始为空表；

>(3)LOOP:若OPEN表是空表,则失败退出；

>(4)选择OPEN表上的第一个节点,把它从OPEN表移出并放

进CLOSED表中，称此节点为节点n;

>(5)若n为一目标节点，则有解并成功退出，此解是追踪图G中

沿着指针从n到S这条路径而得到的(指针将在第(7)步中设置

)；

7

3.L2图搜索的一般过程(续)

»(6)扩展节点n,同时生成不是n的祖先的那些后继

节点的集合M,把M的这些成员作为n的后继节点

添入图6中；

>(7)对那些未曾在G中出现过的(即未曾在OPEN表

上或CLOSED表中出现过的)M成员设置一个通向n

的指针，把M的这些成员加进OPEN表。对已经在

OPEN或CLOSED表上的每一个M成员，确定是否

需要更改通到n的指针方向。对已在CLOSED表上

的每个M成员，确定是否需要更改图G中通向它的

每个后裔节点的指针方向；

>(8)按某一任意方式或按某个探试值,重排OPEN表;

>(9)GoLoop

o8

3.L2图搜索的一般过程(续)

是

CPF、表为空工一SJ失败

把第一个节点(”)从

OPEN表移至CLOSED表

——

〃是否为目标节点?

把”的后继节点"放入OPEN表

的末端,提供返回节点〃的指针

修改指针方向

重排OPEN表

9

图搜索过程框图

3.1.2搜索的一般过程（续）

•过程说明：

»①搜索图：图搜索的一般过程生成一个明确的图G,

称为搜索图。

»②搜索树：图搜索的一般过程生成G的一个子集T

称为搜索树。由步骤(7)中设置的指针来确定。

>③G中每个节点(S除夕D都有一个只指向G中一个父

辈节点的指针,该父辈子点就定为树中那个节点的

惟一父辈节点。

A④OPEN表工.节点都是搜索图上未被扩展的端节

点，而CLOSED表上的节点,或者是已被扩展但没

有生成后继节点的端节点,或者是搜索树的非端节

点。

10

3.L2图搜索的一般过程(续)

>⑤步骤(8)对OPEN表上的节点进行排序，以便选出

一个“最好”的节点作为步骤(4)扩展使用。

(1)排序可以是任意的即肓目的(盲目搜索)

(2)可以用启发信息为依据(启发式搜索)

>⑥当扩展某个节点时,搜索图已经保存了从初始节

点到该节点的搜索树。

>⑦每当被选作扩展的节点为目标节点时，这一过程

就宣告成功结束。这时，从目标节点按指向父节

点的指针不断回溯，能够重现从起始节点到目标节

点的成功路径。

>⑧当搜索树不再剩有末被扩展的端节点

OPEN表为空时)，过程就以失败告终。

点，达不到目标节点。

11

3.L2图搜索的一般过程(续)

>⑨步骤(6)扩展节点时，生成一个节点的所有后继节点。

扩展节点1以前的搜索图扩展节点1以后搜索图

12

3.2盲目搜索

•3.2.1宽度优先搜索

•3.2.1深度优先搜索

•3.2.3等代价搜索

13

321宽度优先搜索

•宽度优先搜索：如果搜索是以接近起始节点的程度来依次

扩展节点，那么这种搜索叫做宽度优先搜索(breadth-first

search)o

•特点：这种搜索是逐层进行的；在对下一层的任一节点进

行搜索之前，必须搜索完本层的所有节点。

宽度优先搜索示意图

14

321宽度优先搜索(续)

•宽度优先搜索算法：

>(1)把起始节点放到OPEN表中(如果该起始节点为

一目标节点，则求得一个解答)。

»(2)如果OPEN是个空表则没有解，失败退出，否

贝『继续。

»(3)把第一个节点(节点从OPEN表移出，并把它

放入CLOSED的护展节占表中。

»(4)扩展节点n,如果没有后继节点，则转向步骤

(2)。

»(5)把n的所有后继节点放到OPEN表的末端，并提

快从这些后继节点回到n的指针。

>(6)如果n的任一个后继节点是个目标节点，则找到

一个解答，成功退出，否则转向步骤(2)。15

321宽度优先搜索(续)

•宽度优先搜索算法说明：

>(1)搜索树：搜索过程产生的节点和指针构成一棵隐

式定义的状态空间图的子树，称为搜索树。

>(2)如果问题有解,宽度优先算法能够保证找到一条

通向目标节点的最短路径(即找到最优解)。

»(3)如果问题无解，对于有限图，该算法会失败退

出；对于无限图，则永远不会终止。

>(4)宽度优先搜索是图搜索一般过程的特殊情况，

将图搜索一般过程中的第8步具体化为本算法中的

第6步，这实际是将OPEN表作为“先进先出”的

队列进行操作。16

321宽度优先搜索（续）

把第一个v点”从

^■OPEN^^CLOSED^^H

扩展〃.把”的后继节点”放入OPEN

表的末端.提供返回节点”的指针

否是否有任何后继

成功

节点为目标节点？

17

321宽度优先搜索（续）

・例：八数码难题，在3X3的方格棋盘上，分

别放置了标有数字1,234,5,6,7,8的八张牌,

初始状态如图So所示，目标状态如图Sg所示,

要求应用宽度优先搜索策略寻找从初始状态

到目标状态的解路径。

283123

1484

765765

18

321宽度优先搜索（续）

八数码难题的宽度优先搜索树19

322深度优先搜索

•深度优先搜索：在搜索过程中，首先扩展最新产生的(即最

深的)节点，深度相等的节点可以任意排列，这种搜索叫做

深度优先搜索(depth-firstsearch)。

•特点：首先，扩展最深的节点的结果使得搜索沿着状态空

深度优先搜索示意图

20

322深度优先搜索（续）

•节点深度：

（1）起始节点（即根节点）的深度为0。

（2）任何其他节点的深度等于其父辈节点的深度加1。

•深度界限：

＞为了避免考虑太长的路径（防止搜索过程沿着无益

的路径扩展下去）,往往给出一个节点扩展的最大深

度，称为深度界限。

＞任何节点如果达到了深度界限，那么都将把它们作

为没有后继节点来处理。

＞即使应用了深度界限，深度优先搜索所求得的解答

路径也不一定就是最短路径。

21

322深度优先搜索(续)

•含有深度界限的深度优先搜索算法：

»⑴把起始节点S放到未扩展节点OPEN表中。如果

此节点为一目标节点，则得到一个解。

>(2)如果OPEN为一空表,则失败退出。

>(3)把第一个节点(节点n)从OPEN表移到CLOSED

表。

>(4)如果节点n的深度等于最大深度，则转向步骤(2)。

>(5)扩展节点n,产生其全部后裔,并把它们放入

OPEN表的前头。如果没有后裔，则转向步骤(2)。

>(6)如果后继节点中有任一个为目标节点，则求得一

个解，成功退出;否则，转向步骤(2)。

22

23

322深度优先搜索（续）

八数码难题深度界限为5的深度优先搜索树24

323等代价搜索

•宽度优先的局限：

＞在宽度优先搜索中作了一种假设,认为状态空间中

各边的代价都相同，且都为一个单位量。从而可用

路径的长度代替路径的代价。

＞然而,对许多问题这种假设是不现实的，它们的状态

空间中的各个边的代价不可能完全相同。

例：城市交通问题。

＞为此,需要在搜索树中给每条边都标上其代价。

・代价树：在搜索树中给每条边都标上其代价。这种

边上标有代价的树称为代价树。

•等代价搜索：寻找从起始状态至目标状态的具有最

小代价的路径问题，叫做等代价搜索。在等代价搜

索算法中，是沿着等代价路径断层进行扩展的。25

323等代价搜索（续）

•例：城市交通问题.设有5个城市，它们之间的

交通路线如图所示，图中的数字表示两个城

市之间的交通费用，即代价。用等代价搜索，

求从A市出发到E市，费用最小的交通路线。

26

323等代价搜索（续）

•解：其代价搜索树如右下图:最优解：A,C,D,E

城市交通图

城市交通图的代价搜索树

27

323等代价搜索（续）

•记号

从节点/到其后继节点j的连接弧线代

价。

>g（/）：从起始节点S到任一节点/的路径代价（即

是从起始节点S到节点/的最少代价路径上的

代价）

28

323等代价搜索（续）

•等代价搜索算法：

»⑴把起始节点S放到未扩展节点有OPEN中。如果

此起始节点为一目标节点，则求得一个解，否是令

g（s）=o0

>（2）如果OPEN是个空表，则没有解而失败退出。

>（3）从OPEN表中选择一个节点I,使其g⑴为最小。

如果有几个节点都合格，那么就要选择一个目标节

点作为节点i（如果有目标节点的话），否则，就从中

选一个作为节点八把节点j从OPEN表移至扩展节

点表CLOSED中。

29

323等代价搜索(续)

>⑷如果节点/为目标节点，则求得一个解。

A(5)扩展节点如果没有后继节点，则转向

步骤(2);

>(6)对于节点/的每个后继节点J,计算

g(h=g(D+c(就,并把所有后继节点j放进

OPEN表,提供回到节点/的指针。

A(7)转向步骤(2)。

30

31

3.3启发式搜索

•3.3.1启发式搜索策略和估价函数

•3.3.2有序搜索

•3.3.3A*算法

•3.3.4图搜索策略的评价

32

3.3启发式搜索（续）

•盲目搜索存在的问题

A扩展节点数目较多。

A效率低，耗费过多的计算时间和空间。

＞分析前面介绍的宽度优先、深度优先搜索，或等代

价搜索算法，其主要的差别是OPEN表中待扩展节点

的顺序问题。如果找到一种方法用于排列待扩展节

点的顺序，即选择最有希望的节点加以扩展，那么,

搜索效率将会大为提高。

33

331启发式搜索策略和估价函数

•启发性信息：指那种与具体问题求解过程有关的，

并可指导搜索过程朝着最有希望方向前进的控制信

息。三种启发性信息：

»(1)用于决定要扩展的下一个节点，以免像在宽度优先或

深度优先搜索中那样盲目地扩展。

»(2)在扩展一个节点的过程中，用于决定要生成哪一个或

哪几个后继节点，以免盲目地同时生成所有可能的节点。

A(3)用于决定某些应该从搜索树中抛弃或修剪的节点。

•启发式搜索：利用启发信息的搜索方法叫做启发

式搜索。

34

331启发式搜索策略和估价函数(续)

•估价函数(evaluationfunction):用于度量节

点的“希望”(此节点在通向目标结点的最佳路

径上的“希望”)的量度。

•记号，(〃)：表示节点n的估价函数值。

a用函数的值来排列图搜索的一般算法中

的OPEN表中节点。

A节点按递增顺序排列，即优先扩展具有低估

价值的节点，根据低估价值节点更有可能处

在最佳路径上。

35

332有序搜索

•有序搜索：应用某个算法(例如等代价法)选

择OPEN表上具有最小罐的节点作为下一个

要扩展的节点，这种搜索方法叫做有序搜索

或最佳优先搜索，其算法就叫做有序搜索算

法(orderedsearch)或最佳优先算法

(best-firstsearch)。

＞有序搜索总是选择最有希望的节点作为下一

个要扩展的节点.

36

332有序搜索(续)

•有序搜索算法：

>(1)把起始节点S放到OPEN表中，计算f(S),并把其

话与节点S联系起来。

A(2)如果OPEN表是个空表,则失败退出，无解。

A从OPEN表中选择一个f值最小的节点i,结果有

兄个节点合格，当其中有一个为目标节点时，则选

择此目标节点，否则就选择其中任一个节点作为节

点i。

>(4)把节点i从OPEN表中移出，并把它放入

CLOSED的扩展节点表中。

»⑸如果i是个目标节点，则成功退出，求得一个解,

37

332有序搜索（续）

•（6）扩展节点人生成其全部后继节点。对于/的每一个后继

节点J：

>a）计算⑪。

Ab）如果/既不在OPEN表中，也不在CLOSED表中，则用

估价函数件巴它添入OPEN表，从J加一指向父辈节点/的

指针（以便找到目标节点时记住一个解答路径）。

Ac）如果j已在OPEN表或CLOSED表上，则比较刚刚对j

计算过的，值和前面计算过的该节点在表中的，值,如果新

的，值较小，则

I,以此新值取代旧值。

II.从J指向而不是指向它的父辈节点。

川・如果节点j在CLOSED表中，则把它移回OPEN表。

•⑺转向（2）,即GOTO（2）;

38

39

332有序搜索（续）

•在有序搜索中

＞定义*/）为节点，的深度，则退化为宽度优先算法搜索。

＞定义*/）为从起始节点至节点/这段路径的代价，则退化为等代价搜索。

•估价函数的作用

＞的选择直接决定了有序搜索中被扩展节点的数目，即直接影响了搜

f索宜廷的效窣。

»对搜索结果具有决定性的作用，如果选择不合适，有序搜索就可能

吴去一个最好雨解甚至全部雨解。

•估价函数的选择，如果没有适用的准确的希望量度，那么f

的选择将涉及两个方面的内容：一方面是时间和空间之间

的折衷方案；另一方面是保证有一个最优的解或任意解。

＞一个节点处在最佳路径上的概率；

＞求出任意一个节点与目标节点集之间的距离度量或差异度量；

＞根据格局（博弈问题）或状态的特点来打分。

40

332有序搜索(续)

•例：八数码难题.设问题的初始状态S。和目标状态Sg如图所

示，定义估价函数为：g

f(n)=d(n)+W(n)

其中，d(m表示节点"在搜索树中的深度；

w(m表示节点〃中“不在位”的数码个数.

请计算初始状态So的估价函数值*So).

解：对初始节点SO,由于d(")=0,W(")=4,因此有：

"。)=4

41

283

164

75

八

数

码

难

题

有

序

搜

索

树

EXTEND42

333A*算法

•估价函数［")的定义：是从起始节点约束地通

过节点。而到达目标节点的最小代价路径的

代价的一个估计。

•估价函数的形式：

f(n)=g(n)+h(n)

其中，g(〃)是从初始节点So到节点"的实际代

价；饵小是从节点,到目标节点Sg的最优路径

的估计代价。

43

333A*算法（续）

•定义3」在GRAPHSEARCH过程中，如果步

骤（8）的重排OPEN表是依据，（。）=g（n）+h

S）进行的，则称该过程为A算法。

•说明：在图搜索的一般算法中，在搜索的每一

步都利用估价函数*m=g（m+M"）对Open表

中的节点进行排序,找出一个最有希望的节

点作为下一次扩展的节点，则该搜索算法称为

A算法。

44

333A*算法(续)

•例：八数码难题。设问题的初始状态和目标状态如

图所示，估价函数为：

f(n)=d(n)+W(n)

其中，仇〃)表示节点〃在搜索树中的深度；

表示节点"中"不在位”的数码个数。

Sg

45

333A*算法(续)

•记号：

>k(nfl；):表示任意两个节点他和之间最小

代价h路径的实际代价(对于两节点向没有通路

的节点，函数k没有定义).

>〃*m)：表示整个目标节点集合上所有

km,«)中最小的一个，即从节点"到目标节点

最优路径的实际代价。

>g*的定义:g*(n)=k(S,n)

>产的定义：f*(n)=g*(n)+h*(n)

46

333A*算法(续)

•估价函数，是"的一个估计：

f(n)=g(n)+h(n)

其中g(〃)是g*(m的估计，h(m是h*(〃)的估计。

•g(n),通常为从S到,这段路径的实际代价则

有gm)2g*m)

•h(Al)：是从节点。到目标节点Sg的最优路径的

估计代价。它的选择依赖于有关问题领域的

启发信息，叫做启发函数。例如八数码中

的W(n)。

47

333A*算法（续）

•定义3.2在A算法中，如果对所有的"存在

白（。号〃（〃）,则称以。）为白*（〃）的下界。

•定义3.3采用〃*（m的下界版。）为启发函数的

A算法，称为A*算法.当加0时,A*算法就变为

有序搜索算法。

＞说明:当定义的启发函数〃m）是h*S）的下界，

即对任意的节点,均有那么这

时的A算法就称为A*算法。

48

333A*算法(续)

•例：八数码难题.设问题的初始状态和目标状

态如前图所示，估价函数为：

f(n)=d(n)+W(n)

其中，d(O)表示节点"在搜索树中的深度；

W(")表示节点"中"不在位”的数码个数.

•d(〃)是对g*(")的一个估计，d(n)^g*(n)

•W(")是对〃*(")的一个估计

49

333A*算法(续)

•算法步骤：

•(1)才巴5放入OPEN表，记，=h,aCLOSED为空表。

•(2)重复下列过程，直至找到目标节点为止。若

OPEN为空表，则宣告失败。

•(3)选取OPEN表中未设置过的具有最小f值的节点

为最佳节点BESTNODE,并才巴它放入CLOSED表。

•(4)若BESTNODE为一目标节点，则成功求得一解。

•(5)若BESTNODE不是目标节点，则扩展之,产生后

继节点SUCCESSOR。

50

333A*算法(续)

•(6)对每个SUCCESSOR进行下列过程：

>a)建立从SUCCESSOR返回BESTNODE的指针。

Ab)计算g(SUC)=g(BES)+g(BES,SUC)O

Ac)如果SUCCESSORSOPEN,贝U称止匕节点为

OLD,并把它添至BESTNODE的后继节点表中。

Ad)比较新旧路径代价•如果g(SUC)vg(OLD),则

重新确定OLD的父辈节点为BESTNODE,记下较

小代价g(OLD),并修正，(OLD)值。

51

333A*算法(续)

•(6)对每个SUCCESSOR进行下列过程：

>e)若至OLD节点的代价较低或一样，则停止扩展节点。

Af)若SUCCESSOR不在CLOSE表中,则看其是否在

CLOSED表中。

>g)若SUCCESSOR在CLOSE表中,则转向(c);

>h)若SUCCESSOR既不在OPEN表中,又不在CLOSED

表中，则把它放入OPEN表中,并添入BESTNODE后裔表,

然后转向(7)。

•(8)GOLOOPo

52

把S放入OPEN表怎效

A

*

算

法

参

考

框

图

53

333A*算法（续）

•例1：八数码难题.定义如下两种估价函数：构

成两个A*算法和，2*。

儿S）：“不在位”的棋子数

%m）：实际走的步数（节点深度）

>42*:

h2（ny.所有棋子偏离目标位置的距离总和

n:

g2（）实际走的步数（节点深度）

则有：儿（〃）<h2（n）

54

333A*算法（续）

A*算法的特点：

若存在从初始节点So到目标节点Sg的路径,则A*

算法必能结束在最佳路径上。

>使用启发函数内（〃）的A*算法，比不使用白（n）

侪（〃）三0）的算法,求得最佳路径时扩展的节点数要

少.

>一般来说,在满足白（〃）“*（〃）的条件下,白（〃）的值越

大,说明它携带的启发性信息越多,搜索时扩展的节

点就越少,搜索效率就越高，当白m尸方*（〃）时，则不

会去扩展多余的节点就可找到解.

57

333A*算法（续）

•例2:迷宫图从入口到出口有若干条通路，求

从入口到出口处最短路径的走法。下图为一

简单迷宫示意图及其平面坐标表示。

T

出

1口

I

入

口

58

333A*算法(续)

•问题状态：物体在迷宫中的位置坐标(x,y)o

则初始状态：(1,1)目标状态：(4,4)

•操作规则(迷宫走法规定为向上、下、左、

右前进一步)

>U:上方无墙一向上走一步(x,y+1)

>D:下方无墙一向下走一步(x,y-1)

>L:左方无墙一向左走-步(x-1,y)

>R：右方无墙一向右走一步(x+1,y)

59

333A*算法(续)

•取力m)=|XG7nl+|YG・%I，g(m=

d(n),f(n)=g(n)+h(n),显然可以满足A*的

条碎。

其中，(XG,YG)为目标点坐标，(Xn,%)

为节点"的坐标。再设当不同节点的植相等

时，以深度优先排序。

60

333A*算法(续)

•例3:修道士和野人问题(M・C问题)。

状态：(m,c,b)

操作：Pij,Qij

证明h(n)=m+c-2b是满足A*条件的。

若不考虑限制条件,如果船在左岸，也就是说，船一次可

以将三人从左岸运到右岸，然后再有一个人将船送回来。

这样，船一个来回可以运过河2人，而船仍然在左岸。

而最后剩下的三个人，则可以一次将他们全部从左岸运

到右岸。则至少摆渡次数为：

m+c-3m+c—3

x2+1>-----------------x2+l=m+c-3+l=m+c-2

22

62

333A*算法(续)

•考虑船在右岸的情况。船在右岸，需要一个人将船运到左

岸。对于状态(m,c,0)来说，其所需要的最少摆渡数，

相当于船在左岸时状态(m+1,c,1)或(m,c+1,1)所需

要的最少摆渡数，再加上第一次将船从右岸送到左岸的一

次摆渡数。因此所需要的最少摆渡数为：(m+c+1)・2+1化

简有：(m+c+1)-2+1=m+Co

综合船在左岸和船在右岸两种情况下，所需要的最少

摆渡次数用一个式子表示为：m+c-2bo其中b=1表示船

在左岸，b=0表示M•在右岸。

由于该摆渡次数是在不考虑限制条件下，推出的最少

所需要的摆渡次数。因此，当有限制条件时，最优的摆渡

次数只能大于等于该摆渡次数。所以该启发函数h是满足

A*条件的。

•定义估价函数，(")=g(n)+h(n),其中g(")=d(n),h(n)=

n?+c-2b63

333A*算法

(3,3,1)(0,0,0)

65Pi5

(3,2,0)(2,2,0)I(34,0)(0,2,1)(1,1,1)

Qni

5

6(3,2,1)(0,1,0)

(3,0,0)69

7(344)"(«44)

(1,1,0)Q01

89

(2,2,1)(0,2,0)

64

•M・C问题的A*算注岫

334

•准则

>1>完备性：有解时能否保证找到解

A2、最优性：如果问题存在多个解，那么利用该

搜索策略一定能够找到最优解。

A3、时间复杂度：根据搜索过程中产生的节点数

目来度量

A4、空间复杂度：在执行搜索的过程中需要的内

存，取决于储存的最大节点数。

•时间与空间的复杂度往往要与问题难度的某种度

量一起考虑

65

334（续）

•问题难度的度量

时间与空间的复杂度往往要与问题难度的某种度

量一起考虑（状态空间图的大小）

»平均分支因子b：节点的后继节点的平均个数

>d：最浅的目标节点的深度（解深度）

>m：状态空间中任何路径的最大深度

66

334（续）

•宽度优先搜索

＞当b有限时，搜索是完备的

＞从寻找最短路径的解（或深度最浅的解）的意义

上最优

＞时间复杂度：0附（b：平均分枝因子，d：解

深度）

»空间复杂度：O（bd）（b：平均分枝因子，d：解

深度）

67

334（续）

•深度优先搜索

＞不完备

A非最优

＞时间复杂度：0句）（b：平均分枝因子，m：

状态空间的最大深度）

»空间复杂度：0付可（b：平均分枝因子，m：

状态空间的最大深度）

68

334（续）

•含有深度界限的深度优先搜索

＞当INd时完备（I：深度限，d：解深度）

A非最优

＞时间复杂度：0（H）（b：平均分枝因子，I：深

度限）

»空间复杂度：O（bl）（b：平均分枝因子，I：深

度限）

69

334（续）

•等代价搜索

＞完备

＞从寻找到根结点代价最小路径的解的意义上最优

＞时间复杂度：0附（b：平均分枝因子，d：解

深度）

»空间复杂度：O（bd）（b：平均分枝因子，d：解

深度）

70

334（续）

•有序搜索

＞不完备

＞不优化

＞时间复杂度：0俨）（b：平均分枝因子，m：

状态空间的最大深度）

71

334（续）

•A*算法

A完备

A优化

＞时间复杂度：0附（b：平均分枝因子，d：解

深度）

＞在内存空间中保存了所有的节点

•A*也称为最佳图搜索算法

72

3・4博弈树搜索

•3.4.1博弈问题概述

•3,4.2极小极大分析法

•343a・B搜索过程

73

3.4.1博弈问题概述

•如下棋、打牌、竞技、战争等一类竞争性智能活动称为博

弈。博弈有很多种，我们讨论最简单的“二人零和、全信

息、非偶然”博弈，其特征如下：

>（D双人对弈，对垒的双方轮流走步。

>（2）信息完备，对垒双方所得到的信息是一样的，不存

在一方能看到，而另一方看不到的情况。

>（3）零和。即对一方有利的棋，对另一方肯定是不利的,

不存在对双方均有利、或均无利的棋。对弈的结果是一方

赢，而另一方输，戢者双方和棋。

>（4）任何一方在采取行动前都要根据当前的实际情况，

进行得失分析，选取对自己为最有利而对对方最为不利的

对策，不存在掷骰子之类的“碰运气”因素。即双方都是很

理智地决定自己的行动。

74

3.4.1博弈问题概述（续）

•博弈树搜索与状态空间搜索的区别

＞由机器完全控制结点的扩展，到由博弈双方分别控制

＞每一步操作后的结果不可预测

由于对手的操作带来不确定性：机器无从知道对方将会如何操

作

对手总是试图给对方带来不便

＞在实际使用中的一些其它问题

特别大的状态空间

国际象棋：

果平均分枝因子：35

枭每盘棋每方平均走棋：50步

堇状态空间大小：351。。（1040不同的合法的状态）

每一次搜索均有时间的限制

对搜索的结果要求更高

75

3.4.1博弈问题概述（续）

•博弈问题的知识表示

在博弈过程中，任何一方都希望自己取得胜利。因此，

当某一方当前有多个行动方案可供选择时，他总是挑选对

自己最为有利而对对方最为不利的那个行动方案。

如果我们站在MAX方的立场上，则可供MAX方选择

的若干行动方案之间是“或”关系，因为主动权操在

MAX方手里，乱或者选择这个行动方案，或者选择另一

个行动方案，完全由MAX方自己决定。

当MAX方选取任一方案走了一步后，MIN方也有若干

个可供选择的行动方案，此时这些行动方案对MAX方来

说它们之间则是“与“关系，因为这时主动权操在MIN方手

里，这些可供选择的行动方案中的任何一个都可能被MIN

方选中，MAX方必须应付每一种情况的发生。

这样，如果站在某一方（如MAX方，即MAX要取胜），

把上述博弈过程用图表示出来，则得到的是一棵“与或树,

描述博弈过程的与或树称为博弈树76

3.4.1博弈问题概述(续)

•博弈树的特点

(1)博弈的初始格局是初始节点。

(2)在博弈树中，“或“节点和“与“节点是逐层交替出

现的。自己一方扩展的节点之间是“或“关系，对方扩展的

节点之间是“与“关系。双方轮流地扩展节点。

(3)所有自己一方获胜的终局都是本原问题，相应的

节点是可解节点；所有使对方获胜的终局都认为是不可解

节点。

假定MAX先走，处于奇数深度级的节点都对应下一

步由MAX走，这些节点称为MAX节点，相应地偶数级为

MIN节点。

77

3.4.1博弈问题概述（续）

•问题空间模型化

四元组：（初始状态，操作集合，终止测试（非

目标测试），判定函数）

以下棋为例：

A初始状态：棋的开局

A操作集合：下棋的规则

＞终止测试：如果以输、赢、和局为下棋的终止，

终止测试代表对输、赢、和局的判定

＞判定函数：通过它可以估计每一种状态下输、赢、

和局的可下丈小（比如：可以表示输，0表示和

局，1表示赢）

78

3.4.1博弈问题概述(续)

•例：分钱币问题

有一堆数目为N的钱币，由两位选手(MAX,MIN)轮流进行

分堆，要求每个选手每次只把其中某一堆分成数目不等的

两小堆。例如选手甲把N分成两堆后，轮到选手乙就可以

挑其中一堆来分，如此进行下去直到有一位选手先无法把

钱币再分成不相等的两堆时就得认输。

用无序数字序列x1,x2,…，Xn表示n堆钱币不同的个数，

再用两个说明符号代表选手，无序数列和符号M组合(x1,

x2,…，Xn，M)就代表由某个选手走步的状态。

初始状态：(7,MIN)

规则：if(x1,xn,M)A(Xj=y+z,y#z)

then(x1,・・・，xh1,y,z,xi+1,xn,M)

79

3.4.1博弈

•分钱币问题状态(7,MIN)

空间图

图中所有终节点(6,l.MAX)⑸2,MAX)(4,3,MAX)

均表示该选手必

输的情况，取胜(5,1,1,MIN)(4,2,1,MIN)(3,2,2,MIN)⑸3,1,MIN)

方的目标是设法

使棋局发展为结

束在对方走步时(4,1,1,1,MAX)(3,2,1,1,MAX)⑵2,2,1,MAX)B

的终节点上，因

此节点A是MAX(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)A

的搜索目标，而

节点B,C则为

MIN的搜索目标。⑵1,1,1，1,MAX)C

3.4.1博弈问题概述（续）

•分钱币问题

寻找MAX的取胜策略便和求与或图的解图一

致起来，即MAX要取胜，必须对所有与节点取

胜，但只需对一个或节点取胜，这就是一个解

图。因此实现一种取胜的策略就是搜索一个解

图的问题，解图就代表一种完整的博弈策略。

81

3.4.1博弈问题概述（续）

•对于分钱币问题这种较简单的博弈，或者复杂博弈的残

局，可以用类似于与或图的搜索技术求出解图，解图代

表了从开局到终局任何阶段上的弈法。但是这对许多博

弈问题是不可能实现的。

•完全取胜策略（或和局）必须丢弃，而应当把目标确定

为寻找一步好棋，等对手回敬后再考虑寻找另一步好棋

这种实际可行的实用策略。这种情况下每一步结束条件

可根据时间限制、存储空间限制或深度限制等因素加以

确定。搜索策略可采用宽度、深度或启发式方法，一个

阶段搜索结束后，要从搜索树中提取一个优先考虑的”

最好的”走步，这就是实用策略的基本点。

82

3.4.2极小极大分析法

•基本思想

＞首先假定，有一个评价函数可以对所有的棋局

进行评估。当评价函数值大于o时，表示棋局对

我方有利，对对方不利。当评价函数小于。时，

表示棋局对我方不利，对对方有利。而评价函

数值越大，表示对我方越有利。当评价函数值

等于正无穷大时，表示我方必胜。评价函数值

越小，表示对我方越不利。

＞当评价函数值等于负无穷大时，表示对方必胜。

假设双方都是对弈高手，在只看一步棋的情况

下，我方一定走评价函数值最大的一步棋，而

对方一定走评彳介函薮值最小的一步棋。

83

3.4.2极4心大分析法（续）

＞极小极大搜索方法

当轮到我方走棋时，首先按照一定的搜索深度

生成出给定深度d以内的所有状态，计算所有叶

节点的评价函数值。然后从d・1层节点开始逆向

计算：对于我方要走的节点（用MAX标记，称

为极大节点）取其子节点中的最大值为该节点

的值（因为我方总是选择对我方有利的棋）；

对于对方要走的节点（用MIN标记，称为极小节

点）取其子节点中的最小值为该节点的值（对

方总是选择对我方不利的棋）。一直到计算出

根节点的值为止。获得根节点取值的那一分枝，

即为所选择的最佳走步。

84

3.4.2极＜J加大分析法（续）

•算法框架

整个算法分为四个步骤：

＞1＞以当前状态为根结点产生一个博弈树。

A2、对博弈树的每一个叶结点，利用判定函数给

出它的判定值。

A3、从叶结点开始，一层一层地回溯。在回溯过

程中，利用最大/最小判定为每一个结点给出其

判定值。

A4、MAX方选择下一层中判定值最大的结点，作

为它的下一状态。

85

3.4.2极小极大分析法（续）

例

86

3.4.2极4加大分析法（续）

•例一字棋游戏

＞设有九个空格，由MAX,MIN二人对弈，轮到谁

走棋谁就往空格上放一只自己的棋子，谁先使自

己的棋子构成“三子成一线”（同一行或列或对角

线全是某人的棋子），谁就取得了胜利。

A设程序方MAX的棋子用（X）表示，对手MIN的

棋子用（O）表示，MAX先走。

87

3.4.2极4心大分析法（续）

・静态估计函数f（p）规定如下：

＞若P对任何一方来说都不是获胜的格局，

贝肝（p）=（所有空格都放上MAX的棋子之后，

MAX的三子成线（行、歹U、对角）的总数一（所

有空格都放上MIN的棋子之后，MIN的三子成线

（行、歹U、对角）的总数）

»若p是MAX获胜的格局，贝什（p）=oo；

»若p是MIN获胜的格局，贝肝（p）=—3

当p的格局如图时，则可得f（p）=6-4=2；

假定具有对称性的两个棋局算作一个棋局

3.4.2极小极大分析法（续）

#0#O

第——_—~~

衣Rx@x|Q|x|Q|乂6_x|p|。MAX的走步

O冈冈区区-池冈

dnIdnoni

4-2=23-2=15-2=33-1=24-2=2

阶

段4。

4-3=13-3=05-3=23-3=04-3=14-3=1_卜一；MIN

搜

-

索..z

xX又XoX

树4-2=24-2=25-2=33-2=14-2=24-2=2

*#i

4-3=14-3=13-3=0

MAX

3.4.3af搜索过程

•在极小极大搜索方法中，由于要先生成指定深度

以内的所有节点，其节点数将随着搜索深度的增

加承指数增长。这极大地限制了极小极大搜索方

法的使用。

•剪枝的基本思想：

边生成博弈树边计算评估各节点的倒推值，并且

根据评估出的倒推值范围，及时停止扩展那些已

无必要再扩展的子节点，即相当于剪去了博弈树

上的一些分枝，从而节约了机器开销，提高了搜

索效率。

92

3.4.3af搜索过程（续）

•算法框架

>（1）对于一个与节点MIN,若能估计出其倒推值的上确界,

并且这个B值不大于MIN的父节点（一定是或节点）的估计

倒推值的下确界a,BPa>p,则就不必再扩展该MIN节点

的其余子节点了（因为这些节点的估值对MIN父节点的倒推

值已无任何影响）。这一过程称为a剪枝。

>（2）对于一个或节点MAX,若能估计出其倒推值的下确界

a,并且这个a值不小于MAX的父节点（一定是与节点）的

估计倒推值的上确界B，即aNB，则就不必再扩展该MAX

节点的其余子节点了（因为这些节点的估值对MAX父节点

的倒推值已无任何影响）。这一过程称为B剪枝。

93

3・4・3。手搜索过程(续)

■算法特点：

(1)MA节点(包括起始节点)的a值永不减少；

(2)MIN节点(包括起始节点)的0值永不增加。

•a和B值的计算方法：

(1)一个MAX节点的a值等于其后继节点当前最大

的最终倒推值。

(2)一个MIN节点的0值等于其后继节点当前最小的

最终倒推值。

94

3.4.3a-|i搜索过程（续）

字棋第一阶段a・B剪枝方法

95

3・4・3。手搜索过程(续)

•注意问题：

>(1)比较都是在极小节点和极大节点间进行的，极大节点和极大节

点的比较，或者极小节点和极小节点间的比较是无意义的。

>(2)在比较时注意是与“先辈层”节点比较，不只是与父辈节点比

较。当然，这里的“先辈层”节点，指的是那些已经有了值的节点。

>(3)当只有一个节点的“固定”以后，其值才能够向其父节点传递。

>(4)剪枝方法搜索得到的最佳走步与极小极大方法得到的结果是

一致的，剪枝并没有因为提高效率，而降低得到最佳走步的可能

性。

>(5)在实际搜索时，并不是先生成指定深