第 4章 图搜索技术
根据问题的实际情况不断寻找可利用的
知识，从而构造一条代价较少的推理路
线，使问题得到圆满解决的过程称为搜
索。搜索实用于：结构不良问题，无成
熟算法；或有算法,但问题复杂，如
博弈。
或图搜索；与或图搜索
第 4章 图搜索技术 ----4.1 状态
图搜索
4.1.1 状态图
例、八数码问题的状态图表示。
状态是描述问题求解过程中任一时刻的状况，
一般用一组变量的有序组合表示。引起状态
中某些分量发生变化，从而使问题从一个状
态变为另一个状态的操作、规则、变换称为
算符。问题求解就是寻找一个从初始状态到
目标状态的算符序列的过程。问题求解过程
可描述为一个有向图，其中的节点代表状态，
边表示状态转换之间的算符。
第 4章 图搜索技术 ----4.1 状态
图搜索
4.1.2 状态图搜索
1、搜索方式
树式搜索：每次扩展所有子节点
线式搜索：每次只扩展一个子节点
可回溯（穷举式搜索） 不可回溯（随机碰
撞式搜索）
2、搜索策略
搜索分为盲目搜索和启发式搜索。盲目搜索：
按预定的控制策略进行搜索，在搜索过程中
获得的中间信息不用来改进控制策略；启发
式搜索：在搜索过程中加入了与问题有关的
启发性信息，用以指导搜索朝着最有希望的
方向前进，加速问题的求解过程并找到最优
解。
第 4章 图搜索技术 ----4.1 状态图搜索
3、搜索算法
树式搜索算法：
步 1 把初始节点放入 OPEN表；
步 2 检查 OPEN表，若为空，则问题无解，退出；
步 3 移出 OPEN表中第一个节点并放入 CLOSED表中，并记该节点
为 n;
步 4 考察节点 n是否为目标节点，若是，则搜索成功，退出；
步 5 若 n不可扩展，则转步 2；
步 6 扩展节点 n，生成所有子节点，对这组子节点作如下处理：
（ 1）、如果有节点 n的先辈节点，则删除之；
（ 2）、如果有已存在于 OPEN表的节点，也删除之；但删除之
前要比较其返回初始节点的新路径与原路径，如果新路径, 短,,
则修改这些节点在 OPEN表中的原指向父节点的指针，使其指向
新的父节点。
第 4章 图搜索技术 ----4.1 状态图搜索
（ 3）、如果有已存在于 CLOSED表中的节点，则作与（ 2）同样的
处理，并且再将其移出 CLOSED表，放入 OPEN表重新扩展；
（ 4）、对其余子节点，配上指向父节点 n的指针后放入 OPEN表，
对 OPEN表按某种搜索策略排序后转步 2。
线式搜索算法
不可回溯的线式搜索：
步 1 把初始节点 S0放入 CLOSED表中；
步 2 令 N= S0 ；
步 3 若 N是目标节点，则搜索成功，结束 ;
步 4 若 N不可扩展，则搜索失败，退出。
步 5 扩展 N，选取一个未在 CLOSED表中出现的子节点 N1放入
CLOSED表中，令 N=N1，转步 3。
第 4章 图搜索技术 ----4.1 状态图搜索
可回溯的线式搜索：
步 1 把初始节点 S0放入 CLOSED表中；
步 2 令 N= S0 ；
步 3 若 N是目标节点，则搜索成功，结束 ;
步 4 若 N不可扩展，则移出 CLOSED表的末端节点 Ne，
若 Ne =S0,则搜索失败，退出。否则，以 CLOSED表
新的末端节点 Ne作为 N,即令 N=Ne，转步 4
步 5 扩展 N，选取一个未在 CLOSED表中出现的子节点
N1放入 CLOSED表中，令 N=N1，转步 3。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.3 穷举式搜索
1、广度优先搜索
又称宽度优先思索，优先在同一级节点中考察，只有当同一级节点扩展完
以后，才扩展下一级节点。
例、解八数码问题。初始状态,（ 2,8,3,4,5,6,7,1），目标状态：
（ 1,2,3,4,5,6,7,8）
广度优先搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，将其所有子节点配上指向 N的指针依次放入 OPEN表
的尾部，转步 2。
第 4章 图搜索技术 ----4.1 状态图搜索
广度优先搜索的特点：完备、解是最优解、效率
低。
2、深度优先搜索
在搜索的每一层，始终只扩展一个节点，不断地
向纵深前进，直到不能再前进时，才从当前节点
返回到上一级节点，延另一节点又继续前进。
例、八数码问题的深度优先搜索。
第 4章 图搜索技术 ----4.1 状态图搜索
深度优先搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，将其所有子节点配上指向 N的返回指针依次放
入 OPEN表的首部，转步 2。
深度优先搜索策略的特点：不完备、找到的解不一定是最优
解。
第 4章 图搜索技术 ----4.1 状态图搜索
3、有界深度优先搜索
搜索深度限制。当深度优先搜索到一定深度后，就不在向纵深搜索，
而是改变方向继续搜索。
有界深度搜索算法：
步 1 把初始节点 S0放入 OPEN表中，置 S0的深度 d(S0)=0；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N的深度 d(N)=dm，或者 N无子节点，则转步 2。
步 6 扩展 N，将其所有子节点 Ni配上指向 N的返回指针后依次放入
OPEN表的前部，置 d(Ni)=d(N)+1，转步 2。
例、上例中八数码问题的有界深度搜索（ dm=4 )。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.4 启发式搜索
1、问题的提出
组合爆炸：梵塔问题，博弈：国际象棋 10120，围棋 10761。
2、启发性信息
（ 1）、用于扩展节点的选择的信息；
（ 2）、用于生成节点的选择的信息；
（ 3）、用于删除节点的选择的信息。
3、启发函数
用来估计搜索树上节点 x与目标节点 Sg接近程度的函数，记
为 h(x).
第 4章 图搜索技术 ----4.1 状态图搜索
4、启发式搜索算法
（ 1）、全局择优搜索
全局择优搜索算法：
步 1 把初始节点 S0放入 OPEN表中，计算 h(S0)；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，计算每个子节点 x的函数值 h(x)，并将所有子
节点配上指向 N的返回指针放入 OPEN表中，再对 OPEN表
中的所有子节点按其函数值大小以升序排序，转步 2。
例、八数码问题的全局择优搜索。
第 4章 图搜索技术 ----4.1 状态图搜索
（ 2）、局部择优搜索。
4.1.5 加权状态图搜索
1、加权状态图与代价树
加权状态图的搜索要增加权值的计算与传播过程，并且要由权值
来确定节点的扩展顺序。代价,g(xj)= g(xi)+c(xi,xj);
g(S0)=0.
2、分支界限法：相当于启发式搜索中的全局择优搜索，不过用
代价函数代替启发函数。
3、最近择优法：相当于启发式搜索中的局部择优搜索，不过用
代价函数代替启发函数。
例、用代价树搜索求解 P96例 4.6的问题。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.6 启发式搜索的 A算法和 A*算法
1、估价函数
f(x)=g(x)+h(x); 其中 g(x)是代价函数,h(x)是启发函数。 或定义为：
f(x)=d(x)+h(x); d(x)是 x的深度。
2,A算法
步 1 把附有 f(S0)的初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，计算每个子节点 x的估价函数值 f(x)，并对这组
子节点作如下处理：
（ 1）、考察是否有已在 OPEN表或 CLOSED表中存在的节点；
第 4章 图搜索技术 ----4.1 状态图搜索
若有，则再考察其中有无 N的先辈节点，若有则删除之；对
于其余节点，也删除之，但由于它们又被第二次生成，因
而需考虑是否修改已经存在于 OPEN表或 CLOSED表中的
这些节点及其后裔的返回指针和 f(x)值，修改原则是, 抄
f(x)值小的路走, ；
（ 2）、对其余子节点配上指向 N的返回指针后放入 OPEN表
中，并对 OPEN表按 f(x)值以升序排序，转步 2。
可以看出,A算法是树式搜索算法加估价函数 f(x)的一种启发
式搜索算法。
3,A*算法
A算法加上限制：对所有节点 x均有 h(x)?h*(x)。其中 h*(x)是
从节点 x到目标节点的最小代价。
第 4章 图搜索技术 ----4.3 与或图搜索
4.2 状态图问题求解
一些实例。
4.3 与或图搜索
4.3.1 与或图
复杂问题分解为简单问题。见例。
解树：问题的求解路径构成的树。
本原问题：直接可解的简单问题。
终止节点：本原问题对应的节点。
端节点：无子节点的节点。终止节点一定是端节点，反之不成立。
与节点：与子节点之间是, 与, 关系的节点。
或节点：与子节点之间是, 或, 关系的节点。
第 4章 图搜索技术 ----4.3 与或图搜索
4.3.2 与或图搜索
1、与或图搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 取 OPEN表中第一个节点 N放入 CLOSED表中；
步 3 若节点 N可扩展，则做下列工作：
（ 1）、扩展 N，将其所有子节点配上指向父节点 N的指针后
放入 OPEN表；
（ 2）、考察这些子节点中是否有终止节点。若有，则标记
它们为可解节点，并将它们也放入 CLOSED表，然后由它
们的可解返回推断其先辈节点的可解性，并对其中的可解
节点进行标记。如果初始节点也被标记为可解节点，则搜
索成功，结束。
（ 3）、删去 OPEN表中那些具有可解先辈的节点（因为其先
辈节点已经可解，故已无考察节点的必要），转步 2。
第 4章 图搜索技术 ----4.3 与或图搜索
步 4 若 N不可扩展，则做下列工作：
（ 1）、标记 N为不可解节点，然后由它的不可解返回推断其先辈
节点的可解性，并对其中的不可解节点进行标记。如果初始节点
S0也被标记为不可解节点，则搜索失败，退出。
（ 2）、删去 OPEN表中那些具有不可解先辈的节点（因为其先辈节
点已不可解，没必要再考察这些节点），转步 2。
2、可解节点与不可解节点
必须满足下列条件之一，一个节点才是可解的：
（ 1）、终止节点是可解的；
（ 2）、一个与节点可解，当且仅当其子节点全都可解；
（ 3）、一个或节点可解，只要其子节点有一个可解。
一个节点是不可解的，必须满足下列条件之一：
（ 1）、非终止节点的端节点是不可解节点；
（ 2）、一个与节点不可解，只要其子节点至少有一个不可解；
（ 3）、一个或节点不可解，当且仅当其子节点全都不可解。
第 4章 图搜索技术 ----4.3 与或图搜索
4.3.3 启发式与或树搜索
最优解树：代价最小的解树称为最优解树。
有序搜索：每次确定欲扩展的节点时，先往前多看几步。计算一下
扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩
展。
1、解树的代价
解树的代价就是树根的代价。
代价的计算方法：
设 g(x)表示节点 x的代价,c(x,y)表示节点 x到其子节点 y的代价（即
边 xy的代价），则
（ 1）、若 x是终止节点,g(x)=0；
（ 2）、若 x是或节点,g(x)=min{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1,
y2, …, yn是 x的子节点。
（ 3）、若 x是与节点，则有两种计算公式：
第 4章 图搜索技术 ----4.3 与或图搜索
(a) 和代价法,g(x)=?{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1, y2, …,
yn是 x的子节点。
(b) 最大代价法,g(x)=max{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1,
y2, …, yn是 x的子节点。
（ 4）、对非终止端节点 x,g(x)=?。
例,p121例 3。
2、希望树
希望树的定义：
（ 1）、初始节点 S0在希望树 T中。
（ 2）、如果节点 x在希望树 T中，则一定有：
(a)、如果 x是具有子节点 y1, y2, …, yn的, 或, 节点，则具有
min{1 ? i ? n}{c(x,yi)+g(yi)}值的那个子节点 yi也应在 T中。
(b)、如果 x是与节点，则它的全部子节点都应在 T中。
第 4章 图搜索技术 ----4.3 与或图搜索
3、与或树的有序搜索过程
步 1 把初始节点 S0放入 OPEN表中；
步 2 求出希望树 T，即根据当前搜索树中节点的代价 g求出
以 S0为根的希望树 T。
步 3 依次把 OPEN表中 T的端节点 N选出放入 CLOSED表中；
步 4 若节点 N是终止节点，则做下列工作：
（ 1）、标记 N为可解节点。
（ 2）、对 T应用可解标记过程，把 N的先辈节点中的可解节
点都标记为可解节点。
（ 3）、若初始节点 S0能被标记为可解节点，则 T就是最优解
树，成功退出。
（ 4）、否则，从 OPEN表中删去具有可解先辈的所有节点。
第 4章 图搜索技术 ----4.3 与或图搜索
步 5 若 N不是终止节点，且它不可扩展，则做下列工作：
（ 1）、标记 N为不可解节点。
（ 2）、对 T应用不可解标记过程，把 N的先辈节点中的不可解节点
都标记为不可解节点。
（ 3）、若初始节点 S0也被标记为不可解节点，则失败退出。
（ 4）、否则，从 OPEN表中删去具有不可解先辈的所有节点。
步 6 若 N不是终止节点，但它可扩展，则做下列工作：
（ 1）、扩展节点 N，产生 N的所有子节点。
（ 2）、把这些子节点都放入 OPEN表中，并为每一个子节点配置指
向父节点 N的指针。
（ 3）、计算这些子节点的 g值及其先辈节点的 g值。
步 7 转步 2。
例、见教材 p123例 4。
第 4章 图搜索技术 ----4.5 博弈树搜索
4.4 与或图问题求解
三阶梵塔问题的与或图表示。
4.5 博弈树搜索
,二人零和、全信息、非偶然, 博弈：
（ 1）、对垒的 A,B双方轮流采取行动。结局有三种情况,A方
胜,B方败； A方败,B方胜；双方平局。
（ 2）、对垒过程中，任何一方都了解当前的格局和过去的历史。
（ 3）、任何一方都要选取对自己最有利而对对方最不利的对策。
不存在碰运气的偶然因素。
4.5.1 博弈树的概念
博弈树是一棵具有以下特点的与或树：
（ 1）、博弈的初始格局是初始节点。
（ 2）、在博弈树中,,或, 节点和, 与, 节点是逐层交替出现
的。
第 4章 图搜索技术 ----4.5 博弈树搜索
自己一方扩展的节点是, 或, 的关系，对方扩展的节点之间是, 与,
的关系。
（ 3）、所有自己一方获胜的终局都是本原问题，相应的节点是可
解节点；所有使对方获胜的终局都是不可解节点。
4.5.2 极小极大分析法
（ 1）设博弈的双方中一方为 A，另一方为 B。然后为其中一方（例
如 A）寻找一个最优行动方案。
（ 2）为了找到当前的最优行动方案，需要考虑每一方案实施后对
方可能采取的所有行动，并计算可能的得分。
（ 3）为了计算得分，需要根据问题的特性信息定义一个估价函数，
用来估算当前博弈树端节点的得分。此得分值称为静态估值。
（ 4）当端节点的估计值计算出来后，在推算父节点的得分。对
,或, 节点，选取其子节点中最大的得分作为父节点的得分；对
,与, 节点，取其子节点中最小的一个得分作为父节点的得分。
这样计算得的父节点的得分称为倒推值。
第 4章 图搜索技术 ----4.5 博弈树搜索
（ 5）如果一个行动方案能获得最大的倒推值，它就是当前最好的行动
方案。
例、一字棋游戏。见 P128例 1。
4.5.3 ?-?剪枝技术
（ 1）对于一个与节点 MIN，若能估计出其倒推值的上确界 ?，并且
这个 ?值不大于 MIN的父节点的估计倒推值的下确界 ?，即 ???，
则就不必再扩展该 MIN节点的其余子节点了。这一过程称为 ?剪
枝。
（ 2）对于一个或节点 MAX，若能估计出其倒推值的下确界 ?，并且
这个 ?值不小于 MAX的父节点的估计倒推值的下确界 ?，即 ???，
则就不必再扩展该 MAX节点的其余子节点了。这一过程称为 ?剪
枝。
作业,P130,6,12,13
根据问题的实际情况不断寻找可利用的
知识，从而构造一条代价较少的推理路
线，使问题得到圆满解决的过程称为搜
索。搜索实用于：结构不良问题，无成
熟算法；或有算法,但问题复杂，如
博弈。
或图搜索；与或图搜索
第 4章 图搜索技术 ----4.1 状态
图搜索
4.1.1 状态图
例、八数码问题的状态图表示。
状态是描述问题求解过程中任一时刻的状况，
一般用一组变量的有序组合表示。引起状态
中某些分量发生变化，从而使问题从一个状
态变为另一个状态的操作、规则、变换称为
算符。问题求解就是寻找一个从初始状态到
目标状态的算符序列的过程。问题求解过程
可描述为一个有向图，其中的节点代表状态，
边表示状态转换之间的算符。
第 4章 图搜索技术 ----4.1 状态
图搜索
4.1.2 状态图搜索
1、搜索方式
树式搜索：每次扩展所有子节点
线式搜索：每次只扩展一个子节点
可回溯（穷举式搜索） 不可回溯（随机碰
撞式搜索）
2、搜索策略
搜索分为盲目搜索和启发式搜索。盲目搜索：
按预定的控制策略进行搜索，在搜索过程中
获得的中间信息不用来改进控制策略；启发
式搜索：在搜索过程中加入了与问题有关的
启发性信息，用以指导搜索朝着最有希望的
方向前进，加速问题的求解过程并找到最优
解。
第 4章 图搜索技术 ----4.1 状态图搜索
3、搜索算法
树式搜索算法：
步 1 把初始节点放入 OPEN表；
步 2 检查 OPEN表，若为空，则问题无解，退出；
步 3 移出 OPEN表中第一个节点并放入 CLOSED表中，并记该节点
为 n;
步 4 考察节点 n是否为目标节点，若是，则搜索成功，退出；
步 5 若 n不可扩展，则转步 2；
步 6 扩展节点 n，生成所有子节点，对这组子节点作如下处理：
（ 1）、如果有节点 n的先辈节点，则删除之；
（ 2）、如果有已存在于 OPEN表的节点，也删除之；但删除之
前要比较其返回初始节点的新路径与原路径，如果新路径, 短,,
则修改这些节点在 OPEN表中的原指向父节点的指针，使其指向
新的父节点。
第 4章 图搜索技术 ----4.1 状态图搜索
（ 3）、如果有已存在于 CLOSED表中的节点，则作与（ 2）同样的
处理，并且再将其移出 CLOSED表，放入 OPEN表重新扩展；
（ 4）、对其余子节点，配上指向父节点 n的指针后放入 OPEN表，
对 OPEN表按某种搜索策略排序后转步 2。
线式搜索算法
不可回溯的线式搜索：
步 1 把初始节点 S0放入 CLOSED表中；
步 2 令 N= S0 ；
步 3 若 N是目标节点，则搜索成功，结束 ;
步 4 若 N不可扩展，则搜索失败，退出。
步 5 扩展 N，选取一个未在 CLOSED表中出现的子节点 N1放入
CLOSED表中，令 N=N1，转步 3。
第 4章 图搜索技术 ----4.1 状态图搜索
可回溯的线式搜索：
步 1 把初始节点 S0放入 CLOSED表中；
步 2 令 N= S0 ；
步 3 若 N是目标节点，则搜索成功，结束 ;
步 4 若 N不可扩展，则移出 CLOSED表的末端节点 Ne，
若 Ne =S0,则搜索失败，退出。否则，以 CLOSED表
新的末端节点 Ne作为 N,即令 N=Ne，转步 4
步 5 扩展 N，选取一个未在 CLOSED表中出现的子节点
N1放入 CLOSED表中，令 N=N1，转步 3。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.3 穷举式搜索
1、广度优先搜索
又称宽度优先思索，优先在同一级节点中考察，只有当同一级节点扩展完
以后，才扩展下一级节点。
例、解八数码问题。初始状态,（ 2,8,3,4,5,6,7,1），目标状态：
（ 1,2,3,4,5,6,7,8）
广度优先搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，将其所有子节点配上指向 N的指针依次放入 OPEN表
的尾部，转步 2。
第 4章 图搜索技术 ----4.1 状态图搜索
广度优先搜索的特点：完备、解是最优解、效率
低。
2、深度优先搜索
在搜索的每一层，始终只扩展一个节点，不断地
向纵深前进，直到不能再前进时，才从当前节点
返回到上一级节点，延另一节点又继续前进。
例、八数码问题的深度优先搜索。
第 4章 图搜索技术 ----4.1 状态图搜索
深度优先搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，将其所有子节点配上指向 N的返回指针依次放
入 OPEN表的首部，转步 2。
深度优先搜索策略的特点：不完备、找到的解不一定是最优
解。
第 4章 图搜索技术 ----4.1 状态图搜索
3、有界深度优先搜索
搜索深度限制。当深度优先搜索到一定深度后，就不在向纵深搜索，
而是改变方向继续搜索。
有界深度搜索算法：
步 1 把初始节点 S0放入 OPEN表中，置 S0的深度 d(S0)=0；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N的深度 d(N)=dm，或者 N无子节点，则转步 2。
步 6 扩展 N，将其所有子节点 Ni配上指向 N的返回指针后依次放入
OPEN表的前部，置 d(Ni)=d(N)+1，转步 2。
例、上例中八数码问题的有界深度搜索（ dm=4 )。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.4 启发式搜索
1、问题的提出
组合爆炸：梵塔问题，博弈：国际象棋 10120，围棋 10761。
2、启发性信息
（ 1）、用于扩展节点的选择的信息；
（ 2）、用于生成节点的选择的信息；
（ 3）、用于删除节点的选择的信息。
3、启发函数
用来估计搜索树上节点 x与目标节点 Sg接近程度的函数，记
为 h(x).
第 4章 图搜索技术 ----4.1 状态图搜索
4、启发式搜索算法
（ 1）、全局择优搜索
全局择优搜索算法：
步 1 把初始节点 S0放入 OPEN表中，计算 h(S0)；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，计算每个子节点 x的函数值 h(x)，并将所有子
节点配上指向 N的返回指针放入 OPEN表中，再对 OPEN表
中的所有子节点按其函数值大小以升序排序，转步 2。
例、八数码问题的全局择优搜索。
第 4章 图搜索技术 ----4.1 状态图搜索
（ 2）、局部择优搜索。
4.1.5 加权状态图搜索
1、加权状态图与代价树
加权状态图的搜索要增加权值的计算与传播过程，并且要由权值
来确定节点的扩展顺序。代价,g(xj)= g(xi)+c(xi,xj);
g(S0)=0.
2、分支界限法：相当于启发式搜索中的全局择优搜索，不过用
代价函数代替启发函数。
3、最近择优法：相当于启发式搜索中的局部择优搜索，不过用
代价函数代替启发函数。
例、用代价树搜索求解 P96例 4.6的问题。
第 4章 图搜索技术 ----4.1 状态图搜索
4.1.6 启发式搜索的 A算法和 A*算法
1、估价函数
f(x)=g(x)+h(x); 其中 g(x)是代价函数,h(x)是启发函数。 或定义为：
f(x)=d(x)+h(x); d(x)是 x的深度。
2,A算法
步 1 把附有 f(S0)的初始节点 S0放入 OPEN表中；
步 2 若 OPEN表为空，则搜索失败，退出；
步 3 取 OPEN表中前面第一个节点 N放入 CLOSED表中；
步 4 若目标节点 Sg =N，则搜索成功，结束 ;
步 5 若 N不可扩展，则转步 2。
步 6 扩展 N，计算每个子节点 x的估价函数值 f(x)，并对这组
子节点作如下处理：
（ 1）、考察是否有已在 OPEN表或 CLOSED表中存在的节点；
第 4章 图搜索技术 ----4.1 状态图搜索
若有，则再考察其中有无 N的先辈节点，若有则删除之；对
于其余节点，也删除之，但由于它们又被第二次生成，因
而需考虑是否修改已经存在于 OPEN表或 CLOSED表中的
这些节点及其后裔的返回指针和 f(x)值，修改原则是, 抄
f(x)值小的路走, ；
（ 2）、对其余子节点配上指向 N的返回指针后放入 OPEN表
中，并对 OPEN表按 f(x)值以升序排序，转步 2。
可以看出,A算法是树式搜索算法加估价函数 f(x)的一种启发
式搜索算法。
3,A*算法
A算法加上限制：对所有节点 x均有 h(x)?h*(x)。其中 h*(x)是
从节点 x到目标节点的最小代价。
第 4章 图搜索技术 ----4.3 与或图搜索
4.2 状态图问题求解
一些实例。
4.3 与或图搜索
4.3.1 与或图
复杂问题分解为简单问题。见例。
解树：问题的求解路径构成的树。
本原问题：直接可解的简单问题。
终止节点：本原问题对应的节点。
端节点：无子节点的节点。终止节点一定是端节点，反之不成立。
与节点：与子节点之间是, 与, 关系的节点。
或节点：与子节点之间是, 或, 关系的节点。
第 4章 图搜索技术 ----4.3 与或图搜索
4.3.2 与或图搜索
1、与或图搜索算法：
步 1 把初始节点 S0放入 OPEN表中；
步 2 取 OPEN表中第一个节点 N放入 CLOSED表中；
步 3 若节点 N可扩展，则做下列工作：
（ 1）、扩展 N，将其所有子节点配上指向父节点 N的指针后
放入 OPEN表；
（ 2）、考察这些子节点中是否有终止节点。若有，则标记
它们为可解节点，并将它们也放入 CLOSED表，然后由它
们的可解返回推断其先辈节点的可解性，并对其中的可解
节点进行标记。如果初始节点也被标记为可解节点，则搜
索成功，结束。
（ 3）、删去 OPEN表中那些具有可解先辈的节点（因为其先
辈节点已经可解，故已无考察节点的必要），转步 2。
第 4章 图搜索技术 ----4.3 与或图搜索
步 4 若 N不可扩展，则做下列工作：
（ 1）、标记 N为不可解节点，然后由它的不可解返回推断其先辈
节点的可解性，并对其中的不可解节点进行标记。如果初始节点
S0也被标记为不可解节点，则搜索失败，退出。
（ 2）、删去 OPEN表中那些具有不可解先辈的节点（因为其先辈节
点已不可解，没必要再考察这些节点），转步 2。
2、可解节点与不可解节点
必须满足下列条件之一，一个节点才是可解的：
（ 1）、终止节点是可解的；
（ 2）、一个与节点可解，当且仅当其子节点全都可解；
（ 3）、一个或节点可解，只要其子节点有一个可解。
一个节点是不可解的，必须满足下列条件之一：
（ 1）、非终止节点的端节点是不可解节点；
（ 2）、一个与节点不可解，只要其子节点至少有一个不可解；
（ 3）、一个或节点不可解，当且仅当其子节点全都不可解。
第 4章 图搜索技术 ----4.3 与或图搜索
4.3.3 启发式与或树搜索
最优解树：代价最小的解树称为最优解树。
有序搜索：每次确定欲扩展的节点时，先往前多看几步。计算一下
扩展这个节点可能要付出的代价，并选择代价最小的节点进行扩
展。
1、解树的代价
解树的代价就是树根的代价。
代价的计算方法：
设 g(x)表示节点 x的代价,c(x,y)表示节点 x到其子节点 y的代价（即
边 xy的代价），则
（ 1）、若 x是终止节点,g(x)=0；
（ 2）、若 x是或节点,g(x)=min{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1,
y2, …, yn是 x的子节点。
（ 3）、若 x是与节点，则有两种计算公式：
第 4章 图搜索技术 ----4.3 与或图搜索
(a) 和代价法,g(x)=?{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1, y2, …,
yn是 x的子节点。
(b) 最大代价法,g(x)=max{1 ? i ? n}{c(x,yi)+g(yi)}，其中 y1,
y2, …, yn是 x的子节点。
（ 4）、对非终止端节点 x,g(x)=?。
例,p121例 3。
2、希望树
希望树的定义：
（ 1）、初始节点 S0在希望树 T中。
（ 2）、如果节点 x在希望树 T中，则一定有：
(a)、如果 x是具有子节点 y1, y2, …, yn的, 或, 节点，则具有
min{1 ? i ? n}{c(x,yi)+g(yi)}值的那个子节点 yi也应在 T中。
(b)、如果 x是与节点，则它的全部子节点都应在 T中。
第 4章 图搜索技术 ----4.3 与或图搜索
3、与或树的有序搜索过程
步 1 把初始节点 S0放入 OPEN表中；
步 2 求出希望树 T，即根据当前搜索树中节点的代价 g求出
以 S0为根的希望树 T。
步 3 依次把 OPEN表中 T的端节点 N选出放入 CLOSED表中；
步 4 若节点 N是终止节点，则做下列工作：
（ 1）、标记 N为可解节点。
（ 2）、对 T应用可解标记过程，把 N的先辈节点中的可解节
点都标记为可解节点。
（ 3）、若初始节点 S0能被标记为可解节点，则 T就是最优解
树，成功退出。
（ 4）、否则，从 OPEN表中删去具有可解先辈的所有节点。
第 4章 图搜索技术 ----4.3 与或图搜索
步 5 若 N不是终止节点，且它不可扩展，则做下列工作：
（ 1）、标记 N为不可解节点。
（ 2）、对 T应用不可解标记过程，把 N的先辈节点中的不可解节点
都标记为不可解节点。
（ 3）、若初始节点 S0也被标记为不可解节点，则失败退出。
（ 4）、否则，从 OPEN表中删去具有不可解先辈的所有节点。
步 6 若 N不是终止节点，但它可扩展，则做下列工作：
（ 1）、扩展节点 N，产生 N的所有子节点。
（ 2）、把这些子节点都放入 OPEN表中，并为每一个子节点配置指
向父节点 N的指针。
（ 3）、计算这些子节点的 g值及其先辈节点的 g值。
步 7 转步 2。
例、见教材 p123例 4。
第 4章 图搜索技术 ----4.5 博弈树搜索
4.4 与或图问题求解
三阶梵塔问题的与或图表示。
4.5 博弈树搜索
,二人零和、全信息、非偶然, 博弈：
（ 1）、对垒的 A,B双方轮流采取行动。结局有三种情况,A方
胜,B方败； A方败,B方胜；双方平局。
（ 2）、对垒过程中，任何一方都了解当前的格局和过去的历史。
（ 3）、任何一方都要选取对自己最有利而对对方最不利的对策。
不存在碰运气的偶然因素。
4.5.1 博弈树的概念
博弈树是一棵具有以下特点的与或树：
（ 1）、博弈的初始格局是初始节点。
（ 2）、在博弈树中,,或, 节点和, 与, 节点是逐层交替出现
的。
第 4章 图搜索技术 ----4.5 博弈树搜索
自己一方扩展的节点是, 或, 的关系，对方扩展的节点之间是, 与,
的关系。
（ 3）、所有自己一方获胜的终局都是本原问题，相应的节点是可
解节点；所有使对方获胜的终局都是不可解节点。
4.5.2 极小极大分析法
（ 1）设博弈的双方中一方为 A，另一方为 B。然后为其中一方（例
如 A）寻找一个最优行动方案。
（ 2）为了找到当前的最优行动方案，需要考虑每一方案实施后对
方可能采取的所有行动，并计算可能的得分。
（ 3）为了计算得分，需要根据问题的特性信息定义一个估价函数，
用来估算当前博弈树端节点的得分。此得分值称为静态估值。
（ 4）当端节点的估计值计算出来后，在推算父节点的得分。对
,或, 节点，选取其子节点中最大的得分作为父节点的得分；对
,与, 节点，取其子节点中最小的一个得分作为父节点的得分。
这样计算得的父节点的得分称为倒推值。
第 4章 图搜索技术 ----4.5 博弈树搜索
（ 5）如果一个行动方案能获得最大的倒推值，它就是当前最好的行动
方案。
例、一字棋游戏。见 P128例 1。
4.5.3 ?-?剪枝技术
（ 1）对于一个与节点 MIN，若能估计出其倒推值的上确界 ?，并且
这个 ?值不大于 MIN的父节点的估计倒推值的下确界 ?，即 ???，
则就不必再扩展该 MIN节点的其余子节点了。这一过程称为 ?剪
枝。
（ 2）对于一个或节点 MAX，若能估计出其倒推值的下确界 ?，并且
这个 ?值不小于 MAX的父节点的估计倒推值的下确界 ?，即 ???，
则就不必再扩展该 MAX节点的其余子节点了。这一过程称为 ?剪
枝。
作业,P130,6,12,13
