是否为目标节点，在第n层的节点没有全部扩展并考察之前， 不对第n+1层的节点进行扩展。Open表中的节点总是按进入 的先后顺序排列，先进入的节点排在前面，后进入的排在后面。
（2）搜索过程
① OPEN:=S0 ② LOOP: IF(OPEN)=( ) THEN EXIT(FALL) ③ n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED) ④ IF GOAL(n) THEN EXIT(SUCCESS) ⑤ IF EXPAND(n)=( ) GO LOOP ⑥ EXPAND(n)→M(mi),ADD(mi,OPEN), mi↑→n;
⑦按某种搜索策略对OPEN表中的节点进行排序
⑧转第②步 GO LOOP
扩展节点1,生成单一后 继节点2,2已有父节点3,
●代表已扩展节点,位于CLOSED表上 ○代表未扩展节点,位于OPEN表上
从S0-2的代价为4,从 →有向边旁的箭头是指向父节点的指
S0-2的代价为2,后者代 价小,修改节点2指向父
15
2 83
71 4
6
5
16
1 23 84
76 5
17
2 34 18 76 5
18
2
8
143
76 5
19
2 83
145
7
6
20
2 83 64
针,每边代价为1
●S0
节点的指针
○
扩展节点4,节点4是节点
●
●
○1
6的后继节点, S0-4的代
价为4,从S0-4的代价为3,
修改节点4的父节点
○
●
●
●2
●6
●3
○5
○
4
开始
把S放入OPEN表
OPEN表为空表？
是
否
把第一个节点(n)从OPEN表移至CLOSED表
n为目标节点吗？
是
否
把n的后继节点放入OPEN表中， 提供返回节点n的指针
14 76 5
3
2
3
1 84
76 5
2 8 34
14 76 5
2 8 35
1 64
7
5
6
83 214 76 5
7
2 83 7 14
65
8
23 184 76 5
9
23 1 84 76 5
10
28 1 43 76 5
11
2 83 145 76
12
2 83 1 64
75
13
2 83 164 75
14
83 214 76 5
启发式搜索(好)
盲目搜索:是按预定的控制策略进行搜索,在搜索的 过程获得的中间信息不用来改进控制策略,搜索具有 盲目性,效率不高,不便于复杂问题的求解.
启发式搜索:在搜索中加入了与问题有关的启发式信 息,用于指导搜索朝着最有希望的方向前进,加速问 题的求解过程并找到最优解.
2状态空间表示法
状态空间表示法是由”状态”和”算符”来表示问题的 一种方法.”状态”用以描述问题求解过程中不同时刻 的状态;”算符”表示对状态的操作,算符的每一次使用 就使问题由一种状态变换为另一种状态.
GO LOOP
一个简单二叉树的宽度优先搜索过程
A
A
A
BC
BC
BC
D E F GD E F G D E F G
A BC D EF G
在每一个阶段，下一个要扩展的节点由箭头指示 出来。
12
6/29/2020
283
1
4
765
123
8
4
765
算符有空格左移、上移、右移、下移
2 8 31
14 76 5
2 8 32ຫໍສະໝຸດ 修改指针方向重排OPEN表
失败 成功
若对OPEN表中节点的排序不使用关于问题的探 索性信息，则必须任意规定一种排序方式，所得到
的搜索过程叫作无信息搜索，也叫盲目搜索。
一般有两种无信息的图搜索过程：深度优先搜 索与宽度优先搜索．
在人工智能中，一般说来人们对无信息的过程 不感兴趣．
（1）基本思想：从S0开始，逐层地对节点进行扩展，考察它
EXPAND(n)→M(mi),G:=ADD(mi,G) ⑥ 针对M中子节点的不同情况,分别进行如下处理
➢ 对于那些未曾在G中出现过的M成员设置一个指 向父节点(n)的指针,并把它放入OPEN表
➢ 对于那些先前已在G中出现过的M成员,确定是否 要修改指向父节点的指针
➢ 对于那些先前已在G中出现,并且已经扩展了的M 成员,确定是否需要修改其后继节点指向父节点的指 针
➢ (1)状态表示:描述问题求解过程中任一时刻状况的 数据结构,一般用一组变量的有序组合表示: SK=(SK0,SK1…) 当每一个分量确定时,就得到一个具体的状态
➢ (2)算符:引起状态中某些分量发生变化,从而使问题 由一个状态变为另一个状态的操作称为算符.
➢ (3)状态空间:由问题的全部状态及一切可用算符所 构成的集合称为问题的状态空间,一般用一个三元组 表示(S.F.G)
初始状态集合 算符集合 目标状态集合
➢ (4)状态空间的图示形式称为状态空间图,节点表示 状态,有向边(弧)表示算符
3状态空间的一般搜索过程 (1)基本思想
①初始状态作为当前状态
②选择适用的算符对其进行操作,生成一组子状态 ③检查目标状态是否在其中出现,若出现,搜索成功, 找到问题的解,若不出现,按某种搜索策略从已生成 的状态中再选一个状态作为当前状态
④重复② ～ ③,直到目标状态出现,或无可用的算 符为止.
(2)搜索过程 OPEN表:用于存放刚生成的节点 CLOSED表:用于存放将要扩展或已扩展的节点 G：搜索图，动态变化
①把初始节点S0放入OPEN表,并建立只含S0的图,记为G OPEN:=S0, G:=G0(G0=S0)
②检查OPEN表是否为空,若为空则问题无解,退出 LOOP: IF(OPEN)=( ) THEN EXIT(FALL)
③把OPEN表的第一个节点取出放入CLOSED表,记该节点 为节点n n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSED)
④观察节点n是否为目标节点,若是,则求得问题的解,退出 IF GOAL(n) THEN EXIT(SUCCESS)
⑤扩展节点n,生成一组子节点.把其中不是节点n先辈 的那些子节点记作集合M,并把这些节点作为节点n 的子节点加入G中.
1什么是搜索
(1)搜索的引起:人工智能要解决的问题大部分是结构 不良或非结构化的问题,而对这样的问题一般不存在 成熟的求解算法,只能用已有的知识一步步地摸索着 前进
(2)搜索:根据问题的实际情况不断寻找可利用的知识, 从而构成一条代价较少的推理路线,使问题得到圆满 解决的过程.
(3)搜索分为 盲目搜索