文档介绍：第三章普通搜索原理
盲目搜索
启发式搜索
归结原理
10/1/
1
人工智能讲义
人工智能一般搜索算法原理
第1页
盲目搜索
图搜索策略
深度优先搜索
宽度优先搜索
等代价搜索
10/1/
2
人工智能讲义
人
1
2
3
4
5
6
7
8
9
a
b
c
d
1 2 3
8 4
7 6 5
目标
10/1/
10
人工智能讲义
人工智能一般搜索算法原理
第10页
深度优先搜索性质
普通不能确保找到最优解
当深度限制不合理时，可能找不到解，能够将算法改为可变深度限制
最坏情况时，搜索空间等同于穷举
与回溯法差异：图搜索
是一个通用与问题无关方法
10/1/
11
人工智能讲义
人工智能一般搜索算法原理
第11页
宽度优先搜索
假如搜索是以靠近起始节点程度依次扩展节点，那么这种搜索就叫做宽度优先搜索。这种搜索使逐层进行，在对下一层任意节点进行搜索之前，必须搜索完本层全部节点。“先产生节点先扩展”
10/1/
12
人工智能讲义
人工智能一般搜索算法原理
第12页
宽度优先搜索算法
1, G=G0(G0=s), OPEN=(s), CLOSED=( );
2, LOOP: IF OPEN=( ) EXIT (FAIL);
3, n=FIRST(OPEN);
4, IF GOAL(n) EXIT (SUCCESS);
5, REMOVE(n, OPEN), ADD(n, CLOSED);
6, EXPAND(n) →{mi}, G=ADD(mi, G);
7, IF 目标在{mi}中 THEN EXIT(SUCCESS);
8, ADD(OPEN, mj), 并标识mj到n指针;
9, GO LOOP;
10/1/
13
人工智能讲义
人工智能一般搜索算法原理
第13页
2 3
1 8 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 3
1 8 4
7 6 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 4
7 6 5
2 8 3
1 6 4
7 5
2 8 3
1 6 4
7 5
2 8 3
7 1 4
6 5
8 3
2 1 4
7 6 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
1 2 3
7 8 4
6 5
1 2 3
8 4
7 6 5
1
2
5
6
7
3
1 2 3
8 4
7 6 5
目标
8
2 3 4
1 8
7 6 5
4
10/1/
14
人工智能讲义
人工智能一般搜索算法原理
第14页
宽度优先搜索性质
当问题有解时，一定能找到解
当问题为单位耗散值，且问题有解时，一定能找到最优解
方法与问题无关，含有通用性
效率较低
属于图搜索方法
10/1/
15
人工智能讲义
人工智能一般搜索算法原理
第15页
等代价搜索
宽度优先搜索可被推广用来处理寻找从起始节点到目标节点含有最小代价路径问题，这种推广了宽度优先搜索算法叫做等代价搜索算法。
10/1/
16
人工智能讲义
人工智能一般搜索算法原理
第16页
等代价搜索算法
算法
1,G=G0(G0=s), OPEN=(s), CLOSED=( ),g(s)=0;
2, LOOP: IF OPEN=( ) EXIT (FAIL);
3, 从OPEN表中选择一个节点i,使其g(i)为最小。假如有几个节点都合格，那么就要选择一个目标节点作为i(要是有目标节点话)；不然，就从中选一个作为节点I; REMOVE(i, OPEN), ADD(i, CLOSED);
4, IF GOAL(i) EXIT (SUCCESS);
5, EXPAND(i) →{j}, G=ADD(j, G);
6, 对每个后继节点j,计算g(j)=g(i)+c(i,j)且ADD(OPEN, j), 并标识j到i指针;
7, GO LOOP;
10/1/
17
人工智能讲义
人工智能一般搜索算法原理
第17页
启发式图搜索
利