企业官网建设流程全解析

简介：这份文档系统整理人工智能搜索技术的主要分支，从搜索概述、状态空间表示，到盲目搜索、启发式搜索，再到A算法与A算法，同时补充博弈搜索与α-β剪枝法，适合初学AI算法或需要系统回顾搜索原理的学习者使用。内容以清晰的知识递进展开：先说明问题求解如何转化为状态图中的搜索，并借助农夫过河、八数码等经典案例演示状态建模与操作定义；再分析宽度优先、深度优先等盲目搜索的优缺点；随后重点讲解启发式估价函数的设计思路，推导A与A算法的搜索流程与最优性条件；最后介绍博弈场景下的极小极大决策与α-β剪枝的剪枝规则，帮助读者理解如何减少无效搜索。资源包含一个PDF文件，总大小6.54MB，便于离线阅读与重点标记。目前已有498人学习下载，可用于课程复习、面试准备或算法选型参考，扎实掌握从基础搜索到高级剪枝的完整知识脉络。

1. 搜索技术：AI 问题求解的核心，从八数码说到迷宫

人工智能搜索技术是 AI 各方向都绕不开的地基。八数码、迷宫寻路、魔方复原、博弈对弈，表面上是不同问题，本质上都是同一件事：在一个状态空间中，从一个初始状态出发，沿着合法操作一步步走到目标状态。问题求解过程就是搜索答案的过程，因此搜索技术也叫问题求解技术。它适用于三类场景：不良结构和非结构化问题、难以获取全部信息的问题、没有现成算法可用的难题。这篇笔记按“状态空间 → 盲目搜索 → 启发式搜索 → 博弈搜索”的顺序，把这套知识拆成能直接复现的代码和参数说明，适合正在学 AI 算法、准备面试或在做路径规划/博弈应用的工程师对照着用。

2. 状态空间建模：把农夫过河写成四元组状态图

2.1 状态用什么数据结构表示

讲搜索之前，第一步永远是建模。状态是问题求解过程中每一步问题状况的数据结构，形式化地写就是 Sk = {Sk0, Sk1, …}，每一个分量给一个确定的值，就得到一个具体状态。以讲义里的农夫过河问题为例，最直观的做法是用四元组（人，狼，羊，菜）表示状态，每个维度取 0 或 1：0 表示在当前左岸（出发点），1 表示在右岸。初始状态是（0，0，0，0），目标状态是（1，1，1，1）。

这个选择的理由很实际：向量化的状态方便程序里直接做索引和比较，也方便后面接 BFS、A* 这类通用搜索框架。你不需要给每个状态起名字，只需要一个 tuple 或者字符串编码。真正要花心思的是状态合法性判断，因为不是所有 16 种组合都能出现在搜索过程中。

非法中间状态必须提前列清楚。农夫不在场时，狼和羊不能单独待在同一岸，羊和白菜也不能单独待在同一岸。讲义里给的非法状态包括（0，0，1，1）、（0，1，1，0）、（0，1，1，1）、（1，1，0，0）等，这些组合的共同特征是：人不在某一岸，而那一岸恰好有捕食关系的一对。常见的错误是只检查单个岸，忽略了“人是否在场”这个前提，导致搜索过程走进非法状态还浑然不觉。

2.2 操作与状态转移函数

操作也叫算符，是把问题从一种状态变换为另一种状态的手段。农夫过河问题中，操作可以理解为一个机械步骤：农夫划船过河，每次可以带一样东西，也可以空手过河。操作是状态集合上的函数，它描述的是状态之间的关系——给定一个当前状态和一个操作，就能唯一确定下一个状态。

用代码实现转移函数时，我一般会写一个 neighbors 函数，它接收当前状态，枚举所有可能的操作，返回所有合法后继状态。这里的参数含义要固定好：p 代表人，w 代表狼，g 代表羊，c 代表白菜，值 0 是左岸，值 1 是右岸。每次过河，人的位置必然翻转（1 - p），至于带的货物，只有选择了它，它的位置才会跟着翻转，否则原地不动。

def is_safe(state): p, w, g, c = state # 人不在场时，不能出现狼和羊同岸、羊和白菜同岸 if p != w and w == g: return False if p != g and g == c: return False return True def neighbors(state): p, w, g, c = state result = [] # None 表示农夫空手过河，其余分别表示带狼、带羊、带菜 for cargo in (None, 'w', 'g', 'c'): np = 1 - p nw = 1 - w if cargo == 'w' else w ng = 1 - g if cargo == 'g' else g nc = 1 - c if cargo == 'c' else c nxt = (np, nw, ng, nc) if nxt != state and is_safe(nxt): result.append(nxt) return result

这段代码的逻辑分两层：is_safe 负责过滤非法状态，核心判断是“人不在场时捕食关系是否存在”；neighbors 负责枚举操作，cargo 决定哪个分量翻转。注意我加了 nxt != state 的判断，因为当 cargo 选择的东西和人不在同一岸时，翻转后状态可能没变化，这种无效操作直接丢弃，避免搜索图里出现自环。运行后能得到一条从（0,0,0,0）到（1,1,1,1）的路径，最短路长度是 7 步。

2.3 从状态图到搜索问题的转化

状态图一旦建好，问题就变成了标准的图搜索：节点是合法状态，边是合法操作，任务是找从初始节点到目标节点的路径。八数码问题同理，用 3×3 矩阵的字符串编码，空格 0 代表移动的位置，相邻交换产生新状态。路径规划、定理证明、机器人行动规划都能归约成这个框架。

建图阶段最容易踩的坑是把所有 16 个状态都当成合法状态去建图。正确做法是先枚举全部状态，用 is_safe 筛掉非法组合，再对合法状态调用 neighbors 生成边。这一步直接决定后续搜索算法的输入质量，后面所有章节的代码都建立在“状态表示 + 转移函数”这两个函数之上，值得在动手前花十分钟把状态表和转移逻辑写清楚。

3. 盲目搜索：BFS 与 DFS 在状态图上的实现代价

3.1 为什么叫“盲目”——不用中间信息改进策略

盲目搜索也叫无信息搜索，它只按预定的控制策略进行搜索，搜索过程中获得的中间信息不拿来改进控制策略。BFS 和 DFS 是最典型的两个：BFS 用队列，先进先出，逐层扩展；DFS 用栈，后进先出，一头扎进深处。它们都不知道目标在哪，只是机械地按顺序把状态空间犁一遍。

这个特性决定了它们的适用边界。BFS 是完备的，只要解存在，一定能找到，而且第一次到达目标时的路径就是最短路径；代价是空间占用大，因为要保存一整层的信息，八数码状态空间约 18 万，BFS 可能把几十万节点都存在内存里。DFS 空间省很多，只保存一条路径上的节点，但可能一头扎进死胡同，在无限状态空间里甚至找不到解。工程上我一般把 DFS 用在深度可控的场景，把 BFS 用在需要保证最短路径的场景。

3.2 八数码上的迭代实现：队列换栈就是 DFS

用代码实现八数码盲目搜索时，状态用字符串表示，0 代表空格，比如“28316745”表示初始局面从左到右从上到下排列。搜索的核心是状态生成：找到 0 的位置，计算它在 3×3 棋盘上的行列，然后尝试与上下左右四个方向的数字交换位置。

from collections import deque def bfs_eight_puzzle(start, goal): q = deque() q.append((start, [])) visited = set([start]) # 移动方向编号：0上 1下 2左 3右 while q: state, path = q.popleft() if state == goal: return path, len(visited) z = state.index('0') r, c = divmod(z, 3) for idx, (dr, dc) in enumerate(((-1, 0), (1, 0), (0, -1), (0, 1))): nr, nc = r + dr, c + dc if 0 <= nr < 3 and 0 <= nc < 3: nz = nr * 3 + nc lst = list(state) lst[z], lst[nz] = lst[nz], lst[z] nxt = ''.join(lst) if nxt not in visited: visited.add(nxt) q.append((nxt, path + [str(idx)])) return None, len(visited)

这里的参数和结构值得说明：q 里存的是（状态，路径），popleft 保证按层扩展；visited 集合记录已访问状态，这是防止死循环的关键，没有它 BFS 会反复进入同一个状态直到内存耗尽；divmod 把一维下标拆成行列坐标，nz = nr * 3 + nc 再把坐标拼回一维下标。改成 DFS 只需要把 q.popleft() 换成 q.pop()，也就是把队列当栈用，其余逻辑完全不变，这就是盲目搜索“只换策略不换模型”的典型体现。

3.3 组合爆炸：盲目搜索为什么撑不过深度 20

讲义里列了一串搜索的挑战：魔方、博弈、皇后、行商、排课、背包。这些问题的共同点是组合爆炸。以八数码为例，状态总数是 9!/2 = 181440，看起来不大，但盲目搜索的节点扩展量受分支因子和深度影响，平均分支因子约 2.7，最坏情况深度能到 30 以上，搜索树规模是分支因子的深度次方量级。魔方的状态空间是 4.3×10^19，18 步最优解硬搜根本不可能。

盲目搜索的问题不在于“能不能找到解”，而在于“找到解之前要浪费多少计算”。BFS 在八数码这种规模尚可的问题里还能接受，到了 15 数码（16!/2 种状态）就明显吃力，再往上的组合问题基本不可行。这也是启发式搜索存在的理由：把“经验”和“已知信息”塞进搜索策略，让搜索朝着最有希望的方向走，而不是把所有方向都试一遍。盲目搜索可以作为正确性基准，用来验证启发式搜索的结果是否最优，这个用法在后面的避坑章节还会提到。

4. 启发式搜索：从 A 算法到 A* 算法的估价函数设计

4.1 估价函数 f(n) = g(n) + h(n) 怎么理解

启发式搜索在搜索中加入了与问题有关的启发性信息，用来指导搜索方向。A 算法的核心是估价函数：f(n) = g(n) + h(n)，g(n) 是从初始状态到当前节点 n 已经付出的实际代价，h(n) 是从 n 到目标节点预估还要付出的代价。A* 是 A 算法的一个特例：当 h(n) 满足可采纳条件，也就是 h(n) 永远不大于实际代价 h*(n) 时，算法保证能找到最优解。

这个区别在工程上非常关键，很多人把 A 算法和 A* 混着叫，实际行为完全不同。A 算法只要给一个 h 就算得动，但不保证最优；A* 要求 h 是实际代价的下界。设计 h 的经验是：宁可低估，不要高估。低估只会让算法多扩展一些节点，高估会直接破坏最优性，让你以为找到了最优解，实际是次优的。八数码里我用曼哈顿距离做 h，它计算每个数字当前位置到目标位置的横向纵向距离之和，由于数字只能相邻移动，这个值永远不会超过真实步数，满足可采纳条件。

4.2 曼哈顿距离与启发函数的实现

曼哈顿距离的实现很简单，但有几个细节容易错：空格 0 不参与计算，因为空格是移动工具不是目标数字；坐标要先转成行列再算差值。下面这段函数把字符串状态的每个字符除以 3 取行、模 3 取列：

def manhattan(state, goal): dist = 0 for i, ch in enumerate(state): if ch == '0': continue gi = goal.index(ch) dist += abs(i // 3 - gi // 3) + abs(i % 3 - gi % 3) return dist

这里用 goal.index(ch) 查找目标位置，每次调用是 O(n) 的线性查找，对八数码这种小规模状态无感；如果换到 15 数码或者更大规模，建议提前把每个数字的目标坐标存成字典，把查找压成 O(1)。另一个细节是 i // 3 和 i % 3 的配合，前者取行，后者取列，顺序不能颠倒，否则曼哈顿距离算出来是错的，后面搜索结果自然不对。

4.3 A* 完整实现与调参要点

有了估价函数，A* 的框架就清晰了：用优先队列按 f 值从小到大取节点扩展，用 g_score 字典记录每个状态的历史最优路径代价，发现更优路径时更新并重新入队。

import heapq def astar_eight_puzzle(start, goal): heap = [] g_score = {start: 0} # 堆元素：f值，g值，状态，路径 heapq.heappush(heap, (manhattan(start, goal), 0, start, [])) expanded = 0 while heap: f, g, state, path = heapq.heappop(heap) expanded += 1 if state == goal: return path, g, expanded z = state.index('0') r, c = divmod(z, 3) for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc = r + dr, c + dc if 0 <= nr < 3 and 0 <= nc < 3: nz = nr * 3 + nc lst = list(state) lst[z], lst[nz] = lst[nz], lst[z] nxt = ''.join(lst) ng = g + 1 if nxt not in g_score or ng < g_score[nxt]: g_score[nxt] = ng heapq.heappush(heap, (ng + manhattan(nxt, goal), ng, nxt, path + [nxt])) return None, -1, expanded

这段代码有三个必须理解的参数：堆元素元组里 f 值放第一位，heapq 按它排序，这是优先队列的优先级来源；g_score 字典的更新条件if nxt not in g_score or ng < g_score[nxt]保证只保留到达该状态的最优代价，这是 A* 最优性的保障；expanded 计数器专门用来统计扩展节点数，后面调试启发函数质量全靠它。

调参方面，最常用的是给 h 加权，把 f 改成 g + w * h，w 大于 1 时搜索更快但不保证最优，w 小于 1 时更保守。我在做路径规划时常用 w = 1 拿最优路径，用 w = 1.5 做快速近似，前者给离线规划，后者给实时决策。另外注意 A* 在八数码上的性能：同一初始状态下，比 BFS 扩展节点数少一个数量级以上，这就是启发信息带了的实际收益。工程上判断 A* 写没写对，先跑一个已知最优解的实例，对比路径长度是否与 BFS 结果一致，一致才说明 h 和 g_score 更新逻辑没毛病。

5. 搜索实现避坑与排查：五个让搜索白跑的问题

5.1 状态编码不一致导致结果全错

现象：搜索跑了半天，BFS 和 A* 返回的路径长度都对不上，甚至 A* 找到的“目标状态”看起来根本不是你要的那个局面。

原因：初始状态字符串的排列顺序和目标状态的排列顺序不一致。八数码里“28316745”必须按从左到右、从上到下的顺序读，如果你初始状态是按行拼接，目标状态却是按列拼接，两者根本不在同一个状态空间里，搜索自然永远到不了真正的目标。

解决：在代码开头写一个断言，强制检查 start 和 goal 的字符集合是否完全一致，并且注释里明确写出“字符串下标 i 对应棋盘第 i//3 行第 i%3 列”。这一步能挡住绝大多数编码错误，我从那以后每次写搜索题第一件事就是先跑这个断言，确认状态编码口径统一再往下走。

5.2 A* 的 g_score 更新条件写错，结果不是最优

现象：A* 能快速找到解，但路径明显比 BFS 找到的最短路径长，而且扩展节点数比预期少很多。

原因：实现时用了一个类似 closed 表的 visited 集合，节点一旦弹出就不再考虑重新入队。A* 的堆弹出顺序虽然按 f 值，但同一个状态可能在找到更优 g 值之前先被弹出过一次，如果直接丢弃，后续更优路径就被错过了。这是把 BFS 的 visited 思路照搬到 A* 上的典型翻车点。

解决：用 g_score 字典代替 visited 集合，只在ng < g_score[nxt]时更新并入队。虽然这会让同一状态多次入队，但堆的规模依然远小于盲目搜索。验证方式是把 A* 的路径长度和 BFS 的对比，若不一致，优先检查 g_score 的更新逻辑，而不是怀疑启发函数。

5.3 启发函数不满足可采纳性，搜索“快”但是错的

现象：A* 在八数码上跑得飞快，但路径比真实最短路径长一截，且把 h 换成 0（退化成 Dijkstra）后路径变正常了。

原因：h 函数高估了实际代价。比如用“不在目标位置的数字个数”做 h，它在某些局面下会超过真实步数，破坏了 A* 的最优性保证。有时候是坐标计算错误，把曼哈顿距离算成了欧氏距离再取整，也会出现高估。

解决：写一个单独的小脚本，随机生成一批状态，对每个状态计算 h 值，再做一次 BFS 求真实代价 h*，检查是否所有状态下 h 都小于等于 h*。这个脚本只跑一次就能定位问题，比在搜索流程里调半天强得多。若只是要快速近似解，可以接受高估，但必须知道这在技术上已经不是 A* 而是 A 算法。

5.4 漏掉 visited 集合，BFS 陷入死循环

现象：BFS 在简单问题上能出结果，在大一点的图上直接内存爆炸，日志里看到状态数量疯狂增长，几万个节点后程序卡死。

原因：图上搜索和树上搜索不同，状态图里存在多条路径可以到达同一状态。没有 visited 集合的情况下，节点会被反复扩展，状态数量指数膨胀，BFS 根本停不下来。

解决：入队时就把状态加入 visited，而不是出队时才加。前者能挡住大部分重复扩展，后者会出现一瞬间的重复入队，在并发或大状态空间下依然危险。DFS 同理，栈里保存路径的同时也要用 visited 记录已完成分支，防止在图中绕圈。

5.5 农夫过河合法性校验只看单岸

现象：农夫过河程序跑出来的路径里出现“人和狼在右岸，羊和白菜在左岸”这类离谱状态，甚至出现狼在左岸羊在左岸而人不在左岸的非法局面。

原因：合法性判断函数据只检查了当前这一岸是否有捕食关系，没有考虑人是否在场。比如状态（0，1，1，0）里，人不在左岸，狼和羊都在左岸，这是非法的，但如果校验函数只检查“狼和羊同岸”就判非法，而没加人不在场的前提，就会把这一状态误判为合法。

解决：合法性判断必须显式写成“农夫不在场时，狼与羊不得同岸、羊与菜不得同岸”两个条件，同时保留人不在场这个前置条件。我在 2.2 节给的 is_safe 函数已经按这个逻辑实现，遇到新问题时要举一反三：任何带“看守者”的状态模型，都要把看守者位置作为合法性判断的必要条件。

6. 博弈搜索与 α-β 剪枝：极小极大法的验证技巧

博弈搜索处理的是双人零和游戏：MAX 方要最大化自己的收益，MIN 方要最小化对方的收益。极小极大法的思路是递归往下推，假设双方都走最优，当前节点取子节点评估值的最大值或最小值，交替进行。α-β 剪枝在此基础上维护两个参数：α 是 MAX 方目前能保证的最大下界，β 是 MIN 方目前能接受的最小上界，当某个节点的评估值使得 β ≤ α 时，剩余分支剪掉不再计算。

def alpha_beta(state, depth, alpha, beta, maximizing): if depth == 0 or is_terminal(state): return evaluate(state) if maximizing: value = float('-inf') for child in get_children(state): value = max(value, alpha_beta(child, depth - 1, alpha, beta, False)) alpha = max(alpha, value) if beta <= alpha: break return value else: value = float('inf') for child in get_children(state): value = min(value, alpha_beta(child, depth - 1, alpha, beta, True)) beta = min(beta, value) if beta <= alpha: break return value

验证这套实现有没有写对，我的习惯是固定同一盘局面，先跑不带剪枝的普通极小极大，再跑带剪枝的版本，对比返回值必须完全一致，同时统计实际评估的节点数，后者一定更少。参数上，α 初始为负无穷，β 初始为正无穷，搜索深度每加一层，剪枝效果越明显，但评估函数的质量决定了剪枝边界。常见误区是忘记在 MAX 层更新 α、在 MIN 层更新 β，或者剪枝条件写反，导致返回值和朴素极小极大不一致。

从那以后我每次写完搜索算法，都强制走一遍三步验证：先跑 BFS 核对路径正确性，再随机生成状态验证 h 的可采纳性，最后用朴素方法与剪枝版本对比博弈结果。这套流程救过我很多次，希望帮到你。

本文还有配套的精品资源，点击获取