迭代加深搜索（Iterative Deepening Search，IDS）
是一种常用的搜索算法，结合了深度优先搜索的空间效率和广度优先搜索的完备性和最优性。其核心思想是重复进行深度优先搜索，但每次都增加搜索的深度限制，直到找到目标。
下面我将用一个简单的例子来演示迭代加深搜索：在一个迷宫中找到从起点到终点的路径。我们将用一个二维数组来表示迷宫，其中0表示可以通行的路，1表示障碍物。起点设为左上角(0,0)，终点设为右下角。
C语言代码实现
首先定义迷宫的大小和迷宫本身，接着实现深度优先搜索函数，然后在主函数中实现迭代加深搜索。
#include <stdio.h>
#include <stdbool.h>
#define MAX 5 // 迷宫大小
int maze[MAX][MAX] = {
{0, 1, 0, 0, 0},
{0, 1, 0, 1, 0},
{0, 0, 0, 1, 0},
{0, 1, 0, 0, 0},
{0, 0, 0, 1, 0}
};
bool visited[MAX][MAX]; // 访问标记数组
// 检查是否可以访问该点
bool isValid(int x, int y) {
return (x >= 0 && x < MAX && y >= 0 && y < MAX && maze[x][y] == 0 && !visited[x][y]);
}
// 深度优先搜索实现
bool DFS(int x, int y, int depth, int maxDepth) {
if (x == MAX - 1 && y == MAX - 1) return true; // 如果到达终点
if (depth > maxDepth) return false; // 超过当前深度限制
// 上下左右移动
int dx[] = {-1, 1, 0, 0};
int dy[] = {0, 0, -1, 1};
for (int i = 0; i < 4; i++) {
int nx = x + dx[i], ny = y + dy[i];
if (isValid(nx, ny)) {
visited[nx][ny] = true; // 标记为已访问
if (DFS(nx, ny, depth + 1, maxDepth)) return true;
visited[nx][ny] = false; // 回溯，撤销访问标记
}
}
return false;
}
// 迭代加深搜索
bool IDDFS() {
for (int maxDepth = 0; maxDepth < MAX * MAX; maxDepth++) {
memset(visited, 0, sizeof(visited)); // 重置访问标记
visited[0][0] = true; // 起点标记为已访问
if (DFS(0, 0, 0, maxDepth)) return true;
}
return false;
}
int main() {
if (IDDFS()) {
printf("找到路径！\n");
} else {
printf("没有可用的路径。\n");
}
return 0;
}
```
上述代码中，迭代加深搜索由函数 `IDDFS()` 实现，该函数通过逐渐增加搜索深度限制来调用深度优先搜索函数 `DFS()`。如果找到路径，则返回真，否则继续增加深度限制。`isValid()` 函数用于检查某个位置是否可以进入。整个迷宫搜索从 (0,0) 开始，目标是到达 (MAX-1, MAX-1)。
这个例子展示了迭代加深搜索在解决限定深度的路径搜索问题中的应用。这种方法特别适合解决路径长度不确定或需要找到最短路径的问题。