文档介绍：第三章一般搜索原理
盲目搜索
启发式搜索
归结原理
2/27/2021
1
人工智能讲义
盲目搜索
图搜索策略
深度优先搜索
宽度优先搜索
等代价搜索
2/27/2021
2
人工智能讲义
一些基本概念
节点深度：
根节点深度=0
其它节点深度=父节点深度+1
0
1
2
3
2/27/2021
3
人工智能讲义
一些基本概念（续1）
路径
设一节点序列为(n0, n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。
路径的耗散值
一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。
2/27/2021
4
人工智能讲义
一些基本概念（续1）
扩展一个节点
生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。
2/27/2021
5
人工智能讲义
一般的图搜索算法（GRAPHSEARCH）
1, G=G0 (G0=s), OPEN=(s);
2, CLOSED=( );
3, LOOP: IF OPEN=( ) EXIT(FAIL);
4, n=FIRST(OPEN), REMOVE(n, OPEN),
ADD(n, CLOSED);
5, IF GOAL(n) EXIT(SUCCESS);
6, EXPAND(n)→{mi}, G=ADD(mi, G);
2/27/2021
6
人工智能讲义
一般的图搜索算法（续）
7, 标记和修改指针：
ADD(mj, OPEN), 并标记mj到n的指针；
计算是否要修改mk、ml到n的指针；
计算是否要修改ml到其后继节点的指针；
8, 对OPEN中的节点按某种原则重新排序；
9, GO LOOP；
2/27/2021
7
人工智能讲义
深度优先搜索
在深度优先搜索中，首先扩展最新产生的(最深的)节点，深度相等的节点可以任意排列。“最晚产生的节点最先扩展”
2/27/2021
8
人工智能讲义
深度优先搜索算法
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, IF DEPTH(n)≥Dm GO LOOP;
7, EXPAND(n) →{mi}, G=ADD(mi, G);
8, IF 目标在{mi}中 THEN EXIT(SUCCESS);
9, ADD(mj, OPEN), 并标记mj到n的指针;
10, GO LOOP;
2/27/2021
9
人工智能讲义
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
2 8 3
6 4
1 7 5
2 8 3
1 6
7 5 4
8 3
2 1 4
7 6 5
2 8 3
7 1 4
6 5
2 8
1 4 3
7 6 5
2 8 3
1 4 5
7 6
1
2
3
4
5
6
7
8
9
a
b
c
d
1 2 3
8 4
7 6 5
目标
2/27/2021
10
人工智能讲义