13.4 深度有限搜索
使用深度优先搜索的一个危险在于，如果所期待的解处在一个有限的深度上，而树的某个子树深度却无穷大，那么使用它深度优先搜索就很有可能陷入无限的搜索当中，而不能找到这个本来应该可以找到的解。而这种情况又是很可能发生的。
故此深度有限搜索（Depth-Limited），就引入对搜索深度的限制，将所有深度达到某限度的结点都看做是没有子结点，即可避免陷入无限的搜索当中。
13.5 迭代加深的深度优先搜索
《人工智能，一种现代方法》和《人工智能，复杂问题求解的结构和策略》介绍了迭代加深（Iterative Deepening）的深度优先搜索的思想。
迭代加深的深度优先搜索是对于深度优先搜索和广度优先搜索的一个很好的折衷，这种平衡是通过对深度优先搜索使用一个界限。
因为折衷算法一层层地搜索空间，所以它保证所发现的目标路径是最短的。这一点和广度优先搜索是一致。
又因为它实质上是一种深度优先搜索，所以它不需要广度优先搜索指数级别那么大的空间要求，这一点上是和深度优先搜索是类似的。
RichardE. Korf似乎对搜索算法贡献很大。对于迭代加深的深度搜索的效率，他指出：因为树上某一给定层的结点数量随着深度呈指数增长，所以几乎所有的时间都花在最深层上，因为即使以算数递增的速度多次产生较浅层也无所谓。
而实际上，有趣的是：尽管看起来迭代加深的深度优先方法在时间上比深度优先搜索和广度优先搜索效率低，但是实际上它的复杂度与两个方法处于同一个数量级，即O(B^n)。其中B为结点的平均孩子数，n为目标结点所在的层次。
13.5.1 实例
PKU JudgeOnline, 3009, Curling 2.0.
13.5.2 问题描述
如上图，一个游戏是在冰面上滑动石块，有如下规则：
1. 如果石块紧靠着一堵墙，那么石块不能朝该方向滑动。否则石块可以朝着该方向滑动。
2. 如果滑动的过程中，石块遇到一堵墙，石块停在墙的前面，并把墙夷为平地。否则一直向前滑。
3. 如果石块滑出区域，游戏失败。
4. 如果石块到达目的地，游戏成功。
5. 如果十步之内没有到达目的地，游戏失败。
问题是找出从出发点到目的地所需要的步数。
13.5.3 输入
21
32
66
10 0 2 1 0
11 0 0 0 0
00 0 0 0 3
00 0 0 0 0
10 0 0 0 1
01 1 1 1 1
61
11 2 1 1 3
61
10 2 1 1 3
121
20 1 1 1 1 1 1 1 1 1 3
131
20 1 1 1 1 1 1 1 1 1 1 3
0 0
13.5.4 输出
1
4
-1
4
10
-1
13.5.5 分析
最基本的迭代加深的深度优先搜索就可以解决这个题目，而且非常自然。据说DFS配合剪枝也可以解决。
13.5.6 程序
#include
#include
#define maxNum 22
#define VISITED '*'
#define UNVISITED 'W'
#define BOUND '.'
#define UP -1
#define DOWN 1
#define LEFT -1
#define RIGHT 1
#define NOP 0
int move[4][2]={{UP, NOP}, {NOP, RIGHT}, {DOWN, NOP}, {NOP, LEFT}};
int num;
int row;
int column;
int grid[maxNum][maxNum];
int depth;
int maxDepth;
int StartX;
int StartY;
int IDDFS_Visit(int a, int b)
{
int i;
inttempRow;
int tempColumn;
intstoneRow;
intstoneColumn;
char temp;
depth++;
int find;
find = 0;
if(depth> maxDepth){
gotoend;
}
for(i = 0;i <4; i++){
tempRow = a + move[i][0];
tempColumn = b + move[i][1];
if((tempRow<1 || tempColumn <1)
||(tempRow > row || tempColumn >column)
||(grid[tempRow][tempColumn] == 1))
{//紧接着的是边界或者砖头
continue;
}
while((tempRow>= 1 && tempColumn >= 1)
&& (tempRow <= row&& tempColumn <= column)){
temp = grid[tempRow][tempColumn];
if(temp== 3){
find = 1;
gotoend;
}elseif(temp == 1){
break;
}
stOneRow= tempRow;
stOneColumn= tempColumn;
tempRow = tempRow + move[i][0];
tempColumn = tempColumn +move[i][1];
}
if(tempRow<1 || tempColumn <1
|| tempRow > row || tempColumn >column)
{//一直滑出了边界
continue;
}
grid[tempRow][tempColumn] = 0;
find = IDDFS_Visit(stoneRow,stoneColumn);
grid[tempRow][tempColumn] = 1;
if(find== 1)
{
gotoend;
}
}
end:
depth--;
returnfind;
}
int main()
{
int i;
int j;
while(scanf("%d%d", &column, &row))
{
if(row== 0 && column == 0)
{
break;
}
memset(grid, 0, sizeof(grid));
for(i =1; i <= row; i++){
for(j= 1; j <= column; j++){
scanf("%d", &grid[i][j]);
if(grid[i][j]== 2){
StartY = i;
StartX = j;
}
}
}
for(maxDepth= 1; maxDepth <= 10; maxDepth++)
{
depth = 0;
if(IDDFS_Visit(StartY,StartX) == 1)
{
break;
}
}
if(maxDepth> 10){
printf("-1\n");
}else{
printf("%d\n",maxDepth);
}
}
}
13.6 双向搜索
双向搜索（Bidirectional）是同时从源结点和目标结点对状态进行搜索。要使用双向搜索首先要同时知道源结点和目标结点的状态，其次要保证从两个状态开始的两个方向的搜索是可行的。
13.7 总结
《人工智能，一种现代方法》对于几种搜索策略的介绍相当深入、细致。讨论了广度优先搜索、代价一致搜索、深度优先搜索、深度有限（Depth-Limited）搜索、迭代深入深度优先搜索、双向搜索（Bidirectional）等无信息的搜索策略。
对于搜索策略，可以从以下几个标准进行评价：
1. 是否完备？即：当问题有解时，这个算法能够找到一个解。
2. 是否最优？即：这个搜索策略是否找到最优解。
3. 时间复杂度。即：找到一个解需要花费多长时间。
4. 空间复杂度。即：执行搜索过程需要多少内存。
该文还总结了下表：
13.8 实例
13.8.1 广度优先搜索算法实例
PKU JudgeOnline, 3170, Knights of Ni.
PKU JudgeOnline, 3669, Meteor Shower.
PKU JudgeOnline, 3126, Prime Path.
PKU JudgeOnline, 2251, Dungeon Master.
PKU JudgeOnline, 3414, Pots.
13.8.2 代价一致搜索实例
PKU JudgeOnline, 2312, Battle City
13.8.3 深度优先搜索算法实例
PKU JudgeOnline, 1562, Oil Deposits.
PKU JudgeOnline, 2386, Lake Counting.
PKU JudgeOnline, 1111, Image Perimeters.
PKU JudgeOnline, 3620, Avoid The Lakes.
13.8.4 迭代加深的深度优先搜索实例
PKU JudgeOnline, 3009, Curling 2.0.
本文章欢迎转载，请保留原始博客链接http://blog.csdn.net/fsdev/article
京公网安备 11010802041100号