20260228 144515 Cpp 入门第十九课

第十九章：搜索算法——在迷宫中寻找出路 ¶

你好！欢迎来到第十九章！在生活中，我们经常需要“搜索”某样东西：在迷宫里找出口、在书架上找一本书、在数字迷宫中找一条路径……在计算机科学中，搜索算法就是系统地探索所有可能的状态，直到找到目标。本章我们将学习两种最基本的搜索策略：深度优先搜索（DFS）和广度优先搜索（BFS），以及它们的优化技巧——剪枝。

19.1 搜索算法概述 ¶

搜索就是从一个初始状态出发，按照一定的规则，不断尝试所有可能的选择，直到找到目标状态。就像你在一个陌生的大楼里找出口，你可以选择一直向右走（深度优先），也可以一层一层地探索（广度优先）。

搜索算法通常用于：
- 求解路径问题（如迷宫）
- 枚举所有可能解（如八皇后）
- 状态空间搜索（如拼图游戏）

两种基本搜索策略 ¶

深度优先搜索（DFS）：从一个分支走到底，再回溯换另一个分支。
广度优先搜索（BFS）：一层一层地探索，先走一步能到的所有点，再走两步能到的点。

19.2 深度优先搜索（DFS）¶

19.2.1 什么是深度优先？¶

想象你在一个迷宫里，你决定“一条路走到黑”：选择一个方向一直走，直到遇到死胡同（无路可走或找到出口），然后回退到上一个岔路口，选择另一个方向继续。这就是深度优先搜索。

DFS可以用递归或栈来实现。递归最直观。

19.2.2 DFS程序范例：全排列 ¶

先看一个简单的DFS例子：生成1~n的所有全排列。这是一个经典的DFS问题，类似于走迷宫：每次选择一个没选过的数字，直到所有数字选完。

#include <iostream>
using namespace std;

const int N = 10;
int n;
int path[N];      // 记录当前排列
bool used[N];     // 标记数字是否用过

void dfs(int u) {
    if (u == n) { // 已经选了n个数，输出一个排列
        for (int i = 0; i < n; i++) cout << path[i] << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            used[i] = true;
            path[u] = i;
            dfs(u + 1);     // 递归下一层
            used[i] = false; // 回溯，恢复现场
        }
    }
}

int main() {
    cout << "请输入n：";
    cin >> n;
    dfs(0);
    return 0;
}

运行示例（n=3）：

这里的关键是回溯：在递归返回后，要把标记还原，这样其他分支才能继续使用这个数字。

19.2.3 DFS走迷宫 ¶

题目：给定一个迷宫，用二维数组表示，0表示空地，1表示障碍。从起点 (sx, sy) 出发，判断能否到达终点 (ex, ey)。输出路径（可选）。

#include <iostream>
using namespace std;

const int N = 10;
int maze[N][N];     // 迷宫地图
int n, m;           // 行数、列数
bool visited[N][N]; // 访问标记
int sx, sy, ex, ey; // 起点、终点
bool found = false;

// 四个方向：上、下、左、右
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

void dfs(int x, int y) {
    if (x == ex && y == ey) {
        found = true;
        return;
    }
    visited[x][y] = true;
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
            maze[nx][ny] == 0 && !visited[nx][ny]) {
            dfs(nx, ny);
            if (found) return;  // 找到目标就提前返回
        }
    }
    // 注意：这里不需要把visited还原，因为不需要找所有路径，只找一条即可
    // 如果要求所有路径，则需要在递归后还原visited
}

int main() {
    cout << "请输入迷宫行数和列数：";
    cin >> n >> m;
    cout << "请输入迷宫（0空地 1障碍）：" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> maze[i][j];
    cout << "请输入起点坐标和终点坐标：";
    cin >> sx >> sy >> ex >> ey;

    dfs(sx, sy);
    if (found)
        cout << "可以到达终点" << endl;
    else
        cout << "无法到达终点" << endl;
    return 0;
}

如果需要输出路径，可以增加一个数组记录前驱节点，或者用栈存储。

19.2.4 DFS与回溯 ¶

回溯是DFS的一种重要技巧，它通过恢复现场来尝试所有可能性。上面的全排列例子中，used[i] = false; 就是回溯。在迷宫问题中，如果我们要找所有路径，也需要在递归返回后把 visited 还原。

19.3 广度优先搜索（BFS）¶

19.3.1 什么是广度优先？¶

想象你在一片水域里丢下一颗石子，波纹会一圈一圈向外扩散。BFS就是这样：从起点出发，先探索所有一步能到的点，再探索两步能到的点，以此类推。BFS天然适合求最短路径（因为第一次到达目标时就是最短步数）。

BFS用队列实现。

19.3.2 BFS程序范例：迷宫最短路径 ¶

用BFS求从起点到终点的最短路径长度（每步移动一格，不能穿越障碍）。

#include <iostream>
#include <queue>
using namespace std;

const int N = 10;
int maze[N][N];
int n, m;
int sx, sy, ex, ey;
int dist[N][N];   // 记录到起点的距离，-1表示未访问

int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};

struct Point {
    int x, y;
};

int bfs() {
    queue<Point> q;
    q.push({sx, sy});
    dist[sx][sy] = 0;

    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        int x = cur.x, y = cur.y;

        if (x == ex && y == ey) {
            return dist[x][y];
        }

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            if (nx >= 0 && nx < n && ny >= 0 && ny < m && 
                maze[nx][ny] == 0 && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
    return -1;  // 不可达
}

int main() {
    cout << "请输入迷宫行数和列数：";
    cin >> n >> m;
    cout << "请输入迷宫（0空地 1障碍）：" << endl;
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            cin >> maze[i][j];
    cout << "请输入起点坐标和终点坐标：";
    cin >> sx >> sy >> ex >> ey;

    // 初始化dist为-1
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            dist[i][j] = -1;

    int steps = bfs();
    if (steps != -1)
        cout << "最短路径长度：" << steps << endl;
    else
        cout << "无法到达终点" << endl;
    return 0;
}

19.3.3 BFS与队列 ¶

BFS的核心是队列：每次将当前点的邻居加入队尾，保证先入队的点先被处理，从而实现“逐层”探索。

19.4 DFS与BFS的比较 ¶

特性	DFS	BFS
数据结构	栈（递归自动使用系统栈）	队列
空间复杂度	O(深度)	O(宽度)（可能很大）
是否保证最短路径	不保证（除非遍历所有）	保证（无权图）
适用场景	枚举所有可能、连通性、回溯	最短路径、分层遍历

19.5 剪枝优化 ¶

搜索算法常常会面临“状态爆炸”的问题，比如八皇后有92种解，但搜索空间巨大。剪枝就是在搜索过程中，提前判断某些分支不可能得到解，从而剪掉它们，减少搜索量。

常见的剪枝：
- 可行性剪枝：当前状态已经不可能达到目标，直接返回。
- 最优性剪枝：当前路径长度已经超过已知最优解，直接返回。
- 重复状态剪枝：用记忆化避免重复搜索。

实例：N皇后问题（经典DFS+剪枝）¶

在 N×N 的棋盘上放置 N 个皇后，使它们互不攻击（不同行、不同列、不同对角线）。输出所有解。

#include <iostream>
using namespace std;

const int N = 20;
int n;
int col[N], dg[2*N], udg[2*N]; // 列、主对角线、副对角线的标记
int path[N];                    // path[i] 表示第i行皇后所在的列

void dfs(int row) {
    if (row == n) {  // 找到一个解
        for (int i = 0; i < n; i++) cout << path[i] + 1 << " "; // 输出列号（从1开始）
        cout << endl;
        return;
    }

    for (int c = 0; c < n; c++) {
        if (!col[c] && !dg[row + c] && !udg[row - c + n]) {
            col[c] = dg[row + c] = udg[row - c + n] = 1;
            path[row] = c;
            dfs(row + 1);
            col[c] = dg[row + c] = udg[row - c + n] = 0; // 回溯
        }
    }
}

int main() {
    cout << "请输入N：";
    cin >> n;
    dfs(0);
    return 0;
}

这里的对角线判断就是剪枝：利用数组快速检查是否有冲突，避免无效的递归。

19.6 编程实例讲解 ¶

实例1：八数码问题（BFS）¶

有一个 3×3 的棋盘，有 1~8 的数字和一个空格（用0表示）。每次可以将空格与上下左右相邻的数字交换。给定初始状态，问最少需要多少步能到达目标状态（例如 1 2 3 4 5 6 7 8 0）。

这题用BFS，状态用字符串或二维数组表示，需要判重。

#include <iostream>
#include <queue>
#include <unordered_map>
#include <string>
using namespace std;

int bfs(string start) {
    string target = "123456780";
    queue<string> q;
    unordered_map<string, int> dist;
    q.push(start);
    dist[start] = 0;

    int dx[4] = {-1, 1, 0, 0};
    int dy[4] = {0, 0, -1, 1};

    while (!q.empty()) {
        string cur = q.front();
        q.pop();
        int d = dist[cur];
        if (cur == target) return d;

        int pos = cur.find('0');   // 空格位置
        int x = pos / 3, y = pos % 3;
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i], ny = y + dy[i];
            if (nx >= 0 && nx < 3 && ny >= 0 && ny < 3) {
                int newPos = nx * 3 + ny;
                string next = cur;
                swap(next[pos], next[newPos]);
                if (!dist.count(next)) {
                    dist[next] = d + 1;
                    q.push(next);
                }
            }
        }
    }
    return -1;
}

int main() {
    string start;
    cout << "请输入初始状态（9个数字，0代表空格）：";
    for (int i = 0; i < 9; i++) {
        char ch;
        cin >> ch;
        start += ch;
    }
    int steps = bfs(start);
    if (steps != -1)
        cout << "最少需要" << steps << "步" << endl;
    else
        cout << "无解" << endl;
    return 0;
}

实例2：素数环（DFS）¶

将从1到n的n个数排成一个环，使得相邻两个数之和都是素数。输出所有可能。

#include <iostream>
#include <cmath>
using namespace std;

const int N = 20;
int n;
int ring[N];
bool used[N];

bool isPrime(int x) {
    if (x < 2) return false;
    for (int i = 2; i <= sqrt(x); i++)
        if (x % i == 0) return false;
    return true;
}

void dfs(int pos) {
    if (pos == n) {
        if (isPrime(ring[0] + ring[n - 1])) {
            for (int i = 0; i < n; i++) cout << ring[i] << " ";
            cout << endl;
        }
        return;
    }
    for (int i = 1; i <= n; i++) {
        if (!used[i] && isPrime(i + ring[pos - 1])) {
            used[i] = true;
            ring[pos] = i;
            dfs(pos + 1);
            used[i] = false;
        }
    }
}

int main() {
    cout << "请输入n：";
    cin >> n;
    ring[0] = 1;  // 通常固定第一个数为1，减少重复
    used[1] = true;
    dfs(1);
    return 0;
}

19.7 阶段性编程练习 ¶

练习1：用DFS求一个迷宫从起点到终点的任意一条路径（不要求最短），并输出路径坐标。
练习2：用BFS求迷宫的最短路径，并输出路径（可以用前驱数组记录）。
练习3：用DFS生成1~n的所有子集（每个数选或不选）。
练习4：用BFS解决“倒水问题”：有两个容量分别为 a 和 b 的壶，问能否量出 c 升水。
练习5：用DFS解决“八皇后”问题，并输出所有解（92种）。