第三章 AI搜索原理oommtt
第三章搜索原理
搜索的概念以及分类
搜索是人工智能中的基本问题
搜索的概念
根据问题的实际情况，按照一定的策略或者规划，从知识库中寻找可以利用的知识，从而构造出一条使得问题获得解决的推理路线的过程
搜索的两层含义
要找到从初始事实到问题最终答案的一条推理路线
找到的这条路线是时间和空间复杂度最小的求解路线
搜索的种类
搜索可以分为盲目搜索和启发式搜索两种
盲目搜索
又称为无信息搜索。也就是在搜索的过程中只按预先的搜索控制策略进行搜索，而没有任何中间信息来改变这些控制策略
启发式搜索
称为有信息搜索。它是指在问题搜索过程中，根据问题本身的特征或者搜索过程中产生出来的一些信息来不断地改变或者调整搜索方向，使搜索朝着最有希望的方向前进，加速问题的求解，并找到最优解。
4
一般图搜索
宽度优先搜索
深度优先搜索
代价树搜索
盲目搜索
5
基本思想
先把问题的初始状态作为当前扩展节点对其进行扩展，生成一组子节点，然后检查问题的目标状态是否出现在这些子节点中。若出现，则搜索成功，找到了问题的解；若没出现，则再按照某种搜索策略从已生成的子节点中选择一个节点作为当前扩展节点。重复上述过程，直到目标状态出现在子节点中或者没有可供操作的节点为止。
扩展:所谓对一个节点进行“扩展”是指对该节点用某个可用操作进行作用，生成该节点的一组子节点。
一般图搜索
算法的数据结构和符号约定
Open表：用于存放刚生成的节点
Closed表：用于存放已经扩展或将要扩展的节点
S：用表示问题的初始状态
G：表示搜索过程所得到的搜索图
M：表示当前扩展节点新生成的且不为自己先辈的子节点集。
一般图搜索
7
开始
把S放入OPEN表，加入图G中,CLOSED表置空
OPEN表为空表？
把第一个节点(n)从OPEN表移至CLOSED表
扩展节点n的子节点;非n先辈子节点记入集合M，并加入G图中
修改指向父节点指针
重排OPEN表
失败
成功
是
是
否
否
设置父节点，放入Open表
节点在G中
节点不在G中
n为目标节点吗？
8
一般图搜索过程
(1) 把初始节点S放入Open表，并建立目前仅包含S的图G；
(2)建立一个叫Closed的已扩展节点表，其初始为空表；
(3) 检查Open表是否为空，若为空，则问题无解，失败推出；
(4) 把Open表的第一个节点取出放入Closed表，并记该节点为节点n；
(5)考察节点n是否为目标节点。若是则得到了问题的解，成功退出；
(6) 扩展节点n，生成一组子节点，若无子节点直接转第(7)步。把这些子节点中不是节点n先辈的那部分子节点记入集合M，并把这些子节点作为节点n的子节点加入G中
(7) 针对M中子节点的不同情况，分别作如下处理：
①对那些没有在G中出现过的M成员设置一个指向其父节点（即节点n）的指针，并把它放入Open表。（新生成的）
②对那些原来已在G中出现过，确定是否需要修改它指向父节点的指针。
(8) 按某种策略对Open表中的节点进行排序。
(9) 转第(2)步。
例：按照一般图搜索策略求解下图从S节点到H节点的解路径。
一般图搜索
Open表：
Closed表：
一般图搜索
S
A
B
D
C
E
E
F
H
D
G图：
一般图搜索
12
算法的几点说明：
(1) 上述过程是状态空间的一般图搜索算法，它具有通用性，后面所要讨论的各种状态空间搜索策略都是上述过程的一个特例。
(2)各种搜索策略的主要区别在于对Open表中节点的排列顺序不同。
例如，广度优先搜索把先生成的子节点排在前面，而深度优先搜索则把后生成的子节点排在前面。
一般图搜索
13
(3) 在第(6)步对节点n扩展后，生成并记入M的子节点有以下两种情况：
①该子节点来从未被任何节点生成过，由n第一次生成；
②该子节点原来被其他节点生成过，这一次又被n再次生成；
以上两种情况是对一般图搜索算法而言的。
状态空间图，与或图是树状结构，因此不会出现后种情况，每个节点经扩展后生成的子节点都是第一次出现的节点，不必检查并修改指向父节点的指针。
一般图搜索
14
(4) 在第(7)步针对M中子节点的不同情况进行处理时，如果发生当第②种情况，那么，这个M中的节点究竟应该作为哪一个节点的后继节点呢？
一般是由原始节点到该节点路径上所付出的代价来决定的，哪一条路经付出的代价小，相应的节点就作为它的父节点。所谓由原始节点到该节点路径上的代价是指这条路经上的所有有向边的代价之和。
一般图搜索
15
(5) 在搜索图中，除初始节点外，任意一个节点都含有且只含有一个指向其父节点的指针。因此，由所有节点及其指向父节点的指针所构成的集合是一棵树，称为搜索树。
(6) 在搜索过程的第(5)步，一旦某个被考察的节点是目标节点，则搜索过程成功结束。由初始节点到目标节点路径上的所有操作就构成了该问题的解，而路径由第(7)步所形成的指向父节点的指针来确定。
(7) 如果搜索过程终止在第(3)步，即没有达到目标，且Open表中已无可供扩展的节点，则失败结束。
一般图搜索
16
宽度优先搜索
开始
把S放入OPEN表
OPEN表为空表？
把第一个节点(n)从OPEN表移至CLOSED表
扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针
失败
是
否
n为目标节点吗？
成功
否
是
n可扩展？
否
是
18
搜索算法
(1)把初始节点S放入Open表中；
(2)如果Open表为空，则问题无解，失败退出；
(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4)考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
(5)若节点n不可扩展，则转第(2)步；
(6)扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。
宽度优先搜索
19
例：
八数码难题（8-puzzle problem）
（初始状态）
规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。
宽度优先搜索
20
1
21
算法的几点说明：
(1) 宽度优先搜索是图搜索一般过程的特殊情况。
将一般图搜索过程中的过程(8)具体为本算法中的过程(6),实际是将Open表作为“先进先出”的队列进行操作。
(2)宽度优先搜索能够保证在搜索树中找到一条通向目标节点的最短路径。
这棵树提供了所有存在的路径。如果没有路径存在，对有限图来说，则该法失败退出；对无限图来说，永远不会终止。
宽度优先搜索
22
算法评价
(1)对于有限图，宽度优先搜索方法必能找到解；
（2）时间复杂度（很高）
其中d为搜索树的深度，b为树的平均分支数，m为搜索到解的深度。
（3）空间复杂度（很高）
宽度优先搜索
bm
O(bm)
23
深度优先搜索
定义
首先扩展最新产生的(即最深的)节点。
特点
搜索效率高，尽可能先对纵深方向进行搜索。
基本思想
从初始节点S开始，在其子节点中选择一个最新生成的节点进行考察，如果该子节点不是目标节点且可以扩展，则扩展该子节点，然后再在此子节点的子节点中选择一个最新生成的节点进行考察，依此向下搜索，直到某个子节点既不是目标节点，又不能继续扩展时，才选择其兄弟节点进行考察。
开始
把S放入OPEN表
OPEN表为空表？
把第一个节点(n)从OPEN表移至CLOSED表
扩展n，把n的后继节点放入OPEN表的首端，提供返回节点n的指针
失败
是
否
n为目标节点吗？
成功
否
是
n可扩展？
否
是
25
算法描述
(1) 把初始节点S放入Open表中；
(2) 如果Open表为空，则问题无解，失败退出；
(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，将其子节点放入Open表的首部，并为每一个子节点设置指向父节点的指针，然后转第(2)步。
深度优先搜索
1
例八数码难题
27
算法评价
(1)对于有限图，深度优先搜索方法必能找到解；
（2）时间复杂度（很高）
其中d为搜索树的深度，b为树的平均分支数
（3）空间复杂度（很高）
深度优先搜索
d*b
最坏情况下的搜索树
O(bd)
28
一种改进的深度优先算法是有界深度优先搜索算法，深度限制为dm
29
算法评价
(1)对于有限图，改进深度优先搜索方法必能找到解；
（2）时间复杂度
（3）空间复杂度
改进深度优先搜索
m*b
O(bm)
30
在代价树中，可以用g(n)表示从初始节点S到节点n的代价，用c(n1, n2)表示从父节点n1到其子节点n2的代价。这样，对节点n2的代价有：g(n2)=g(n1)+c(n1, n2)。代价树搜索的目的是为了找到最佳解，即找到一条代价最小的解路径。
代价树搜索
定义：
在搜索树中定义每条连接弧线上的有关代价,表示时间、距离等花费。沿着代价从小到大进行节点的扩充搜索。
分为代价树宽度优先搜索和代价树深度优先搜索。
31
代价树的广度优先搜索算法：（P197）
(1) 把初始节点S放入Open表中，置S的代价g(S)=0；
(2) 如果Open表为空，则问题无解，失败退出；
(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4) 考察节点n是否为目标。若是，则找到了问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，生成其子节点ni(i=1, 2, …)，将这些子节点放入Open表中，并为每一个子节点设置指向父节点的指针。按如下公式：
g(ni)=g(n)+c(ni) i=1,2,...
计算各子结点的代价，并根据各子结点的代价对Open表中的全部结点按由小到大的顺序排序。然后转第(2)步。
代价树搜索-宽度优先
32
例：城市交通问题。设有5个城市，它们之间的交通线路如左图所示，图中的数字表示两个城市之间的交通费用，即代价。用代价树的宽度优先搜索，求从A市出发到E市，费用最小的交通路线。
城市交通图
解：代价树如右图所示。其中，红线为最优解，其代价为8
城市交通图的代价树
33
代价树的深度优先搜索算法：
(1) 把初始节点S0放入Open表中，置S0的代价g(S0)=0；
(2) 如果Open表为空，则问题无解，失败退出；
(3) 把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4) 考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；
(5) 若节点n不可扩展，则转第(2)步；
(6) 扩展节点n，生成其子节点ni(i=1, 2, …)，将这些子节点按边代价由小到大放入Open 表的首部，并为每一个子节点设置指向父节点的指针。然后转第(2)步。
代价树搜索-深度优先
34
启发性信息和估价函数
A算法
A*算法
启发式搜索
35
启发性信息的概念：
启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。
启发性信息的种类：
①有效地帮助确定扩展节点的信息；
②有效的帮助决定哪些后继节点应被生成的信息；
③能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。
启发性信息的作用：
启发信息的启发能力越强，扩展的无用结点越少。
启发性信息
36
估价函数用来估计节点重要性的函数。估价函数f(n)被定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。它的一般形式为：
f(n)=g(n)+h(n)
其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。
估价函数
例八数码难题。设问题的初始状态S0和目标状态Sg如下图所示。估价函数为
f(n)=d(n)+W(n)
其中：d(n)表示节点n在搜索树中的深度
W(n)表示节点n中“不在位”的数码个数。
请计算初始状态S0的估价函数值f(S0)
估价函数
Sg
S0
解：取g(n)=d(n)，h(n)=W(n)。它说明是用从S0到n的路径上的单位代价表示实际代价，用结点n中“不在位”的数码个数作为启发信息。
一般来说，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。
对初始节点S0，由于d(S0)=0，W(S0)=3，因此有
f(S0)=0+3=3
39
定义：在一般图搜索算法中，如果第(8)步的重排OPEN表是利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则该搜索算法为A算法。
由于估价函数中带有问题自身的启发性信息，因此，A算法也被称为启发式搜索算法。A算法
40
A算法分类：
可根据搜索过程中选择扩展节点的范围，将启发式搜索算法分为全局择优搜索算法和局部择优搜索算法。
全局择优：从Open表的所有节点中选择一个估价函数值最小的一个进行扩展。
局部择优：仅从刚生成的子节点中选择一个估价函数值最小的一个进行扩展。
一般解决问题采用全局择优方法选取扩展节点
A算法
41
开始
把S放入OPEN表，计算估价函数f (s)
OPEN表为空表？
选取OPEN表中f值最小的节点n放入CLOSED表
n为目标节点吗？
扩展n，得后继节点ni，计算f(ni)，提供返回节点ni的指针，利用f(ni)对OPEN表重新排序，调整亲子关系及指针
失败
成功
是
否
否
42
全局择优搜索A算法描述：
(1)把初始节点S放入Open表中，f(S)=g(S)+h(S)；
(2)如果Open表为空，则问题无解，失败退出；
(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；
(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；
(5)若节点n不可扩展，则转第(2)步；
(6)扩展节点n，生成其子节点ni(i=1, 2, …)，计算每一个子节点的估价值f(ni)(i=1, 2, …)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；
(7)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；
(8)转第(2)步。
A算法
43
例子
八数码难题（8-puzzle problem）
（目标状态）
（初始状态）
八数码难题的有序搜索树见下图：
44
1
4
5
6
3
2
（4）
A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法假设f*(n)是从初始节点出发，经过节点n达到目标节点的最小代价，估价函数f(n)是对f*(n)的估计值。且
f*(n)=g*(n)+h*(n)
A*算法对A算法（全局择优的启发式搜索算法）中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；
第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)≤h*(n)。
即满足上述两条限制的A算法称为A*算法。
A*算法
46
A*算法
A*算法说明：
（1）可纳性
对任一状态空间图，当从初始节点到目标节点有路径存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A*算法具有可纳性。
（2）最优性
A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说，在满足h(n) ≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。
47
A*算法
（3）h(n)的单调限制
在A*算法中，每当扩展一个节点n时，都需要检查其子节点是否已在Open表或Closed表中。
如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述检查
为满足这一要求，我们需要对启发函数h(n)增加单调性限制。
定义如果启发函数满足以下两个条件:
(1) h(Sg)=0;
(2) 对任意节点ni及其任一子节点nj，都有
0≤h(ni)-h(nj)≤c(ni, nj)
其中c(ni, nj)是ni到其子节点nj的边代价，则称h(n)满足单调限制。
48
例八数码难题。
2 8 3
1 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
1 2 3
8 4
7 6 5
1 2 3
6 5
1 2 3
8 4
7 6 5
S0
f=6 g*=1h*=3 f=6 f=6
g*=2 h*=2 f=6
f=4
g*=3 h*=1
f=4
g*=4 h*=0
f=4
f=6
Sg
八数码难题h(n)=P(n)的搜索树
f(n)=d(n)+P(n)
d(n) 深度
P(n)与目标距离
显然满足
P(n)≤h*(n)
即f*=g*+h*
f=4
h*=4 f=4
49
例修道士和野人问题。
设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去? 用A*搜索求解，画出搜索树，并标注解路径。A*算法
50
解：首先选取描述问题状态的方法。在这个问题中，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸。从而可用一个三元组来表示状态
S=(m, c, b)
其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。
右岸的状态可由下式确定：
右岸修道士数m'=3-m
右岸野人数c'=3-c
右岸船数b'=1-b
在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32种状态。
A*算法
51
这32种状态并非全有意义，除去不合法状态和修道士被野人吃掉的状态，有意义的状态只
S0=(3, 3, 1) S1=(3, 2, 1) S2=(3, 1, 1) S3=(2, 2, 1)
S4=(1, 1, 1) S5=(0, 3, 1) S6=(0, 2, 1) S7=(0, 1, 1)
S8=(3, 2, 0) S9=(3, 1, 0) S10=(3, 0, 0) S11=(2, 2, 0)
S12=(1, 1,0) S13=(0, 2, 0) S14=(0, 1, 0) S15=(0, 0, 0)
有了这些状态，还需要考虑可进行的操作。
A*算法
52
操作是指用船把修道士或野人从河的左岸运到右岸，或从河的右岸运到左岸。
每个操作都应当满足如下条件：
（1）船至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；
（2）每次操作船上人数不得超过2个；
（3）操作应保证不产生非法状态。
因此，操作应由条件部分和动作部分：
条件：只有当其条件具备时才能使用
动作：刻划了应用此操作所产生的结果。
A*算法
53
操作的表示：
用符号Pij表示从左岸到右岸的运人操作
用符号Qij表示从右岸到左岸的操作
其中：
i表示船上的修道士人数
j表示船上的野人数
操作集
本问题有10种操作可供选择：
F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20}
下面以P01和Q01为例来说明这些操作的条件和动作。
操作符号条件动作
P01 b=1, m=0或3, c≥1 b=0, c=c-1
Q01 b=0, m=0或3，c≤2 b=1, c=c+1
54
对A*算法，首先需要确定估价函数。
设g(n)=d(n)，h(n)=m+c-2b，则有
f(n)=g(n)+h(n)=d(n)+m+c-2b
其中，d(n)为节点的深度。通过分析可知h(n)≤h*(n)，满足A*算法的限制条件。
M-C问题的搜索过程如下图所示。
A*算法
55
(3,3,1) h=4 f=4
(3,2,0) (3,1,0) (2,2,0)
(3,2,1)
(2,1,0) (3,0,0)
(2,2,1) (3,1,1)
(0,2,0) (1,1,0)
(0,3,1)
(0,1,0)
(0,2,1)
(0,0,0)
h=5 f=6
h=3 f=5
h=3 f=6 h=3 f=6
h=2 f=6
h=2 f=7
h=1 f=7
h=1 f=8
h=0 f=8
传教士和野人问题的搜索图
问题状态：(m,c,b)
估价函数：h(n)=m+c-2b
h=4 f=5
h=4 f=5
h=2 f=6
h=2 f=7
F={P01, P10, P11, P02, P20,Q01, Q10, Q11, Q02, Q20}
56
与/或树的盲目搜索
与/或树的启发式搜索
与/或树搜索
与/或树
可解节点
该节点是一个终止节点
该节点是一个“或”节点，且其子节点中至少有一个为可解节点
该节点是一个“与”节点，且其子节点全部为可解节点
不可解节点
该节点是一个端节点，但却不是终止节点
该节点是一个“或”节点，但其子节点中没有一个是可解节点
该节点是一个“与”节点，且其子节点中至少有一个为不可解节点
与/或树
59
与/或树的宽度优先搜索与状态空间的宽度优先搜索的主要差别是，在搜索过程中需要多次调用可解标识过程或不可解标识过程。
其搜索算法如下：
(1)把初始节点S0放入Open表中；
(2)把Open表的第一个节点取出放入Closed表，并记该节点为n；
(3)如果节点n可扩展，则做下列工作：
①扩展节点n，将其子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针；
与/或树的宽度优先搜索
60
②考察这些子节点中是否有终止节点。若有，则标记这些终止节点为可解节点，并用可解标记过程对其父节点及先辈节点中的可解解节点进行标记。如果初始解节点S0能够被标记为可解节点，就得到了解树，搜索成功，退出搜索过程；如果不能确定S0为可解节点，则从Open表中删去具有可解先辈的节点。
③转第(2)步。
(4) 如果节点n不可扩展，则作下列工作：
①标记节点n为不可解节点；
②应用不可解标记过程对节点n的先辈中不可解的节点进行标记。如果初始解节点S0也被标记为不可解节点，则搜索失败，表明原始问题无解，退出搜索过程；如果不能确定S0为不可解节点，则从Open表中删去具有不可解先辈的节点。
③转第(2)步。
61
例设有下图所示的与/或树，节点按标注顺序进行扩展，其中标有t1、t2、t3的节点是终止节点，A、B、C为不可解的端节点，通过宽度优先搜索算法计算此与或树是否有解存在？1
2 3
A 4 t1 5
t2 B t3 C
与/或树的宽度优先搜索
62
搜索过程为：
(1) 先扩展1号节点，生成2号节点和3号节点。
(2) 扩展2号节点，生成A节点和4号节点。
(3) 扩展3号节点，生成t1节点和5号节点。由于t1为终止节点，则标记它为可解节点，并应用可解标记过程，不能确定3号节点是否可解。
(6) 扩展5号节点，生成t3节点和C节点。由于t3为终止节点，则标记它为可解节点，并应用可解标记过程，可标记1号节点为可解节点。
(7) 搜索成功，得到由1、2、3、4、5号节点即t1、t2、t3节点构成的解树。
(4) 扩展节点A，由于A是端节点，因此不可扩展。调用不可解标记过程…。
(5) 扩展4号节点，生成t2节点和B节点。由于t2为终止节点，则标记它为可解节点，并应用可解标记过程，可标记2号节点为可解，但不能标记1号节点为可解。
63
与/或树的启发式搜索通常称为AO*算法，与/或树的启发式搜索是AO*算法在与/或树上应用的特殊过程。
与/或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。
算法的每一步都试图找到一个最有希望成为最优解树的子树。
最优解树是指代价最小的那棵解树。
它涉及到解树的代价与希望树。
与/或树的启发式搜索
64
解树的代价可按如下规则计算：
(1)若n为终止节点，则其代价h(n)=0；
(2)若n为或节点，且子节点为n1, n2, …,nk，则n的代价为：
其中，c(n, ni)是节点n到其子节点ni的边代价。
(3)若n为与节点，且子节点为n1, n2, …,nk，则n的代价可用和代价法或最大代价法。
若用和代价法，则其计算公式为：
若用最大代价法，则其计算公式为：
(4)若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为h(n)=∝。
(5)根节点的代价即为解树的代价。
与/或树的启发式搜索
65
例设下图是一棵与/或树，它包括两颗解树，左边的解树由S0、A、t1、C及t2组成；右边的解树由S0、B、t2、D及t4组成。在此与或树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。
解：先计算左边的解树
按和代价：h(S0)=2+4+6+2=14
按最大代价：h(S0)=(2+6)+2=10
再计算右边的解树
按和代价：h(S0)=1+5+3+2=11
按最大代价：h(S0)=(1+5)+2=8
S0
2
A B
t1 C t2 D
t3 E t4 F
与/或树的代价
2
4
6
2
3
1
5
66
希望树是指搜索过程中最有可能成为最优解树的那棵树。
与/或树的启发式搜索过程就是不断地选择、修正希望树的过程，在该过程中，希望树是不断变化的。
定义希望解树
(1) 初始节点S0在希望树T
(2) 如果n是具有子节点n1, n2, …, nk的或节点，则n的某个子节点ni在希望树T 中的充分必要条件是
(3) 如果n是与节点，则n的全部子节点都在希望树T中。
与/或树的启发式搜索
67
与/或树的启发式搜索过程如下：
(1) 把初始节点S0放入Open表中，计算h(S0)；
(2) 计算希望树T；
(3) 依次在Open表中取出T的末节点放入Closed表，并记该节点为n；
(4)如果节点n为终止节点，则做下列工作：
①标记节点n为可解节点；
②在T上应用可解标记过程，对n的先辈节点中的所有可解解节点进行标记；
③如果初始解节点S0能够被标记为可解节点，则T就是最优解树，成功退出；
④否则，从Open表中删去具有可解先辈的所有节点。
⑤转第(2)步。
与/或树的启发式搜索
68
(5) 如果节点n不是终止节点，但可扩展，则做下列工作：
①扩展节点n，生成n的所有子节点；
②把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针
③计算这些子节点及其先辈节点的h值；
④转第(2)步。
(6) 如果节点n不是终止节点，且不可扩展，则做下列工作：
①标记节点n为不可解节点；
②在T上应用不可解标记过程，对n的先辈节点中的所有不可解解节点进行标记；
③如果初始解节点S0能够被标记为不可解节点，则问题无解，失败退出；
④否则，从Open表中删去具有不可解先辈的所有节点。
⑤转第(2)步。
例
要求搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。它实际上就是下一节将要讨论的博弈树的结构。
设初始节点为S0，对S0扩展后得到的与/或树如右图所示。其中，端节点B、C、E、F，下面的数字是用启发函数估算出的h值，节点S0、A、D旁边的数字是按和代价法计算出来的节点代价。
此时，S0的右子树是当前的希望树。
S0
8
A
8
D
7
B
E
F
3
3
3
2
h(n)=c(n,ni)+h(ni)
按和代价法：
例，节点A的值=3+1+3+1=8
扩展S0后得到的与/或树
70
扩展节点E，得到如右图所示的与/或树。
此时，由右子树求出的h(S0)=12。但是，由左子树求出的h(S0)=9。显然，左子树的代价小。因此，当前的希望树应改为左子树。
S0
9
A
8
D
11
B
C
E
F
3
3
7
2
3
2
2
2
7
6
扩展节点E后得到的与/或树
71
对节点B进行扩展，扩展两层后得到的与/或树如下图所示。由于节点H和I是可解节点，故调用可解标记过程，得节点G、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。
S0
9
A
8
11
B
C
E
F
3
3
7
2
3
2
2
2
7
6
G
J
H
I
K
L
2
2
2
6
扩展节点B后得到的与/或树
72
对节点C进行扩展，扩展两层后得到的与/或树如右图所示。由于节点N和P是可解节点，故调用可解标记过程，得节点M、C、A也为可解节点，进而可标记S0为可解节点，这就的到了代价最小的解树。按和代价法，该最优解的代价为9。
S0
9
A
8
D
11
B
C
E
F
3
7
2
3
2
2
2
7
6
G
J
H
I
K
L
2
2
2
6
M
N
P
5
2
2
9
扩展节点C后得到的与/或树
73
博弈的概念
博弈是一类具有智能行为的竞争活动，如下棋、战争等。
博弈的类型
双人完备信息博弈：两位选手（例如MAX和MIN ）对垒，轮流走步，每一方不仅知道对方已经走过的棋步，而且还能估计出对方未来的走步。
机遇性博弈：存在不可预测性的博弈，例如掷币等。
博弈树搜索
74
博弈树
若把双人完备信息博弈过程用图表示出来，就得到一棵与/或树，这种与/或树被称为博弈树。
博弈树的特点