盲目搜索启发式搜索(1).ppt

盲目搜索
按预定的控制策略进行搜索，在搜索过程中获得的中间信息不用来改进控制策略。效率低、主要用于简单问题求解。
启发式搜索
在搜索中加入了与问题有关的启发性信息，用以指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。
搜索原理
什么是搜索？
根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程。
1
.
与图有关的术语
状态空间图——由节点(不一定是有限的节点)及连接节点的分枝的集合构成。
有限节点图——节点数目有限的图称为有限节点图。
有向图——一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。
2
.
扩展——求解父节点的所有子节点，叫做扩展。
路径——在一系列节点n1,n2,,nm中，从n1开始，ni总有分枝连接ni+1，称从n1到nm之间的分枝集合是路径。路径中不包含两个及以上相同的分枝，如果n1和nm是同一个节点，则称这种路径为闭路。不构成闭路的称为树。
在用状态空间图来表示问题时，对问题的求解就是求出从初始节点到目标节点的路径。
3
.
图搜索策略
1. 图搜索的定义——一种计算机在状态图中寻找路径的方法。
4
.

编号
节点号
父节点号
CLOSED表
(记录扩展过的节点)
5
.
OPEN表的引入
节点号
父节点号
OPEN表
(记录待扩展的节点)
6
.
举例：八数码魔方例子中
7
.
OPEN表变化过程
节点号
父节点号
S0
空
A
S0
B
S0
C
S0
D
S0
E
A
F
A

8
.
CLOSED表变化过程
编号
节点号
父节点号
0
S0
空
1
A
S0
2
B
S0

9
.
图搜索的一般过程
(1) 建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN表的未扩展节点表中。
(2)建立一个叫做CLOSED的已扩展节点表，其初始为空表。
(3)LOOP：若OPEN表是空表，则失败退出。
(4) 选择OPEN表上的第一个节点，把它从OPEN表移出并放进CLOSED表中。称此节点为节点n。
(5) 若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的(指针将在第7步中设置)。
10
.