第4章 · AI的思维模式——搜索

来源、目录与技术核对边界

“第4章 · AI的思维模式——搜索”以天瓏书店详细书目与目录核对段忠杰、顾业鸣著、中国水利水电出版社、ISBN 9787522615059、245 页以及全书 6 章；该页标出版日期 2023 年 6 月 1 日。河南省政府采购书目记录同一 ISBN、题名、作者和出版社，但出版时间写作 2023 年 5 月。日期口径相差一个月，本课程保留差异，不自行断言哪一天是正式首发日。

对“第4章 · AI的思维模式——搜索”而言，公开来源只提供书目和详细目录，不含可授权改写的完整正文；本站的解释、推导、代码、交互、练习和答案均为独立教学重写。目录页第 4 章和第 6 章标题存在明显 OCR 或排版异常，站内按上下文规范化标题，但在清单中披露校正。

“第4章 · AI的思维模式——搜索”的技术事实另以Tarjan 深度优先搜索原始论文复核：技术来源 1。来源用于检查概念、语言语义或历史算法边界，不把现代竞赛规则静默投射成 2023 年原书的逐字内容。

围绕“怎样从状态、动作、终止条件和剪枝安全性证明搜索既完整又可控？”，先预测正确轨迹，再只注入“把 visited 设得过粗，合并了未来选择不同的状态并错误剪掉答案”。若不能用最小反例定位第一处错误决策，就拒绝当前算法解释。

从“AI是不是在凭直觉下棋”开始

先预测：井字棋程序若没有任何训练数据，能不能做到永不输？可以。只要把棋盘编码为状态，列出合法落子，递归评估对手的最佳回应，就能从有限博弈树中算出安全策略。第4章所谓AI的思维模式，首先是把问题看成状态空间中的搜索。

搜索需要四个合同：

• State：到达未来所需的全部信息；
• Action：从当前状态生成哪些合法后继；
• Goal / value：怎样判断成功、失败或优劣；
• Resource policy：怎样控制重复状态、深度、时间与内存。

4.1 深度优先搜索

可以由递归调用栈实现，也可显式维护stack。图上还必须记录visited，否则环会让递归永不结束。

void dfs(int u, const Graph& graph, std::vector<bool>& visited) {
    visited[u] = true;
    for (int v : graph[u]) {
        if (!visited[v]) dfs(v, graph, visited);
    }
}

若图有$V$个顶点、$E$条边，邻接表DFS时间为$O(V+E)$，额外空间为visited加最深递归栈$O(V)$。在树形决策问题里没有全局visited，因为不同路径可能代表不同资源使用；状态合同决定“相同节点”如何判定。

4.1.1 零钱搭配

零钱搭配可以搜索每种面额使用多少枚。状态可写成(coin_index, remaining)；动作是当前面额取0枚到可取上限；目标是remaining为0，目标值可以是方案数或最少硬币数。

int solve(int index, int remaining) {
    if (remaining == 0) return 0;
    if (index == coin_count || remaining < 0) return INF;
    int best = INF;
    for (int count = 0; count * coin[index] <= remaining; ++count) {
        best = std::min(best, count + solve(index + 1, remaining - count * coin[index]));
    }
    return best;
}

候选顺序只影响何时发现好答案，不影响完整搜索的正确性。先尝试大面额可能更早得到较小上界，从而剪掉“已用硬币数不小于best”的分支；但它不是任意币制上的贪心证明。

4.1.2 “油漆桶”与连通性

图像编辑器的油漆桶与连通性是同一问题：像素是顶点，四邻域或八邻域定义边，起点颜色相同且可达的像素组成一个。

Flood fill从seed出发，只把原颜色相同的邻居压入stack。必须先标记再入栈，若等到弹出才标记，同一像素可能被多个邻居重复加入。大图递归深度可能超过语言栈限制，应改用显式stack或scanline fill。

4.2 记忆化

零钱搜索中，许多不同选择顺序会到达同一(index, remaining)。如果后续答案只由这个状态决定，就可用把递归树合并为有向状态图。

int solve(int index, int remaining) {
    if (remaining == 0) return 0;
    if (index == coin_count || remaining < 0) return INF;
    auto key = std::pair{index, remaining};
    if (auto it = memo.find(key); it != memo.end()) return it->second;
    int skip = solve(index + 1, remaining);
    int take = 1 + solve(index, remaining - coin[index]);
    return memo[key] = std::min(skip, take);
}

若有$m$种面额、目标$A$，状态数至多$O(mA)$。但缓存键必须包含影响未来的全部信息；若遗漏“剩余使用次数”或“上一动作”，两个未来不同的路径会被错误合并。

4.3 在游戏中制胜的AI

在游戏中制胜的AI需要面对对手也会选择最优动作。对零和、完全信息、轮流行动游戏，可用。

若终局从当前玩家视角得分为win=1, draw=0, loss=-1，negamax利用零和对称：

4.3.1 永远的平局——井字棋

永远的平局——井字棋是有限搜索的理想实验。棋盘最多9格，合法状态远少于$3^9$，完整minimax可以证明：双方最优时初始状态价值为0。

int negamax(Board board, Player turn) {
    if (board.is_terminal()) return board.score_for(turn);
    int best = -1;
    for (Move move : board.legal_moves()) {
        best = std::max(best, -negamax(board.play(move, turn), other(turn)));
    }
    return best;
}

利用旋转、镜像对称可把等价棋盘规范化后缓存。Alpha-beta剪枝还可跳过不可能改变祖先选择的分支，但最终值与完整minimax相同。

4.3.2 一起来解谜——数独

一起来解谜——数独不是和对手博弈，而是约束满足。每个空格的domain为1到9，行、列、宫格要求all-different。选择候选最少的空格先分支，是minimum remaining values启发式；它不删合法解，只让矛盾更早出现。

Propagation先反复填入唯一候选；若某格domain为空，立即回退。若需要判断题目是否唯一，找到第一个解不能停止，必须继续搜索直到第二个解或空间耗尽。

4.3.3 速战速决——拼图

速战速决——拼图的状态数量远大于井字棋。滑块拼图动作是空格与相邻方块交换，目标是达到固定排列。只用DFS可能深入很差路径；A*按$f=g+h$选择候选，其中$g$是已走步数，$h$是剩余步数下界。

Manhattan距离把每个方块到目标位置的行列距离相加。每次移动只移动一个方块一步，因此真实剩余步数至少是该和；它是admissible heuristic，A*在正确duplicate handling下仍能找最短解。

4.4 迭代加深

若解很浅但不知道深度，BFS能找最浅解却保存整层节点；DFS省内存却可能先钻入无限深分支。结合二者：limit依次为0、1、2，直到找到解。

Result iddfs(State start) {
    for (int limit = 0; ; ++limit) {
        Result result = depth_limited(start, limit);
        if (result.found) return result;
        if (!result.cutoff) return Result::failure();
    }
}

4.4.1 搜索的深度

搜索的深度既是资源上限，也是问题结构。分支因子$b$、最浅解深度$d$时，最后一层约$b^d$个节点。此前各轮重复的浅层节点相对较少：

Depth-limited search必须区分三种返回：found、cutoff、failure。Cutoff表示可能有更深解，应增大limit；failure表示该分支无解，继续加深也无意义。

4.4.2 加深加深再加深——扫雷

加深加深再加深——扫雷可以把未知格视为Boolean变量，已揭示数字是周围mine数量约束。Constraint propagation能直接推出必雷或必安全格；推不动时，假设一个未知格并向下搜索。

迭代加深可限制“同时做多少个未经证明的假设”，优先寻找短证明。若目标是计算每格为雷概率，则需要枚举所有满足约束的assignment并按剩余全局雷数加权，任意找到一个可行assignment并不等于概率答案。

4.5 那些更复杂的AI——现代人工智能技术选讲

那些更复杂的AI——现代人工智能技术选讲把显式搜索扩展到学习。监督学习从样本学习状态到答案，强化学习学习状态到动作的policy，生成模型学习上下文中的条件分布；它们可以提供启发式、价值函数、候选动作或表示。

现代AI仍逃不开搜索合同：

• 表示是否保留决策需要的信息；
• 动作或输出是否满足硬约束；
• 训练目标是否和真实评价一致；
• 分布外输入怎样失败；
• 结果是否需要确定性验证或人工复核。

AlphaGo类系统把神经网络的policy/value与树搜索结合，就是“学习缩小搜索”和“搜索校验局部选择”的组合，不是二者互相替代。

正式节点与算法证据

• 深度优先搜索 ：第 1 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 零钱搭配 ：第 2 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 油漆桶与连通性 ：第 3 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 记忆化 ：第 4 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 在游戏中制胜的AI ：第 5 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 永远的平局——井字棋 ：第 6 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 一起来解谜——数独 ：第 7 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 速战速决——拼图 ：第 8 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 迭代加深 ：第 9 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 搜索的深度 ：第 10 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 加深加深再加深——扫雷 ：第 11 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。
• 现代人工智能技术选讲 ：第 12 个正式节点要能回到“搜索状态唯一可解释，访问策略不会丢失可行解，深度和资源上限有显式退出。”，并给出成功输入与失败反例。

小结

本章从深度优先搜索进入零钱搭配和油漆桶与连通性，再用记忆化把重复递归树合并为状态图。在游戏中制胜的AI部分，井字棋展示minimax，数独展示constraint propagation，拼图展示启发式最短路。

搜索的深度引出迭代加深，扫雷展示约束与假设的组合。现代人工智能技术可以学习表示、policy与value，但状态、动作、目标、资源和证据仍是共同骨架。

练习与答案

名词解释