当前位置：文档之家 › 盲目搜索启发式搜索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课件


失败
扩展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课件

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的 指针，以便一旦找到目标节点时记住一个解答路径。
  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