当前位置：文档之家 › 第三章与或图搜索.

第三章与或图搜索.

  • 格式：ppt
  • 大小：538.00 KB
  • 文档页数：61

下载文档原格式

  / 61

合集下载

2013第三章_与或图的搜索

2013第三章_与或图的搜索

第10次课 10月07日
上次课程回顾




与或图搜索:搜索从初始节点到一组终节点集N的一个 解图。 对于与或图搜索，是通过对局部图的评价来选择待扩 展的节点。 解图的求法是：从节点n开始，正确选择一个外向连接 符，再从该连接符所指的每一个后继结点出发，继续 选一个外向连接符，如此进行下去直到由此产生的每 一个后继节点成为集合N中的一个元素为止。 具有最小耗散值的解图称为最佳解图。 能解节点 不能解节点
算法

极大极小过程MINIMAX：
1. T:=(s, MAX)，OPEN:=(s)，CLOSED:=( );开始时树由初始节点 构成，OPEN表只含有S. 2. LOOP1: IF OPEN =( ) THEN GO LOOP2; 3. n:=FIRST(OPEN)，REMOVE(n,OPEN)，ADD(n,CLOSED);将n放到 CLOSED表的前面， 4. IF n可直接判定为赢, 输或平局 THEN f(n):= -0，GO LOOP1 ELSE EXPAND(n){ni}， ADD ({ni} ，T) IF d{ni} k THEN ADD({ni}, OPEN) ,GO LOOP1 ELSE 计算f(ni); ni达到深度k,计算各端节点f值.
n5(1)
2
n6
n8
n8(0)
目标
n7
目标
n7(0)
红色：5 蓝色：6
3次循环之后
n0 n1 n2
初始节点
n1 n4 5
n0
初始ห้องสมุดไป่ตู้点
1 n4(1)
n2(4)
n3
n5 n3(4) n6(2)
n5(1)
2
n6

与或图搜索问题

与或图搜索问题

与或图搜索问题的特点
组合优化问题
与或图搜索问题是一个典型的组 合优化问题，因为解决方案空间 通常非常大，需要采用高效的搜 索策略来找到最优解。
逻辑约束
与或图中的节点之间存在逻辑约 束，即某些节点必须同时满足与 （AND）或（OR）关系。
决策变量
与或图中的节点代表决策变量， 需要确定它们的取值以最大化目 标函数或满足特定条件。
03
与或图搜索问题的求解算法
深度优先搜索算法
深度优先搜索是一种用于遍历或搜索树 或图的算法。该算法会尽可能深地搜索 树的分支，当节点v的所在边都己被探 寻过，搜索将回溯到发现节点v的那条
边的起始节点。
深度优先搜索算法适合求解与或图中的 AND-OR图问题，可以找到所有解或
最优解。
算法步骤：选择一个起始节点，标记为 已访问，然后递归地搜索与该节点关联 的所有未被访问的节点，直到所有节点
与或图搜索问题的求解目标
找到最优解
与或图搜索问题的求解目标是找到满足所有 逻辑约束的节点组合，以最大化目标函数或 满足特定条件。
高效求解
由于与或图搜索问题通常具有较大的解决方案空间 ，因此需要采用高效的搜索策略和启发式算法来快 速找到最优解。
实际应用
与或图搜索问题在许多实际应用中具有广泛 的应用，如电路设计、计划调度、物流优化 等。
路径规划
在路径规划问题中，与或图搜索问题可以用于寻找满足特定条件的路径， 如最短路径、最少花费路径等，使得路径能够连接起点和终点。
02
与或图搜索问题概述
与或图搜索问题的定义
与或图搜索问题是一种组合优化问题，旨在寻找满足一系列与 （AND）或（OR）逻辑关系的节点组合。
它通常由一个有向图表示，其中节点表示决策变量，边表示 逻辑关系。

与或图

与或图
与或图的搜索 及应用
北京信息科技大学 孙骏 2014.05.13
与或图的搜索策略
1 与或图的一般搜索过程 2 与或图的广度优先搜索
3 与或图的深度优先搜索
4 与或图的有序搜索 5 博弈树的启发式搜索
1 与或图的一般搜索过程

与图: 把一个原问题分解为若干个子问题，P1，P2， P3，…可用“与图”表示；P1，P2，P3，…对应的子问
S0 2
A 6 t1 5 t2 E C 1 t3 2 F 3 1 2 B 2
D 1 G 1
t4 2 t5
解：左边解树， 按和代价：h(A)=11 h(S0)=13; 按最大代价：h(A)=6 h(S0)=8; 右边解树， 按和代价：h(G)=3, h(D)=4, h(B)=6, h(S0)=8; 按最大代价：h(G)=2, h(D)=3, h(B)=5, h(S0)=7
P
E
F
2
G
0 0 2 2 0 0
H
3
2
h(N)=2, h(P)=7, h(C)=3, h(A)=8 左子树h(S0)=9
3
2
2
2
三阶梵塔问题
1 2 3 1 2 3
A
A
B C
B C
初始配置
目标配置

问题描述: 采用三元组表示状态: S=(i,j,k) 其中，i, j, k分别表示金片C,B，A所在的钢针号。 初始状态（1，1，1），目标状态（3，3，3）
a
4-5=-1 b
5-4=1
5-5=0
5-5=0
6-6=0
程可用一个“与或图”来表示
P P1 P11 P12 P2 P31 P3 P32 P33

(搜索推理技术-与或树搜索)

(搜索推理技术-与或树搜索)

7、无判断起始节点1可解
8、从OPEN中删除含有可解先辈节点的节点
删除
OPEN= { B, C, t1, 10, 11, 12, A, t2, t3 }
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9 } OPEN= {t1, 10, 11, 12, t2, t3}
CLOSED= {1, 2, 3, 4, 5, 6, 7, 8, 9} 说明：对于OPEN表中的叶节点直接移到 CLOSED表，不作任何处理
OPEN= {9, B, C, t1, 10, 11, 12, A} CLOSED= {1, 2, 3, 4, 5, 6, 7, 8}
第九大循环（3、4、5、6、7、8步）： 3、从OPEN表中取出节点9，并送到CLOSED表 4、扩展节点9，生成后继节点 t2、t3，并送到 OPEN表的末端 5、有叶节点 6、实现可解标志过程（可以判断节点9、4、2可解）
即OPEN是堆栈
注意
由于深度限制，深度优先搜索算法有可能找不 到解
例：
深度界限为4
√
2
1
√
√
6
√
3
Ⅹ A √ √
7 √
C
Ⅹ
4
5
8
t
√
Ⅹ B
t
t
t
t
√
√
√
√
注：后生成的节点画在左边
课堂练习：用宽度和深度优先搜索算法找出解树
提示：对于宽度优先搜索，先生成的节点画在左；
对于深度优先搜索，后生成的节点画在左
CLOSED= { 1, 2, 3, 4, 5, 6, 7, 8, 9, t1, 10 }
搜索过程演示
√

与或图搜索问题

与或图搜索问题

f
0
0 1
d b
0 3
m h
1
1
n e
k i
-3 1
6
a
0
c
-3
3
g
5 4
6
j
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
α-β剪枝
极大节点的下界为α。 极小节点的上界为β。 剪枝的条件：
后辈节点的β值≤祖先节点的α值时， α剪枝 后辈节点的α 值≥祖先节点的β值时， β剪枝
α-β剪枝的其他应用
故障诊断
A 风险投资
B
C
D
1
极大
1
b
0
极小
6
a
0
3
1
0
-3
3
-3
-3
-2
1
-3
6
-3
0
5
-3
3 3
-3
0
2
2
-3
0
-2
3 5 4
1
-3
0 6
8 9
-3
5 α-β剪枝
设某博弈问题如下图所示，应用极小极大方法进行搜索。假设搜索的 顺序为从下到上，从左到右。当计算完a的值为0后，由于b是极大节 点，马上就可以知道b的值大于等于0。接下来求c的值。由于c是极小 节点，由d的值为-3，知道c的值小于等于-3。而a和c都是b的子节点， 所以即便不扩展节点e，也可以知道b的值一定为0了。所以在这种情 况下，没有生成节点e的必要。同样，在知道b的值为0后，由于k是极 小节点，所以立即知道k的值要小于等于0。而通过节点f、g，知道h 的值至少为3。这样即便不扩展A所包围的那些节点，也能知道k的值 一定为0。所以A包围的那些节点也没有生成的必要，不管这些节点取 值如何，都不影响k的值。如果在搜索的过程中，充分利用这些信息， 不就可以少生成很多节点，从而提高搜索的空间利用率吗？α-β过程 正是这样一种搜索方法。

与或图搜索-2015

与或图搜索-2015

黄色：6 目标
2015-6-17 22 华北电力大学
AO*算法举例
n0 n1 n2 n4
初始节点
n1 5
n0
初始节点
n4(1)
n2(4)
n3
n5
n3(4)
n5(1)
2
n6(2)
n6
n8
n8(0)
目标
n7
红色：5
n7(0)
23
目标
2015-6-17
黄色：6
华北电力大学
AO*算法举例
n0
n1 n2
初始节点
（2,2,1,1,1）
对方扩展的节点
（2,1,1,1,1,1）
2015-6-17 27 华北电力大学
与或图搜索技术 问题
对简单的博弈或复杂博弈的残局，可以用类似于与或 图的搜索技术求出解图，解图代表了从开局到终局任 何阶段上的弈法 对许多博弈问题不可实现：
• 中国象棋：一盘棋平均走50步，总状态数约为10的161 次方。假设1毫微秒走一步，约需10的145次方年→→不 可能穷举 • 即使用了强有力的启发式搜索技术，也不可能使分枝压 到很少
2015-6-17
28
华北电力大学
与或图搜索技术
解决：
实用策略：把目标确定为寻找一步好棋，等对手回 敬后再考虑寻找另一步好棋 每一步结束条件可根据时间限制、存储空间限制或 深度限制等因素加以确定 搜索策略可采用宽度、深度或启发式方法，一个阶 段搜索结束后，要从搜索树中提取一个优先考虑的 “最好的”走步，这就是实用策略的基本点 极小极大搜索策略就是其中的一种
2015-6-17 11
华北电力大学
基本概念 局部图：
① 单一节点是一个局部图 ② 对于一个局部图的任意叶节点n，选择一个n的外向连 接符K，则该局部图、外向连接符K，以及K所连接的n 的后继节点一起组成的图，仍然组成一个局部图

与或图搜索

8
• 解图：
初始节点
目标
目标
该解图的耗散值为: (1+(1+1))+(1+1)=5
9
局部解图的耗散值计算
如果我们也将局部图的耗散值记为k(n,N),则: ① 若n是局部图的一个叶节点，则
k(n,N)=h(n)；
② 若n是一个外向连接符指向后继节点{n1,…, ni}，并设该连接符的耗散值为Cn，则
1
与或图例子
2
2.1 基本概念
与或图是一个超图，节点间通过连接符连接。
超图是图的最一般的表达形式，无论什 么图，你都可以说它是超图，就像无论 整数，无理数，复数，反正都是数一样。
超图的定义由两个集合构成：一个点集A， 另一个是点集A中元素的子集的集合B(B 中所有元素的并集就是集合A)。A中的元 素叫节点；B中的元素就叫边，这样超图 H=(A,B)。
17
与或树的一般搜索过程(续)
• 由上述搜索过程所形成的节点和指针 结构称为搜索树。 • 与或树搜索的目标是寻找解树，从而 求得原始问题的解。如果在搜索的某一 时刻，通过可解标示过程可确定初始节 点是可解的，则由此初始节点及其下属 的可解节点就构成了解树。
18
与或树的一般搜索过程(续)
• 如果在某时刻被选为扩展的节点不可扩 展，并且它不是终止节点，则此节点就 是不可解节点。此时可应用不可解标示 过程确定初始节点是否为不可解节点，
如果可以确定初始节点是不可解的，则搜 索失败；否则继续扩展节点。
19
与或树的性质
• 可解与不可解标示过程都是自下而上进行 的，即由子节点的可解性确定父节点的可解性。
• 在与或树中搜索解树时，如果已确定某个 节点为可解节点，则其不可解的后裔节点就不 再有用，可从搜索树中删去；同样，如果已确 定某个节点是不可解节点，则其全部后裔节点 都不再有用，可从搜索树中删去，但当前这个 不可解节点还不能删去，因为在判断其先辈节 点的可解性时还要用到它。

第3章产生式系统的搜索策略


四皇后问题的改进：
• 思路： 利用问题有关信息对规则进行动态排序
• 方法：定义一个对角线函数 Maxdiag（i，j）。该函 数计算棋盘上ij单元的最长对角线长度，通过比较 不同单元的函数值来决定每行（列） Rij 的排序
• 例如，若 Maxdiag（i，k）小于 Maxdiag（i，j）， 则规则顺序为（Rik，Rij），即对角线短的单元，相 应的规则排在前头，若相同，则维持原顺序
综合数据库：DATA=L（表），L元素用{ij}表示，i，j 的值域为{1，2，3，4}。即L表的元素表示皇后所在 的行和列。如（12 24 31 43）、（13 21 34 42）、 （11 21）、（11 22）、（11 23 31）.
Artificial Intelligence
• 规则集：
BACKTRACK1(DATALIST):
1 DATA FIRST(DATALIST) 参数: 初始到当前状态的逆序表 2 if MEMBER(DATA,TAIL(DATALIST), return FAIL 回老路 3 if TERM(DATA), return NIL 到达目标，成功返回 4 if DEADEND(DATA), return FAIL 到达不合理状态，退回 5 if LENGTH(DATALIST) > BOUND, return FAIL 到深度限制 6 RULES APPRULES(DATA) 得出可应用的规则集 7 LOOP: if NULL(RULES), return FAIL 进入死胡同，退回 8 R FIRST(RULES) 取出第一条可应用规则
过程返回解路径规则表（或局部解路径子表）.
Artificial Intelligence
举例

第3章搜索推理技术3与或树搜索

OPEN表的末端 5、无叶节点，转到3步
OPEN= { 2，3 } CLOSED= { 1 }
第二大循环（3、4、5步）： 3、从OPEN表中取出节点2，并送到CLOSED表 4、扩展节点2，生成后继节点4、5，并送到OPEN
表的末端 5、无叶节点，转到3步
OPEN= { 3, 4, 5 } CLOSED= { 1, 2 }
1、没有后裔的非终叶节点是不可解节点
2、如果某一个非终叶节点含有“或”后继节点， 那么，只要当所有的后继节点都不可解时，这一 个非终叶节点才是不可解的
3、如果某一个非终叶节点含有“与”后继节点， 那么，只要有一个后继节点是不可解的，这一个 非终叶节点就是不可解的
可解标志过程与不可解标志过程:
根据可解与不可解节点的递归定义，用递归的方 式作用于某一个与或图，以标出所有的可解节点 与不可解节点
注意
由于深度限制，深度优先搜索算法有可能找不 到解
例： 深度界限为4
√
1
√
√
2
6
√
3
ⅩA 7 √ C
Ⅹ
4
√
5
√
8
t√
ⅩB
t
t
t
t
√
√
√
√
注：后生成的节点画在左边
课堂练习：用宽度和深度优先搜索算法找出解树
提示：对于宽度优先搜索，先生成的节点画在左； 对于深度优先搜索，后生成的节点画在左
2 4
算法结束的条件：
➢ 若初始节点被标志为可解节点，算法成 功结束（有解）
➢ 若起始节点被标志为不可解节点，则搜 索失败结束（无解）
与或图的解图： 由最少的可解节点所构成的子图，这些节 点能够使问题的起始节点是可解的

第3章图搜索与问题求解


第 3 章 图搜索与问题求解 图 3-1 迷宫图
第 3 章 图搜索与问题求解 图 3-2 迷宫的有向图表示
第 3 章 图搜索与问题求解
例 3.2 在一个3×3的方格棋盘上放置着1, 2, 3, 4, 5, 6, 7, 8八个数码, 每个数码占一格, 且有一个空格。 这些数码可 在棋盘上移动, 其移动规则是：与空格相邻的数码方可移入空 格。现在的问题是：对于指定的初始棋局和目标棋局(如图3-3 所示), 给出数码的移动序列。该问题称为八数码难题或重排九 宫问题。
可以看出,图中的一条边(即相邻两个节点的连线)就对应一 次数码移动,反之, 一次数码移动也就对应着图中的一条边。而 数码移动是按数码的移动规则进行的。所以, 图中的一条边也 就代表一个移动规则或者移动规则的一次执行。于是,这个八数 码问题也就是要在该有向图中寻找目标节点, 或找一条从初始节 点到目标节点的路径问题。
按搜索范围的扩展顺序的不同, 搜索又可分为广度优先和 深度优先两种类型。对于树式搜索, 既可深度优先进行, 也可 广度优先进行。对于线式搜索则总是深度优先进行。
第 3 章 图搜索与问题求解
3. 搜索算法
由于搜索的目的是为了寻找初始节点到目标节点的路径, 所以在搜索过程中就得随时记录搜索轨迹。为此, 我们用一个 称为CLOSED表的动态数据结构来专门记录考查过的节点。显然, 对于树式搜索来说, CLOSED表中存储的正是一棵不断成长的搜 索树； 而对于线式搜索来说, CLOSED表中存储的是一条不断伸 长的折线, 它可能本身章 图搜索与问题求解
启发式搜索则是利用“启发性信息”引导的搜索。 所谓 “启发性信息”就是与问题有关的有利于尽快找到问题解的信 息或知识。例如：“欲速则不达”、“知已知彼, 百战不殆”、 “学如逆水行舟不进则退”等格言, 就是指导人们行为的启发 性信息。常识告诉我们,如果有向导引路, 则就会少走弯路而 事半功倍。 所以, 启发式搜索往往会提高搜索效率, 而且可 能找到问题的最优解。根据启发性信息的内容和使用方式的不 同, 启发式搜索又可分为许多不同的策略, 如全局择优、局部 择优、 最佳图搜索等等。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

(3 2 2) (3 3 3)
(1 1 1) (1 1 3)
(1 2 3)
(3 2 2) (3 2 1)
(3 3 1) (3 3 3)
(1 2 2)
(1 1 3)
(3 2 1)
(1 2 3)
(3 3 1)

小结
– 状态空间法与问题归约法的比较 状态空间——问题空间 操作——归约 求解路径——本原问题 – 归约就是化简，即把复杂问题分解为若干子
A
P1
P2
Pk
P1
P2
Pk
no n1 n2 n3 n5 n4
n6
n8
n7 与或图
– 与或图搜索 从代表原始问题的根节点开始，按一定的规则 (归约操作)进行与或扩展，直到代表本原问题 的终节点。 要选择适当的或分枝进行扩展，以求找到一个 最佳分解方案。 在与或图中搜索最佳分解方案，即在问题空间 搜索一个最佳解图。
解图－－－在与或图是无环的假定条件下，解图 可递归定义如下： 定义：一个与或图Ｇ中，从节点n到节点集Ｎ的 解图记为Ｇ’，Ｇ’是Ｇ的子图． ①若n是N的一个元素,则G’由单一节点组成; ②若n有一个指向节点{n1,n2,……nk}的外向连接 符K,使得从每一个ni到N有一个解图(i=1,2,……k), 则G’由节点n,连接符K,及{n1,n2,……nk}中的每一 个节点到N的解图所组成; ③否则n到N不存在解图. 同样可以递归定义局部图如下： ①单一节点是局部图 ②对于一个局部图的任意叶节点n，选择一个n 的外向连接符K，则该局部图、外向连接符K以及 K所连接的后继节点一起组成图，仍然组成一个局 部图
问题，且使得：

每个子问题比原问题好解； 这些子问题解决了，原问题就解决了。
– 归约法的分类 有序归约(分段归约) 无序归约(分解归约)
梵塔难题 求五边形的面积
与或图表示法
– 与扩展 将一个问题分解为若干 子问题， 所有的子问题 有解，原问题才有解。 K-联接符 – 或扩展 将一个问题转化为若干 子问题，只要一个子问 题有解，原问题就有解。 单线联接符
第三章
与或图搜索问题 ---问题归约法
§3.0 引言
归约(Reduction)
– 例1
问题1：现有煤气灶、水龙头、水壶和火 柴，你怎样烧水？ 答：向水壶中注满水，把水壶放在煤气 灶上，擦火柴点燃煤气灶。 •问题2：问题1中其他情况不变，只是水壶 中已经灌满了水，你怎样烧水？
答：把水壶放在煤气灶上，擦火柴点燃煤气 灶或擦火柴点燃煤气灶，把水壶放在煤气灶上。

将上面的分析理一下顺序：就把原问题归约 为3个子问题：
– 移动A、B至柱2的双圆盘问题； – 移动C至柱3的单元盘问题；（本原问题） – 移动A、B至柱3的双圆盘问题。
– 将梵塔问题归约为本原问题的问题空间
(1 1 1) (3 3 3)
(1 1 1) (1 2 2)
(1 2 2) (3 2 2)
问题，对子问题再归约，直至成为可 以直接求解的本原问题。
§3.1问题空间及与或图表示

梵塔难题的两种解法 A – 状态空间法 B

1
2
3
C 初始数据库 (1 1 1) 表示C, B, A三个盘都在柱1上 目标数据库 (3 3 3) 表示C, B, A三个盘都在柱3上

状态空间
(1 1 1) 其中(i j k)表示 MOVE(A,1,3) C在柱i, B在柱j, (1 1 2) (1 1 3) MOVE(B,1,2) A在柱k上 (1 2 3) (1 3 2) MOVE(A,3,2) (1 3 3) (1 2 2) (1 3 1) (1 2 1) MOVE(C,1,3) (2 3 3) (3 2 2) MOVE(A,2,1) (2 3 1) (3 2 1) (2 3 2) (3 2 3) MOVE(B,2,3) (2 2 1) (2 1 2) (3 1 3) (3 3 1) MOVE(A,1
3
②
求解步骤：
① I 1 求五边形面积 求 1面积 求 I面积 求 2面积 求 II面积 求 3面积 求 III面积 求• ③面积 2 II III
本原问题
– 可直接得到答案的问题称为本原问题 例1中的原始的烧水问题 例2中根据鸽巢原理直接可回答的问题 例3中求矩形面积的问题 归约法 – 把原问题转化(分解)为一个或几个子
– 若干概念 终节点 可解节点 不可解节点 解图 耗散值 最佳解图 可解过程 不可解过程
与或图中某一个节点n到节点集N的一个解图类似于普 通图中的一条解路径。

解图的求法：从节点n开始，正确选择一个外向 连接符，在从该连接符所指的每一个后继节点出 发，继续选一个外向连接符，如此进行下去直到 由此产生的每一个后继节点成为集合N中的一个 元素为止． n n
例2 在边长为2的正方形内，任意放置5个点 ，求证其中必存在两个点，它们之间的距 离不大于2。 . 问题可转化为： . 在四个单位正方形内， . 任意放置5个点，至少 . . 有两个点在同一正方形内。
例3
假定我们已经会求 矩形的面积，现在要 求如图所示的五边形 的面积。
①
I 1
III ③
2 II


解图的生成——自根节点开始选一外向连接， 并从该连接指向的每个子节点出发，再选一 外向连接，如此反复进行，直到所有外向连 接都指向终节点为止。 * 解图纯粹是一种“与”图； *由于与或图中存在“或”关系；可产生或 搜索到多个解图（上图）， * 解图应无环，即任何节点的外向连接均不 得指向自己或自己的先辈，否则会使搜索陷 入死循环。
S
(2 2 2)
(2 1 3) (3 1 1) (3 3 2) (3 3 3) (2 2 3) (2 1 1) (3 1 2)
t

采用归约法
– 要把所有圆盘移至柱3，必须先把C盘移至
柱3，而在移动C盘至柱3前，柱3必须为空。 – 只有把A、B移至柱2后，才能将C移到柱3。 – 在C移至柱3后，再解决将A、B移至柱3。
o 0
n1 n3 n5 n5 n4 n5
n0
n4
n8
no n7
n8
（1）
n7
（2） 三个解图
n8 n7 （3）
·K-连接——表示从父节点到子节点间的连接 * 也称为父节点的外向连接， * 以园弧指示同父子节点间的“与”关系， * K为这些子节点的个数，K>1时成为超连接， * 一个父节点可以有多个外向的K-连接。 * 当所有超连接的K都等于1时，与或图蜕化为一 般图。 · 根、叶、终节点 * 无父节点的节点——根节点，用于指示问题的 初始状态； * 无子节点的节点——叶节点。 * 用于联合表示目标状态的节点——终节点， * 终节点必定是叶节点，反之不然；