当前位置：文档之家 › 盲目搜索启发式搜索PPT课件

盲目搜索启发式搜索PPT课件

  • 格式：ppt
  • 大小：2.22 MB
  • 文档页数：60

下载文档原格式

  / 60

合集下载

智能控制-第三章--搜索推理技术概要PPT课件

智能控制-第三章--搜索推理技术概要PPT课件
第三章 搜索推理技术
3.1 图搜索策略 3.2 盲目搜索 3.3 启发式搜索 3.4 消解原理 3.5 规则演绎系统
3.6 产生式系统 3.7 系统组织技术 3.8 小结
3.1 图搜索策略
❖ 图搜索控制策略 一种在图中寻找路径的方法。 图中每个节点对应一个状态，每条连线对应 一个操作符。这些节点和连线又分别由产生 式系统的数据库和规则来标记。求得把一个 数据库变换为另一数据库的规则序列问题就 等价于求得图中的一条路径问题。
5）若n为一目标节点，则有解并成功退出，此 解是追踪图G中沿着指针从n到S这条路径而 得到的(指针将在第7步中设置)。
.
3.1 图搜索策略
6）扩展节点n，同时生成不是n的祖先的那些后 继节点的集合M。把M的这些成员作为n的后 继节点添入图G中。
7）对那些未曾在G中出现过的M成员设置一个 通向n的指针。把M的这些成员加进OPEN表。 对已经在OPEN或CLOSED表上的每一个M成 员，确定是否需更改通到n的指针方向。对已 在CLOSED表上的每个M成员，确定是否需 要更改图G中通向它的每个后裔节点的指针方 向。
是否有后继节点 为目标节点？
否
是 成功
图3.2 宽度优先算法框图
.
❖ 例子
八数码难题（8-puzzle problem）
3.2 盲目搜索
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
（目标状态）
规定：将棋子移入空格的顺序为：从空格左边开 始顺时针旋转。不许斜向移动，也不返回先辈节 点。从图可见，要扩展26个节点，共生成46个 节点之后才求得解（目标节点）。
.
深度优先搜索示意图

搜索PPT演示课件

搜索PPT演示课件
迭代加深搜索是最优的，也是完备的 重复搜索深度较小的节点，是否浪费？
10
例 聪明的打字员
阿兰是某机密部门的打字员，她现在接到一个 任务：需要在一天之内输入几百个长度固定为 6的密码。当然，她希望输入的过程中敲击键 盘的总次数越少越好。
不幸的是，出于保密的需要，该部门用于输入 密码的键盘是特殊设计的，键盘上没有数字键， 而只有以下六个键：Swap0, Swap1, Up, Down, Left, Right，为了说明这6个键的作用，我们先 定义录入区的6个位置的编号，从左至右依次 为1，2，3，4，5，6。
宽度优先搜索（Breadth-first search） 深度优先搜索（Depth-first search）
6
宽度优先搜索
优点
目标节点如果存在，用宽度优先搜索算法总可 以找到该目标节点，而且是最小（即最短路径） 的节点
缺点
当目标节点距离初始节点较远时，会产生许多 无用的节点，搜索效率低
11
例 聪明的打字员
Swap0：按Swap0，光标位置不变，将光标所在位置的数字与录入区的1号位置 的数字（左起第一个数字）交换。如果光标已经处在录入区的1号位置，则按 Swap0键之后，录入区的数字不变
Swap1：按Swap1，光标位置不变，将光标所在位置的数字与录入区的6号位置 的数字（左起第六个数字）交换。如果光标已经处在录入区的6号位置，则按 Swap1键之后，录入区的数字不变
4
搜索问题
搜索问题：在一个空间中寻找目标
搜索什么（目标） 在哪里搜索（状态空间）
在搜索中，如何扩展状态空间是关键性问题 搜索可以根据是否使用启发式信息分成
盲目搜索：只能区分当前状态是否为目标状态 启发式搜索：在搜索过程中加入与问题相关的

启发式搜索(共49张PPT)

启发式搜索(共49张PPT)
f(x)=g(x)+h(x)
其中：g(x)——从初始节点S0到节点x的实际代价； h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问
题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式 函数。
2022/10/14
6
评估函数
启发式方法把问题状态的描述转换 成了对问题解决程度的描述。
这一程度用评估函数的值来表示。
2022/10/14
7
评估函数
S
搜索图G
2022/10/14
n ng
初始状态节点S
f(n):s-n-ng的估计最小路径代价
g(n):s-n的实际路径代价 h(n): n-ng的估计最小路径代价
节点n
目标状态节点ng
8
启发式搜索A算法
A算法的设计与一般图搜索相同，划分为二个阶段：
IF f(ni)>f(n,ni) THEN 令f(ni)=f(n,ni)
修改指针指向新父结点n
排序OPEN表（f(n)值从小到大排序）
2022/10/14
10
2022/10/14
4功指1搜 未做.若.退针建扩C索nL出从立为展图O，n一S一节到GE个此,目的把点S只这解标已S表放条包是扩节中路到含追展点；径一节起踪，建而个点始图则立得叫表节G有一到中O，点解P个的沿其ES成N叫；的初着的
始为空表；
5.扩展节点n，同时生成不是n的 祖 M2出的.先若；这的OP些那EN成些表员子是作节空为点表n，的的则集后失合继败节M,退点把 添入搜索图G中；对于M中每个 子3把 表.节选中它点f择(，从nnO,称nOi,P计iP)E此EN=算N表节g表:(n上点移,n为的出i) +节并第h放点一(n进in)个；C节LO点SE，

5-搜索之BFSPPT演示课件

5-搜索之BFSPPT演示课件

while(队列不空){
v2
取出队头结点;
1
V2不是终点
若它是所求的目标状态,跳出循环;
否则，从它扩展出子结点,全都添到队尾;
}
若循环中找到目标,输出结果; 否则输出无解;
•21.01.2024
•24
V2
v1 v2 v4 v5 v6 v3
0 11112V1Fra bibliotekV4V3
定义一个队列; 起始点加入队列; while(队列不空){
V2
V1
V4
定义一个队列;
V6
起始点加入队列;
V5
while(队列不空){
取出队头结点;
若它是所求的目标状态,跳出循环;
否则，从它扩展出子结点,全都添到队尾;
}
若循环中找到目标,输出结果; 否则输出无解;
•21.01.2024
•22
v1 v2 v4 v5 v6 0 1111
V2
V1
V4
定义一个队列;
•21.01.2024
•12
BFS思想
1的.从(所图有中未某被顶访点问v的0出)邻发接，顶在点访v问1了.vv20…之后，搜索v0 2.依次从这些邻接顶点出发，广搜图中其它顶点，
直至图中所有已被访问的顶点的邻接顶点都被访问 到。 3.若此时图中还有未被访问到的顶点，则再选择其 中之一作为v0重复上述过程。直到图中所有顶点 均被访问到。
若它是所求的目标状态,跳出循环;
否则，从它扩展出子结点,全都添到队尾;
}
若循环中找到目标,输出结果; 否则输出无解;
•21.01.2024
•27
V2
v1 v2 v4 v5 v6 v3
0 11112

6第六讲 第三章(盲目、启发搜索)

6第六讲 第三章(盲目、启发搜索)

二、有序搜索
用估价函数 f 来排列OPEN表上的节点。
应用某个算法选择OPEN表上具有最小f 值的节点作为
二、宽度优先搜索
例3.2 八数码问题 操作规定: 允许空格四周上、下、左、右的数码 块移入空格中，不许斜方向移动，不许返回先辈 结点。
1 2 3 8 5 7 4 6
1
4
1 3 8 2 5 7 4 6
2
1 2 3 8 4 5 7 6
3
1 2 3 8 5 7 4 6
5
1 2 3 8 5 7 4 6
深度优先搜索的特点
OPEN表为堆栈，操作是后进先出（LIFO） 深度优先又称纵向搜索。 一般不容易保证找到最优解（如下图所示） 防止搜索过程沿着无益的路径扩展下去，往往 给出一个节点扩展的最大深度——深度界限。
2、有界深度优先搜索
引入搜索深度限制值d，使深度优先搜索具有完备性 。 （1）深度界限的选择很重要 d若太小，则达不到解的深度，得不到解；若太大，既 浪费了计算机的存储空间与时间，降低了搜索效率。由于 解的路径长度事先难以预料，要恰当地给出d的值是比较 困难的。 （2）即使能求出解，它也不一定是最优解。 例3.3：设定搜索深度限制d=5的八数码问题。
4. 搜索过程框图
S0放入OPEN表 是 OPEN表空？ 否 将OPEN表中第一个节点(n) 移至CLOSE表 否 n是目标节点？ 扩展节点n，把n的后继节点放入 OPEN表末端，提供指向 节点n的指针 修改指针方针，重排OPEN表
失败
是
成功
一、图搜索策略(Graph Search) 5.图搜索方法分析：
3.2 启发式搜索
盲目搜索的不足：效率低，耗费空间与时间。 启发式搜索：利用问题本身特性信息（启发信息） 指导搜索过程。是有序搜索。 一、启发式搜索策略 启发式信息主要用途：

3.3-启发式搜索(2)PPT课件

3.3-启发式搜索(2)PPT课件
(5) If 栈为空并且 c, Then cc , 并返回2
End
.
25
迭代加深A*算法
上述算法涉及了两个深度限制:
(1)如果栈中所含节点的所有子节点的f值小于 限制值c,则把这些子节点压如栈中以满足迭代 加深算法的深度优先准则.
(2)如果不这样,即节点n的一个或多个子节点 n 的f值大于限制值c,则节点n的 c 值设置为 micn,f((n))
节点的最佳路径的总代价的估值。
.
16
A*算法
把估价函数f (n)和 f *(n)相比较：
g (n)是对 g*(n)的估计。 h (n)是对h* (n)的估计。
在这两个估计中，尽管g (n)容易计算，但它不 一定就是从起始节点S0到节点n 的真正的最短 路径的代价，很可能从初始节点S0到节点n 的 真正最短路径还没有找到，所以一般都有：
该算法终止的条件为:
(1)找到目标节点(成功结束); (2)栈为空并且限制值 c 。
.
26
迭代加深A*算法
IDA*算法和A*算法相比，主要优点是对于内存 的需求。A*算法需要指数级数量的存储空间，因 为没有深度方面的限制。而IDA*算法只有当节点 n的所有子节点 的 n 小f (于n)限制值c时才扩展 它,这样就可以节省大量的内存。
点 x 是从初始节点经过m步得到，则g (x) 应该和 m 成正比（或者就是m）。 如何计算h(x)呢? h (x) 只是一个预测值。
.
3
图搜索算法（A算法）(P78:算法3.8)
Procedure Graph-Search
Begin 建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表；计算f(S0)=g(S0)+h(S0); 假定初始时CLOSED表为空。 While OPEN 表不空 do Begin 从OPEN表中取出f值最小的节点(第一节点),并放入CLOSED表中.假设该节点 的编号为n。 If n是目标,则停止;返回n,并根据n的反向指针指出的从初始节点到n的路径。 Else do

图搜索—图搜索策略ppt课件

图搜索—图搜索策略ppt课件

失败
扩展n，把n的后继节点放入OPEN 表的末端，提供返回节点n的指针
是否有后继节点 为目标节点？
是 成功
否 图3.2 宽度优先算法框图
思考：与原始算法比较异同，宽度优先的体现？
14
3.2 盲目搜索
例子 八数码难题（8-puzzle problem）
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
❖各自特点：重排OPEN表的依据不同。
❖盲目搜索可能带来组合爆炸。
启发式信息：用来加速搜索过程的问题领域信息，一般与有关问题
具体领域背景有关，不一定具有通用性。
启发式搜索：利用启发式信息的搜索方法
– 特点：重排OPEN表，选择最有希望的节点加以扩展
– 种类：有序搜索、A*算法等
24
3.3 启发式搜索
失败
节点n的深度等于最大深度？ 否
扩展n，把n的后继节点放入OPEN 表的前端，提供返回节点n的指针
是否有后继节点 为目标节点？
是 成功
否
图3.6 深度优先算法框图
19
3.2 盲目搜索
示范：有界深度(4)优先的八数码问题深度优先 搜索树？
28 3
1
4
76 5
（初始状态）
12 3
8
4
76 5
（目标状态）
是依据f(x)=g(x)+h(x)进行的，则称该过程为A算法。
– 定义2 在A算法中，如果对所有的x存在h(x)≤h*(x),则称h(x)
为h*(x)的下界，它表示某种偏于保守的估计。
– 定义3 采用h*(x)的下界h(x)为启发函数的A算法，称为A*算 法。当h=0时，A*算法就变为等代价搜索算法。

盲目搜索启发式搜索

盲目搜索启发式搜索

2015-3-22
39
有序状态空间搜索算法
(6) 扩展节点i生成其全部后继节点。对于i的每一个后继节点j： – (a) 计算f(j)。 – (b) 如果j既不在OPEN表中，又不在CLOSED表中，则用估 价函数 f 把它添入 OPEN 表。从 j 加一指向其父辈节点 i 的指 针，以便一旦找到目标节点时记住一个解答路径。 – (c) 如果 j 已在 OPEN 表上或 CLOSED 表上，则比较刚刚对 j 计算过的f值和前面计算过的该节点在表中的 f值。如果新 的f值较小，则 (i) 以此新值取代旧值。 (ii) 从j指向i，而不是指向它的父辈节点。 (iii) 如果节点j在CLOSED表中，则把它移回OPEN表 (7) 转向(2)，即GO TO(2)。
2015-3-22
24
3.1.3 深度优先搜索
2015-3-22
25
有界深度优先搜索
定义节点的深度如下： (1) 起始节点(即根节点)的深度为0。 (2) 任何其它节点的深度等于其父辈节点深度加上1。 • 对于许多问题，其状态空间搜索树的深度可能为无限深， 或者可能至少要比某个可接受的解答序列的已知深度上限 还要深。为了避免考虑太长的路径(防止搜索过程沿着无 益的路径扩展下去 ) ，往往给出一个节点扩展的最大深 度——深度界限。任何节点如果达到了深度界限，那么都 将把它们作为没有后继节点处理。值得说明的是，即使应 用了深度界限的规定，所求得的解答路径并不一定就是最 短的路径。

CLOSED表变化过程
编号 0 ቤተ መጻሕፍቲ ባይዱ 2 节点号 S0 A B 父节点号 空 S0 S0
图搜索的一般过程
(1) 建立一个只含有起始节点S的搜索图G，把S放到一 个叫做OPEN表的未扩展节点表中。 (2)建立一个叫做CLOSED的已扩展节点表，其初始为 空表。 (3)LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出 并放进CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点，则有解并成功退出，此解是追 踪图G中沿着指针从n到S这条路径而得到的(指针将 在第7步中设置)。

3-4启发式搜索策略PPT课件

3-4启发式搜索策略PPT课件
4
fn
n
…
hn
…
11
gn
33
定义一个评价函数 f
3.4.2 局部择优搜索
• 基本思想 ： 当一个节点扩展后, 在它的所有子
节点中，选估价函数f(n)最优者作为下一 个考察的节点 。
• 例1 ：用局部择优搜索策略求解八数码问题。
估价函数定义为f(n)= g（n）+h(n) 。 其中， g（n）=d(n)表示搜索depth,等代价时, g（n）对局
在OPEN表中保留所有已生成而未扩展的节点，并 用估价函数f(n)对它们全部进行估计，and sort!
❖ 得到的不一定是实际上的最佳解。
Answer: Design proper f(n). otherwise
QuestionS：
① how many h(w) of the states are ？
3.4 启发式搜索策略
➢ 启发信息和估价函数
➢ A*算法
Background
and Questions:
1. 宽度优先、深度优先搜 索属于盲目搜索（按规 定的路线搜索）。盲目 搜索效率低，耗费过多 的计算空间与时间。
2. 2. 若选择最有希望的节
点加以扩展(NOT按规定
的路线盲目搜索) ，则搜
索效率将会大为提高。
28 3
16 4
7
5
c)
W(n)=4 steps=5
2
3
18 4
76 5
b)
W(n)=3 steps=3
1 23 84
76 5
a)
31
W(n)=1 steps=1
Compare global and local
h(n)＝W(n)

盲目搜索启发式搜索

盲目搜索启发式搜索

B
S0
C
S0
D
S0
E
A
F
A
CLOSED表变化过程
编号
0 1 2
节点号
S0 A B
父节点号
空 S0 S0
图搜索的一般过程
(1) 建立一个只含有起始节点S的搜索图G，把S放到一 个叫做OPEN表的未扩展节点表中。
(2)建立一个叫做CLOSED的已扩展节点表，其初始为 空表。
(3)LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出ຫໍສະໝຸດ 失败 成功一、盲目搜索
盲目搜索又叫做无信息搜索，一般只适用于求解比较简 单的问题。主要包括宽度优先搜索、等深度优先搜索等。 特点：
1）搜索按规定的路线进行，不使用与问题有关的启发性 信息。
2）适用于其状态空间图是树状结构的一类问题。
13
1、 宽度优先搜索
定义：如果搜索是以接近起始节点的程度依次扩展节点的， 那么这种搜索就叫做宽度优先搜索(breadth-first search)。
(8) 按某一任意方式或按某个探试值，重排OPEN表。 (9) GO LOOP。
开始
把S放入OPEN表
是 OPEN表为空表？
否 把第一个节点(n)从OPEN表移至CLOSED表
n为目标节点吗？
是
否
把n的后继节点放入OPEN表的 末端，提供返回节点n的指针
修改指针方向 重排OPEN表
图搜索一般过程的框图
2024/7/19
39
有序状态空间搜索算法
(6) 扩展节点i生成其全部后继节点。对于i的每一个后继节点j：
– (a) 计算f( j)。
– (b) 如果j既不在OPEN表中，又不在CLOSED表中，则用 估价函数f把它添入OPEN表。从j加一指向其父辈节点i的 指针，以便一旦找到目标节点时记住一个解答路径。

启发式搜索ppt课件

启发式搜索ppt课件
a) 计算g(mi)=g(n)+ C(n, mi); f=g(mi)+h(mi); b) 如计op果算en表m的i或已g(mc经lio)存小se在d于表于等中o于p取e当n出表前与中的m或gi相(者m同i在)，的c那l子os么结edg点表ot中mo 6i，’。且否先则前从 c) 令mi ：= mi’ ，将mi的父指针指向n d) 将结点mi插入到open表，然后将open表按f值排序。 7. goto 3
h = max(h1, h2 ,······, hm)
• 从经验中学习：已知某些特征x1与x2和h有关，但 不知道具体的关系，那么可以定义 h=c1x1 +c2x2 通过学习调整c1与c2。
• ABSOLVER程序能自动生成启发式。魔方的第一 个有用的启发式就是它找到的
• 模式数据库
h(n)对搜索效率的影响
– 每个边的代价都大于ε,于是，Open表中的所有
结 所点有的结g点(n的)值f(都n)将都超将过超f过*(fn*0()n，0) 也。就是说， – 这于引理1的结论3矛盾， – 故A*算法必定会终止
定理一的证明（2）
• A*终止于一条最优路径上（反证法）：
– A*只能终止于第3步或第5步。终止于第3步的情况只能 出现在不包含任何结点的有限图中。这与已知条件
• 二维地图上的路径规 划
– h1=0 – h2取欧氏距离 – h3取城市距离 – h4取10倍的欧氏距离 – h5取20倍的欧氏距离
– h1≤h2 ≤ h3 ≤ h4 ≤ h5
代价 结点 h1 136.1 12002 h2 136.1 2045 h3 138.0 672 h4 304.0 147 h5 468.5 131
“从开始结点n0到目标结点有一条有限代价的路径”矛

人工智能 第1章 搜索问题PPT课件

人工智能 第1章 搜索问题PPT课件
8, 对OPEN中的节点按某种原则重新排序； 9, GO LOOP；
34
节点类型说明
…...
…...
…...
mk
mj
ml
…...
…...
35
修改指针举例
s
1
2 6
3
4
5
36
修改指针举例（续1）
s
1
2 6
3
4
5
37
修改指针举例（续2）
s
1
2 6
3
4
5
38
修改指针举例（续3）
s
1
2 6
3
4
5
39
31
一些基本概念（续2）
• 扩展一个节点 生成出该节点的所有后继节点，并给出它 们之间的耗散值。这一过程称为“扩展一 个节点”。
32
一般的图搜索算法
1, G=G0 (G0=s), OPEN:=(s); 2, CLOSED:=( ); 3, LOOP: IF OPEN=( ) THEN EXIT(FAIL); 4, n:=FIRST(OPEN), REMOVE(n, OPEN),
– 盲目搜索 – 启发式搜索
• 关键问题： 如何利用知识，尽可能有效地找到问题 的解（最佳解）。
1
整体 概述
一 请在这里输入您的主要叙述内容
二
请在这里输入您的主要 叙述内容
三 请在这里输入您的主要叙述内容
2
问题的状态空间表示
• 状态空间可用三元组（S,O,来描述。
S：状态的集合，状态是某种事实的符号或数据 O：操作算子，利用它将一个状态转化为另一状态 G：S的非空子集，表示目标状态集 S0：初始状态，也是S的非空子集

第五章 启发式搜索课件.

第五章 启发式搜索课件.
❖ 为了保证找到解，应选择合适的深度限制值，或采取不断加 大深度限制值的办法，反复搜索，直到找到解。
❖ 与宽度优先搜索根本的不同点：将扩展的后继节点放在 OPEN表的最前端。
5.3.3 深度优先搜索策略
▪ 例3 卒子穿阵问题，要求一卒子从顶部通过下图所
示的阵列到达底部。卒子行进中不可进入到代表敌
兵驻守的区域（标注1），并不准后退。假定深度
（状态）
（操作算子）
状态空间的有向图描述
第5章 搜索求解策略 ▪ 5.1 搜索的概念 ▪ 5.2 状态空间知识表示方法
✓5.3 盲目的图搜索策略
▪ 5.4 启发式图搜索策略 ▪ 5.5 与/或图搜索策略
5.3 盲目的图搜索策略 5.3.1 回溯策略 5.3.2 宽度优先搜索策略 5.3.3 深度优先搜索策略
特点：逐层搜索；高价搜索：若解存在，必能找到。
5.3.2 宽度优先搜索策略
▪ 例2 通过搬动积木块，希望从初始状态达到一个目 的状态，即三块积木堆叠在一起。
A BC
(a) 初始状态
积木问题
A B C
(b) 目的状态
5.3.2 宽度优先搜索策略
▪ 操作算子为MOVE（X，Y）：把积木X搬到Y（积 木或桌面）上面。MOVE（A，Table）：“搬动积木A到桌
G ：若干具体状态或满足某些性质的路径信息描述。
5.2.1 状态空间表示法 ▪ 求解路径：从S0结点到G结点的路径。
状态空间的一个解：一个有限的操作算子序列。
S0 O1S1 O2 S2 O3Ok G
O1,,Ok ：状态空间的一个解。
❖ 例如下棋、迷宫及各种游戏。
5.2.1 状态空间表示法 ▪ 例1 三数码问题（3 puzzle problem）。
  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

失败 成功
12
一、盲目搜索
盲目搜索又叫做无信息搜索，一般只适用于求解比较简 单的问题。主要包括宽度优先搜索、等深度优先搜索等。 特点：
1）搜索按规定的路线进行，不使用与问题有关的启发性 信息。
2）适用于其状态空间图是树状结构的一类问题。
.
13
1、 宽度优先搜索
定义：如果搜索是以接近起始节点的程度依次扩展节点的， 那么这种搜索就叫做宽度优先搜索(breadth-first search)。
• 路径——在一系列节点n1,n2,,nm中， 从n1开始，ni总有分枝连接ni+1，称从n1 到nm之间的分枝集合是路径。路径中不 包含两个及以上相同的分枝，如果n1和 nm是同一个节点，则称这种路径为闭路。 不构成闭路的称为树。
• 在用状态空间图来表示问题时，对问题
的求解就是求出从初始节点到目标节点
目标节点，则求得一个解答)。 (2) 如果OPEN是个空表，则没有解，失败退出；否
则继续。 (3) 把第一个节点(节点n)从OPEN表移出，并把它放
入CLOSED扩展节点表中。 (4) 扩展节点n。如果没有后继节点，则转向上述第
(2)步。 (5) 把n的所有后继节点放到OPEN表的末端，并提供
从这些后继节点回到n的指针。 (6) 如果n的任一个后继节点是个目标节点，则找到
(8) 按某一任意方式或按某个探试值，重排OPEN表。
(9) GO LOOP。
.
11
开始
把S放入OPEN表
OPEN表为空表？
是
否
把第一个节点(n)从OPEN表移至CLOSED表
n为目标节点吗？
是
否
把n的后继节点放入OPEN表的 末端，提供返回节点n的指针
修改指针方向
重排OPEN表
图搜索一. 般过程的框图
一个解答，成功退出；否则转向第(2)步。
2020/5/14
.
16
宽度优先搜索算法框图
.
17
宽度优先搜索方法分析：
• 宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一 般过程中的第8步具体化为本算法中的第6步，这实际是 将OPEN表作为“先进先出”的队列进行操作。
• 宽度优先搜索方法能够保证在搜索树中找到一条通向目标 节点的最短途径；这棵搜索树提供了所有存在的路径(如 果没有路径存在，那么对有限图来说，就说该法失败退出； 对于无限图来说，则永远不会终止)。
(7) 对那些未曾在G中出现过的(既未曾在OPEN表上或 CLOSED表上出现过的)M成员设置一个通向n的指针。 把 M 的 这 些 成 员 加 进 OPEN 表 。 对 已 经 在 OPEN 或 CLOSED表上的每一个M成员，确定是否需要更改通 到n的指针方向。对已在CLOSED表上的每个M成员， 确定是否需要更改图G中通向它的每个后裔节点的 指针方向。
基本思想：从初始节点S开始，逐层地对节点进行扩展并考 察它是否为目标节点，在第n层的节点没有全部扩展并考 察之前，不对第n＋1层的节点进行扩展。OPEN表中的节 点总是按进入的先后顺序排列，先进入的节点排在前面， 后进入的排在后面。
.
14
宽 度 优 先 搜 索 示 意 图
.
15
宽度优先搜索算法： (1) 把起始节点放到OPEN表中(如果该起始节点为一
的路径。
.
3
图搜索策略
1. 图搜索的定义——一种计算机在状态图 中寻找路径的方法。
.
4
2.CLOSED表的引入
CLOSED表 (记录扩展过的节点)
编号 节点号 父节点号
.
5
3. OPEN表的引入
OPEN表 (记录待扩展的节点)
节点号 父节点号
.
6
举例：八数码魔方例子中
.
7
OPEN表变化过程
.
18Байду номын сангаас
例如：宽度优先搜索用于八数码难题。这个问题 就是要把初始棋局变为如下目标棋局的问题：
搜索树上的所有节点都标记它们所对应的状态描 述，每个节点旁边的数字表示节点扩展的顺序(按 顺时针方向移动空格)。图中最后一个节点是目标 节点。
.
19
八数码难题的宽度优先搜索树
26
.
20
对应动态演示图
.
21
节点号 父节点号
S0
空
A
S0
B
S0
C
S0
D
S0
E
A
F
A
.
8
CLOSED表变化过程
编号
0 1 2
节点号
S0 A B
父节点号
空 S0 S0
.
9
图搜索的一般过程
(1) 建立一个只含有起始节点S的搜索图G，把S放到一 个叫做OPEN表的未扩展节点表中。
(2)建立一个叫做CLOSED的已扩展节点表，其初始为 空表。
(3)LOOP：若OPEN表是空表，则失败退出。 (4) 选择OPEN表上的第一个节点，把它从OPEN表移出
并放进CLOSED表中。称此节点为节点n。 (5) 若n为一目标节点，则有解并成功退出，此解是追
踪图G中沿着指针从n到S这条路径而得到的(指针将 在第7步中设置)。
.
10
图搜索的一般过程
(6) 扩展节点n，同时生成不是n的祖先的那些后继节点 的集合M。把M的这些成员作为n的后继节点添入图 G中。
.
1
与图有关的术语
❖ 状态空间图——由节点(不一定是有限的 节点)及连接节点的分枝的集合构成。
❖ 有限节点图——节点数目有限的图称为 有限节点图。
❖ 有向图——一对节点用分枝线连接起来， 从一个节点指向另一个节点。这种图叫 做有向图。始节点叫父节点或双亲节点， 终节点叫子节点。
.
2
• 扩展——求解父节点的所有子节点，叫 做扩展。
搜索原理
什么是搜索？ 根据问题的实际情况不断寻找可利用的知识，从而构造 一条代价较少的推理路线，使问题得到圆满解决的过程。
• 盲目搜索 按预定的控制策略进行搜索，在搜索过程中获得的中间 信息不用来改进控制策略。效率低、主要用于简单问 题求解。
• 启发式搜索 在搜索中加入了与问题有关的启发性信息，用以指导搜 索朝着最有希望的方向前进，加速问题的求解过程并 找到最优解。
.
23
3、深度优先搜索
在深度优先搜索中，首先扩展最新产生的(即最深的)节点 （深度相等的节点可以任意排列）。其结果是搜索沿着状态 空间某条单一的路径从起始节点向下进行下去；只有当搜索 到达一个没有后裔的状态时，它才考虑另一条替代的路径。 替代路径与前面已经试过的路径不同之处仅仅在于改变最后 n步，而且保持n尽可能小。
2、 深度优先搜索
基本思想：
从初始节点S开始，在其子节点中选择一个节点进行 考察，若不是目标节点，则再在该子节点中选择一个节 点进行考察，一直如此向下搜索。当到达某个子节点， 且该子节点既不是目标节点又不能继续扩展时，才选择 其兄弟节点进行考察。
2020/5/14
.
22
深度优先搜索示意图
2020/5/14