1. 从“走迷宫”到“状态搜索”问题模型的本质在算法竞赛和实际开发中我们常常遇到一类问题给定一个初始状态和一个目标状态以及一系列允许的“操作”或“移动”规则要求找到从初始状态变换到目标状态所需的最少步骤。这听起来很像小时候玩的“华容道”或者“数字推盘”游戏也像在迷宫里找最短路径。没错这类问题统称为搜索问题更具体地说是状态空间搜索。“第二章 搜索”这个标题通常出现在系统性的算法学习材料中它标志着从基础数据结构向更复杂、更“智能”的算法策略迈进。本章的核心就是探讨当问题规模变大简单的暴力搜索如朴素的BFS/DFS力不从心时我们有哪些“武器”来提升搜索效率直达目标。本章提到的最小步数模型、双端队列广搜、双向广搜、A*正是四种应对不同场景、层层递进的优化策略。它们不是孤立的技巧而是一个解决“如何更快找到最优解”这一核心问题的工具箱。理解这些算法的关键在于转变视角不要只把它们看作“找路”的算法而要看作在状态空间中寻找最优转移路径的通用框架。这个“状态”可以是棋盘上的一个局面、一个字符串的排列、一个数字集合甚至是多个物体在空间中的位置组合。一旦你建立了“状态”和“状态转移”的思维模型很多看似不同的问题如八数码、单词接龙、Knight Moves等都可以归约到同一个框架下解决。接下来我们将逐一拆解这四种策略我会结合具体的代码示例和场景分析让你不仅知道它们怎么写更明白在什么情况下该用哪一个以及为什么这么用。这些都是我在刷题和项目实践中反复验证过的经验。2. 最小步数模型BFS的经典战场与陷阱规避当我们提到“最小步数”第一个跃入脑海的算法通常是广度优先搜索BFS。BFS之所以能保证找到最短路径或最少步数是因为它按照距离起点“层层推进”的顺序访问节点。距离起点为1步的所有状态访问完才会去访问距离为2步的状态以此类推。2.1 BFS解决最小步数问题的标准框架我们以经典的“走迷宫”为例一个二维网格S代表起点T代表终点.代表可通行#代表障碍。每次可以向上下左右四个方向移动一格求最短步数。#include iostream #include queue #include cstring using namespace std; typedef pairint, int PII; const int N 110; int n, m; char g[N][N]; // 存储地图 int dist[N][N]; // 存储每个点到起点的最短距离同时兼作visited数组-1表示未访问 int bfs(PII start, PII target) { queuePII q; memset(dist, -1, sizeof dist); // 初始化为-1表示未访问 dist[start.first][start.second] 0; // 起点距离为0 q.push(start); // 方向数组上、右、下、左 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; while (!q.empty()) { auto t q.front(); q.pop(); // 如果到达终点返回距离 if (t target) return dist[t.first][t.second]; // 遍历四个方向 for (int i 0; i 4; i) { int x t.first dx[i], y t.second dy[i]; // 检查边界、障碍物和是否已访问 if (x 0 x n y 0 y m g[x][y] ! # dist[x][y] -1) { dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } return -1; // 如果队列为空仍未找到终点说明不可达 } int main() { // 假设已读入n, m和地图g以及起点start和终点target // int steps bfs(start, target); return 0; }这个框架是解决所有基于网格或图的最小步数问题的基石。dist数组至关重要它记录了最短距离并防止重复访问避免了DFS可能导致的无限递归或非最短路径。2.2 模型扩展与常见“坑点”实际比赛中问题不会总是标准的网格迷宫。状态可能是一个整数、一个字符串、或者一个更复杂的结构。这时BFS的核心思想不变但实现细节需要调整。1. 状态表示与哈希当状态不是一个坐标而是一个字符串如八数码问题”12345678x”或一个整数时我们需要将其唯一映射以便用dist数组或哈希表来记录是否访问过及距离。// 例如八数码状态用字符串表示 unordered_mapstring, int dist; // 记录每个状态对应的步数 queuestring q;这里最大的坑是状态空间的大小。八数码有9! 362880种状态尚可接受。但如果状态表示不当导致空间爆炸BFS会超内存。务必估算状态总数。2. 步长不为1的BFS等权图与不等权图标准BFS适用于每次移动代价步长相同的情况即边权为1。如果移动代价不同比如有些移动花费1步有些花费2步例如骑士走日字朴素的BFS将无法保证最先弹出的目标状态就是最短路径。因为BFS队列只保证“步数层数”单调递增不保证“总代价”单调递增。这时需要用到双端队列广搜0-1 BFS或优先队列广搜Dijkstra算法这是下一节的重点。3. 多起点/多终点问题有时起点或终点不唯一。对于多起点问题一个高效技巧是反向BFS将所有起点同时加入队列初始距离为0或者从终点反向搜索。这避免了为每个起点单独BFS的冗余计算。个人踩坑心得在实现BFS时最容易出错的地方是状态判重。一定要在状态入队时就标记为已访问dist[x][y] newDist而不是在出队时。如果在出队时判重同一个状态可能会被多次加入队列导致时间复杂度和空间复杂度急剧上升甚至内存超限。这个细节决定了BFS的成败。3. 双端队列广搜应对0-1权值图的利器现在我们来解决上面提到的“不等权图”问题。考虑一个经典模型有一个网格有些格子是平地走过去花费1点体力有些格子是沼泽走过去花费2点体力。求从起点到终点的最小体力消耗。如果还用普通队列BFS会出现什么问题假设从起点A到邻居B是平地代价1到邻居C是沼泽代价2。第一轮B和C都被加入队列假设B在前。从B扩展出的节点D代价累加为112会比从C扩展出的节点E代价累加为213更早出队。但如果存在一条路径A-C-F-D总代价是2114虽然D点被以代价2先访问了但这条更优路径下的D代价4却不会被更新因为D点已经被标记访问过了。这就导致了错误。解决方案是双端队列广搜Deque BFS 或称0-1 BFS。它适用于边权只有两种通常是0和1的图。其核心思想是如果通过一条边权为0的边到达新节点相当于“没有增加代价”那么这个新节点应该拥有和当前节点同等的优先级应该被放到队列的前端以便下一轮优先扩展如果边权为1则放到队列的后端。这样队列前端到后端节点的“当前已知代价”是单调不减的类似于优先队列但更高效。3.1 算法框架与实现我们修改上面的迷宫问题假设上下左右移动代价为1但可以使用一个“魔法”瞬间移动到相邻四个方向的两格外代价为0使用次数有限或无限。求最小代价。#include iostream #include deque #include cstring using namespace std; typedef pairint, int PII; const int N 110; int n, m; char g[N][N]; int dist[N][N]; // 最小代价 int bfs_01(PII start, PII target) { memset(dist, 0x3f, sizeof dist); // 初始化为无穷大 dist[start.first][start.second] 0; dequePII dq; dq.push_back(start); // 普通移动方向 int dx1[4] {-1, 0, 1, 0}, dy1[4] {0, 1, 0, -1}; // 魔法移动方向假设移动到两格外 int dx2[4] {-2, 0, 2, 0}, dy2[4] {0, 2, 0, -2}; while (!dq.empty()) { auto t dq.front(); dq.pop_front(); if (t target) return dist[t.first][t.second]; // 首次出队即为最优 // 扩展代价为1的移动普通移动 for (int i 0; i 4; i) { int x t.first dx1[i], y t.second dy1[i]; if (x 0 x n y 0 y m g[x][y] ! #) { int new_dist dist[t.first][t.second] 1; if (new_dist dist[x][y]) { dist[x][y] new_dist; dq.push_back({x, y}); // 代价为1放队尾 } } } // 扩展代价为0的移动魔法移动 for (int i 0; i 4; i) { int x t.first dx2[i], y t.second dy2[i]; if (x 0 x n y 0 y m g[x][y] ! #) { // 注意魔法移动可能穿越障碍吗这里假设不能且中间格子无障碍。实际需判断。 int midX t.first dx1[i], midY t.second dy1[i]; if (g[midX][midY] #) continue; // 中间有障碍魔法失效 if (dist[t.first][t.second] dist[x][y]) { // 新代价为0旧代价 dist[x][y] dist[t.first][t.second]; dq.push_front({x, y}); // 代价为0放队头关键 } } } } return -1; }3.2 为什么双端队列有效与Dijkstra的对比双端队列广搜本质上是Dijkstra算法在边权仅为0或1时的特化和优化。Dijkstra使用优先队列堆来保证每次取出当前距离最小的节点时间复杂度为O(E log V)。而在0-1权值图中由于边权只有两种队列内部的节点距离值只会有两种d和d1。通过将0边到达的节点放队头1边到达的节点放队尾我们手动维护了队列的“有序性”使得每次从队头取出的节点其距离值一定是当前最小的。这样就将logV的复杂度降为了O(1)总时间复杂度优化为O(VE)。核心技巧判断一个题目能否用双端队列BFS就看状态转移的代价是否只有0和1两种。常见的场景包括使用技能不消耗步数、走某些特殊路径不消耗时间、翻转棋子或开关状态等操作有时翻转视为代价1不翻视为代价0。4. 双向广搜从起点和终点“两头堵”当状态空间非常庞大时即使使用BFS搜索树也会呈指数级膨胀。单向BFS从起点一层层扩展直到碰到终点。如果分支因子是b最短路径长度是d那么搜索的节点数量级大约是O(b^d)。这是一个可怕的数字。双向广搜提供了一个聪明的优化思路既然知道起点和终点为什么不从两头同时开始BFS呢从起点和终点分别进行BFS当两个搜索的“前沿”相遇时路径就找到了。这样搜索的深度从d变成了大约d/2搜索的节点数量级从O(b^d)降低到O(b^{d/2} b^{d/2}) O(2 * b^{d/2})这在b和d较大时是数量级的优化。4.1 算法流程与实现细节双向BFS需要维护两个队列、两个距离记录表或一个表但记录来源。我们以字符串变换为例如“AAB” - “BBC”每次变换一个字符且新字符串必须在给定的字典中。#include iostream #include queue #include unordered_map #include string #include unordered_set using namespace std; // 双向BFS框架 int bidirectional_bfs(string start, string target, unordered_setstring dict) { if (start target) return 0; if (dict.find(target) dict.end()) return -1; // 终点不在字典中 queuestring q_start, q_target; unordered_mapstring, int dist_start, dist_target; // 初始化 dist_start[start] 0; dist_target[target] 0; q_start.push(start); q_target.push(target); // 为了均匀扩展可以每次选择节点数少的队列进行扩展 while (!q_start.empty() !q_target.empty()) { int steps -1; // 总是扩展较小的一边平衡搜索 if (q_start.size() q_target.size()) { steps expand(q_start, dist_start, dist_target, dict); } else { steps expand(q_target, dist_target, dist_start, dict); } if (steps ! -1) { return steps; } } return -1; } // 扩展函数从队列q中扩展一层dist_cur是当前方向的距离记录dist_other是另一方向的 int expand(queuestring q, unordered_mapstring, int dist_cur, unordered_mapstring, int dist_other, unordered_setstring dict) { int size q.size(); for (int i 0; i size; i) { string cur q.front(); q.pop(); int cur_dist dist_cur[cur]; // 生成所有可能的下一状态例如变换字符串的一个字符 for (int j 0; j cur.size(); j) { char original cur[j]; for (char c A; c C; c) { // 假设只能变成A,B,C if (c original) continue; string next cur; next[j] c; // 1. 必须在字典中 if (dict.find(next) dict.end()) continue; // 2. 如果这个状态在当前方向已访问过跳过 if (dist_cur.find(next) ! dist_cur.end()) continue; // 3. 如果这个状态在另一个方向已访问过相遇了 if (dist_other.find(next) ! dist_other.end()) { return cur_dist 1 dist_other[next]; } // 4. 否则加入当前方向的队列 dist_cur[next] cur_dist 1; q.push(next); } } } return -1; // 这一层扩展完没有相遇 }4.2 适用场景与注意事项双向BFS非常适用于知道明确起点和终点且状态转移可逆的问题。比如八数码、单词接龙、某些棋盘游戏。几个关键点相遇判断当从一端扩展出的新状态在另一端的距离记录表中已经存在时即表示相遇。总步数为dist_start[cur] 1 dist_target[next]。注意那个1是因为next状态是从cur扩展出来的边权为1。扩展策略通常选择当前节点数少的队列进行扩展这能保证两个搜索前沿大致同步更快相遇是一种有效的优化。状态判重每个方向需要独立的dist记录或者在一个记录里用正负号区分来源。相遇检查是核心。不可逆操作如果某些操作不可逆例如某些棋子移动后不能原路返回双向BFS可能不适用因为从终点反向搜索时可能无法执行“逆操作”。经验之谈不要盲目使用双向BFS。只有当状态空间极大单向BFS明显会超时或超内存时才考虑它。因为双向BFS的代码复杂度高于单向BFS且需要维护两套状态。在状态空间本身不大比如网格图在100x100以内的情况下单向BFS就足够了双向BFS带来的优化可能抵不上代码复杂度的增加。5. A*搜索用“启发”引导搜索方向A搜索是本章的“智慧担当”。如果说BFS是“地毯式搜索”那A就是“有经验的向导”。它通过一个启发式函数Heuristic Function来估算从当前状态到目标状态的预计代价并优先搜索“预计总代价”最小的状态。这里的“预计总代价” “从起点到当前状态的实际代价g(n)” “从当前状态到目标状态的估计代价h(n)”。A*搜索能保证找到最优解的条件是启发函数h(n)必须是可采纳的Admissible即它永远不会高估从当前状态到目标状态的实际代价。常用的启发函数有曼哈顿距离、欧几里得距离、汉明距离等。5.1 A*算法框架与八数码实例我们以八数码问题为例。状态是一个3x3的排列用字符串表示如”12345678x”。每次操作可以将x与上下左右的数字交换。目标是”12345678x”。启发函数h(n)的选择错误位置数Hamming Distance统计不在目标位置的数字个数。可采纳但不够“聪明”。曼哈顿距离Manhattan Distance计算每个数字当前位置到其目标位置的曼哈顿距离行差列差之和。这是最常用的也是可采纳的。#include iostream #include queue #include unordered_map #include string #include algorithm using namespace std; // 状态结构体用于优先队列 struct State { string s; // 状态字符串 int g; // 从起点到当前状态的实际步数 int h; // 启发函数值曼哈顿距离 int f; // f g h // 重载运算符用于优先队列小顶堆 bool operator(const State other) const { // 注意优先队列默认是最大堆所以我们用 实现最小堆 return f other.f; } }; // 计算曼哈顿距离 int manhattan(const string s) { int distance 0; for (int i 0; i 9; i) { if (s[i] x) continue; int num s[i] - 1; // 数字1~8转换为0~7 // 数字num的目标位置是 (num/3, num%3) // 数字num的当前位置是 (i/3, i%3) distance abs(i / 3 - num / 3) abs(i % 3 - num % 3); } return distance; } // A*搜索主函数 int astar(string start) { string target 12345678x; if (start target) return 0; priority_queueState heap; unordered_mapstring, int dist; // 记录到达某个状态的最小实际代价g // 也可以用一个unordered_mapstring, State来记录更多信息 heap.push({start, 0, manhattan(start), 0 manhattan(start)}); dist[start] 0; // 方向数组和对应的移动描述用于输出路径这里略去路径存储 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; char op[4] {u, r, d, l}; // 上右下左 while (!heap.empty()) { auto t heap.top(); heap.pop(); string state t.s; int step t.g; // 如果出队的状态不是最优的由于堆中可能存在同一状态的不同f值跳过 if (dist[state] step) continue; if (state target) { return step; } // 找到x的位置 int k state.find(x); int x k / 3, y k % 3; for (int i 0; i 4; i) { int a x dx[i], b y dy[i]; if (a 0 a 3 b 0 b 3) { string next_state state; swap(next_state[k], next_state[a * 3 b]); // 计算新状态的实际代价和估计代价 int g_next step 1; int h_next manhattan(next_state); // 如果这个状态未被访问过或者找到了更优的路径 if (dist.find(next_state) dist.end() || g_next dist[next_state]) { dist[next_state] g_next; heap.push({next_state, g_next, h_next, g_next h_next}); } } } } return -1; }5.2 A*算法的核心启发函数与效率权衡A*的效率极度依赖于启发函数h(n)的质量。h(n) ≡ 0A*退化为Dijkstra算法或等权图的BFS只按实际代价g(n)搜索效率最低但保证最优。h(n) ≤ 实际代价可采纳保证找到最优解。h(n)越接近实际代价A*需要扩展的节点就越少效率越高。h(n) 实际代价不可采纳可能找不到最优解但可能更快找到一个解不一定最优。一致性Consistency如果对于任意状态n和其后继状态n’满足h(n) ≤ cost(n, n’) h(n’)则称h(n)是一致的。一致性是可采纳的更强条件能保证A*在扩展一个状态时已经找到了到达该状态的最优路径因此每个状态只需被扩展一次代码中if (dist[state] step) continue这个判断在一致启发函数下可以省略但保留更安全。在八数码问题中曼哈顿距离是一致的吗是的。移动一个数字与x交换一次最多使其曼哈顿距离减少1如果移向目标也可能增加1如果移开或者不变如果横向移动但未改变行/列差。因此对于任何移动|h(n) - h(n’)| ≤ 1 cost(n, n’)满足一致性条件。避坑指南A*搜索的优先队列中可能会多次加入同一个状态因为可能通过不同路径以不同的f值发现它。这就是为什么我们需要dist数组来记录到达某个状态的最小实际代价g。当从堆中取出一个状态时如果发现记录的g值已经小于当前状态的g值说明这个状态已经被以更优的路径访问过了当前这个出队的节点是一个“过时”的副本直接跳过即可。这个检查至关重要否则算法会做大量无用功。6. 策略选择与综合应用如何为你的问题挑选武器学完了四种策略面对具体问题时该如何选择我总结了一个决策流程你可以把它当作检查清单问题是否在求最小步数/最短路径如果不是可能需要DFS或其他算法。图状态转移图的边权是否全为1是优先考虑标准BFS。代码简单效率高。否但边权只有0和1两种考虑双端队列BFS。它比Dijkstra的优先队列实现更高效。否边权为任意正数需要使用Dijkstra算法优先队列BFS。这超出了本章“双端队列”的范畴但思想一脉相承。状态空间是否巨大且起点终点明确是在尝试了BFS发现超时后考虑双向BFS。它能将指数爆炸的搜索树“腰斩”。是否有良好的启发式函数来估算到目标的距离是且需要最优解A*搜索是你的首选。特别是在路径规划、拼图类问题上A*的表现往往远优于BFS。是但可以接受次优解可以考虑使用权重A*如f g ε*h ε1来加快搜索速度但可能牺牲最优性。是否可以结合使用双向A*结合双向BFS和A的思想从起点和终点同时进行A搜索。实现复杂但在某些问题上效果惊人。IDA*迭代加深的A*适用于内存紧张但时间充裕的场景。它用DFS的框架通过迭代加深的深度限制和启发函数来剪枝。为了更直观这里用一个表格对比这几种算法算法核心思想适用条件优点缺点时间复杂度最坏BFS层层推进先到先得边权为1等权图保证最优实现简单状态空间大时效率低O(VE)双端队列BFS0边队头1边队尾边权仅为0或1比Dijkstra高效保证最优仅适用于0-1权图O(VE)双向BFS起点终点同时搜索状态空间大转移可逆大幅减少搜索节点数代码复杂需维护两套状态O(b^{d/2})A*实际代价估计代价有可采纳的启发函数用启发信息引导效率高启发函数设计是关键内存占用可能大O(b^d)但常数小最后再分享一个综合性的解题思路面对一个新的搜索问题我通常会先尝试用标准BFS写一个暴力版本评估其状态数。如果状态数在10^6量级以内BFS通常能过。如果超时分析原因是边权不为1考虑双端队列或Dijkstra。是状态空间爆炸看看能否设计启发函数用A*或者起点终点明确用双向BFS。很多时候竞赛题目的正解就是这些优化策略的组合。多练习培养出对问题模型的直觉你就能快速选出最合适的那把“手术刀”。 算法竞赛搜索优化：BFS、双端队列、双向与A*实战解析
1. 从“走迷宫”到“状态搜索”问题模型的本质在算法竞赛和实际开发中我们常常遇到一类问题给定一个初始状态和一个目标状态以及一系列允许的“操作”或“移动”规则要求找到从初始状态变换到目标状态所需的最少步骤。这听起来很像小时候玩的“华容道”或者“数字推盘”游戏也像在迷宫里找最短路径。没错这类问题统称为搜索问题更具体地说是状态空间搜索。“第二章 搜索”这个标题通常出现在系统性的算法学习材料中它标志着从基础数据结构向更复杂、更“智能”的算法策略迈进。本章的核心就是探讨当问题规模变大简单的暴力搜索如朴素的BFS/DFS力不从心时我们有哪些“武器”来提升搜索效率直达目标。本章提到的最小步数模型、双端队列广搜、双向广搜、A*正是四种应对不同场景、层层递进的优化策略。它们不是孤立的技巧而是一个解决“如何更快找到最优解”这一核心问题的工具箱。理解这些算法的关键在于转变视角不要只把它们看作“找路”的算法而要看作在状态空间中寻找最优转移路径的通用框架。这个“状态”可以是棋盘上的一个局面、一个字符串的排列、一个数字集合甚至是多个物体在空间中的位置组合。一旦你建立了“状态”和“状态转移”的思维模型很多看似不同的问题如八数码、单词接龙、Knight Moves等都可以归约到同一个框架下解决。接下来我们将逐一拆解这四种策略我会结合具体的代码示例和场景分析让你不仅知道它们怎么写更明白在什么情况下该用哪一个以及为什么这么用。这些都是我在刷题和项目实践中反复验证过的经验。2. 最小步数模型BFS的经典战场与陷阱规避当我们提到“最小步数”第一个跃入脑海的算法通常是广度优先搜索BFS。BFS之所以能保证找到最短路径或最少步数是因为它按照距离起点“层层推进”的顺序访问节点。距离起点为1步的所有状态访问完才会去访问距离为2步的状态以此类推。2.1 BFS解决最小步数问题的标准框架我们以经典的“走迷宫”为例一个二维网格S代表起点T代表终点.代表可通行#代表障碍。每次可以向上下左右四个方向移动一格求最短步数。#include iostream #include queue #include cstring using namespace std; typedef pairint, int PII; const int N 110; int n, m; char g[N][N]; // 存储地图 int dist[N][N]; // 存储每个点到起点的最短距离同时兼作visited数组-1表示未访问 int bfs(PII start, PII target) { queuePII q; memset(dist, -1, sizeof dist); // 初始化为-1表示未访问 dist[start.first][start.second] 0; // 起点距离为0 q.push(start); // 方向数组上、右、下、左 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; while (!q.empty()) { auto t q.front(); q.pop(); // 如果到达终点返回距离 if (t target) return dist[t.first][t.second]; // 遍历四个方向 for (int i 0; i 4; i) { int x t.first dx[i], y t.second dy[i]; // 检查边界、障碍物和是否已访问 if (x 0 x n y 0 y m g[x][y] ! # dist[x][y] -1) { dist[x][y] dist[t.first][t.second] 1; q.push({x, y}); } } } return -1; // 如果队列为空仍未找到终点说明不可达 } int main() { // 假设已读入n, m和地图g以及起点start和终点target // int steps bfs(start, target); return 0; }这个框架是解决所有基于网格或图的最小步数问题的基石。dist数组至关重要它记录了最短距离并防止重复访问避免了DFS可能导致的无限递归或非最短路径。2.2 模型扩展与常见“坑点”实际比赛中问题不会总是标准的网格迷宫。状态可能是一个整数、一个字符串、或者一个更复杂的结构。这时BFS的核心思想不变但实现细节需要调整。1. 状态表示与哈希当状态不是一个坐标而是一个字符串如八数码问题”12345678x”或一个整数时我们需要将其唯一映射以便用dist数组或哈希表来记录是否访问过及距离。// 例如八数码状态用字符串表示 unordered_mapstring, int dist; // 记录每个状态对应的步数 queuestring q;这里最大的坑是状态空间的大小。八数码有9! 362880种状态尚可接受。但如果状态表示不当导致空间爆炸BFS会超内存。务必估算状态总数。2. 步长不为1的BFS等权图与不等权图标准BFS适用于每次移动代价步长相同的情况即边权为1。如果移动代价不同比如有些移动花费1步有些花费2步例如骑士走日字朴素的BFS将无法保证最先弹出的目标状态就是最短路径。因为BFS队列只保证“步数层数”单调递增不保证“总代价”单调递增。这时需要用到双端队列广搜0-1 BFS或优先队列广搜Dijkstra算法这是下一节的重点。3. 多起点/多终点问题有时起点或终点不唯一。对于多起点问题一个高效技巧是反向BFS将所有起点同时加入队列初始距离为0或者从终点反向搜索。这避免了为每个起点单独BFS的冗余计算。个人踩坑心得在实现BFS时最容易出错的地方是状态判重。一定要在状态入队时就标记为已访问dist[x][y] newDist而不是在出队时。如果在出队时判重同一个状态可能会被多次加入队列导致时间复杂度和空间复杂度急剧上升甚至内存超限。这个细节决定了BFS的成败。3. 双端队列广搜应对0-1权值图的利器现在我们来解决上面提到的“不等权图”问题。考虑一个经典模型有一个网格有些格子是平地走过去花费1点体力有些格子是沼泽走过去花费2点体力。求从起点到终点的最小体力消耗。如果还用普通队列BFS会出现什么问题假设从起点A到邻居B是平地代价1到邻居C是沼泽代价2。第一轮B和C都被加入队列假设B在前。从B扩展出的节点D代价累加为112会比从C扩展出的节点E代价累加为213更早出队。但如果存在一条路径A-C-F-D总代价是2114虽然D点被以代价2先访问了但这条更优路径下的D代价4却不会被更新因为D点已经被标记访问过了。这就导致了错误。解决方案是双端队列广搜Deque BFS 或称0-1 BFS。它适用于边权只有两种通常是0和1的图。其核心思想是如果通过一条边权为0的边到达新节点相当于“没有增加代价”那么这个新节点应该拥有和当前节点同等的优先级应该被放到队列的前端以便下一轮优先扩展如果边权为1则放到队列的后端。这样队列前端到后端节点的“当前已知代价”是单调不减的类似于优先队列但更高效。3.1 算法框架与实现我们修改上面的迷宫问题假设上下左右移动代价为1但可以使用一个“魔法”瞬间移动到相邻四个方向的两格外代价为0使用次数有限或无限。求最小代价。#include iostream #include deque #include cstring using namespace std; typedef pairint, int PII; const int N 110; int n, m; char g[N][N]; int dist[N][N]; // 最小代价 int bfs_01(PII start, PII target) { memset(dist, 0x3f, sizeof dist); // 初始化为无穷大 dist[start.first][start.second] 0; dequePII dq; dq.push_back(start); // 普通移动方向 int dx1[4] {-1, 0, 1, 0}, dy1[4] {0, 1, 0, -1}; // 魔法移动方向假设移动到两格外 int dx2[4] {-2, 0, 2, 0}, dy2[4] {0, 2, 0, -2}; while (!dq.empty()) { auto t dq.front(); dq.pop_front(); if (t target) return dist[t.first][t.second]; // 首次出队即为最优 // 扩展代价为1的移动普通移动 for (int i 0; i 4; i) { int x t.first dx1[i], y t.second dy1[i]; if (x 0 x n y 0 y m g[x][y] ! #) { int new_dist dist[t.first][t.second] 1; if (new_dist dist[x][y]) { dist[x][y] new_dist; dq.push_back({x, y}); // 代价为1放队尾 } } } // 扩展代价为0的移动魔法移动 for (int i 0; i 4; i) { int x t.first dx2[i], y t.second dy2[i]; if (x 0 x n y 0 y m g[x][y] ! #) { // 注意魔法移动可能穿越障碍吗这里假设不能且中间格子无障碍。实际需判断。 int midX t.first dx1[i], midY t.second dy1[i]; if (g[midX][midY] #) continue; // 中间有障碍魔法失效 if (dist[t.first][t.second] dist[x][y]) { // 新代价为0旧代价 dist[x][y] dist[t.first][t.second]; dq.push_front({x, y}); // 代价为0放队头关键 } } } } return -1; }3.2 为什么双端队列有效与Dijkstra的对比双端队列广搜本质上是Dijkstra算法在边权仅为0或1时的特化和优化。Dijkstra使用优先队列堆来保证每次取出当前距离最小的节点时间复杂度为O(E log V)。而在0-1权值图中由于边权只有两种队列内部的节点距离值只会有两种d和d1。通过将0边到达的节点放队头1边到达的节点放队尾我们手动维护了队列的“有序性”使得每次从队头取出的节点其距离值一定是当前最小的。这样就将logV的复杂度降为了O(1)总时间复杂度优化为O(VE)。核心技巧判断一个题目能否用双端队列BFS就看状态转移的代价是否只有0和1两种。常见的场景包括使用技能不消耗步数、走某些特殊路径不消耗时间、翻转棋子或开关状态等操作有时翻转视为代价1不翻视为代价0。4. 双向广搜从起点和终点“两头堵”当状态空间非常庞大时即使使用BFS搜索树也会呈指数级膨胀。单向BFS从起点一层层扩展直到碰到终点。如果分支因子是b最短路径长度是d那么搜索的节点数量级大约是O(b^d)。这是一个可怕的数字。双向广搜提供了一个聪明的优化思路既然知道起点和终点为什么不从两头同时开始BFS呢从起点和终点分别进行BFS当两个搜索的“前沿”相遇时路径就找到了。这样搜索的深度从d变成了大约d/2搜索的节点数量级从O(b^d)降低到O(b^{d/2} b^{d/2}) O(2 * b^{d/2})这在b和d较大时是数量级的优化。4.1 算法流程与实现细节双向BFS需要维护两个队列、两个距离记录表或一个表但记录来源。我们以字符串变换为例如“AAB” - “BBC”每次变换一个字符且新字符串必须在给定的字典中。#include iostream #include queue #include unordered_map #include string #include unordered_set using namespace std; // 双向BFS框架 int bidirectional_bfs(string start, string target, unordered_setstring dict) { if (start target) return 0; if (dict.find(target) dict.end()) return -1; // 终点不在字典中 queuestring q_start, q_target; unordered_mapstring, int dist_start, dist_target; // 初始化 dist_start[start] 0; dist_target[target] 0; q_start.push(start); q_target.push(target); // 为了均匀扩展可以每次选择节点数少的队列进行扩展 while (!q_start.empty() !q_target.empty()) { int steps -1; // 总是扩展较小的一边平衡搜索 if (q_start.size() q_target.size()) { steps expand(q_start, dist_start, dist_target, dict); } else { steps expand(q_target, dist_target, dist_start, dict); } if (steps ! -1) { return steps; } } return -1; } // 扩展函数从队列q中扩展一层dist_cur是当前方向的距离记录dist_other是另一方向的 int expand(queuestring q, unordered_mapstring, int dist_cur, unordered_mapstring, int dist_other, unordered_setstring dict) { int size q.size(); for (int i 0; i size; i) { string cur q.front(); q.pop(); int cur_dist dist_cur[cur]; // 生成所有可能的下一状态例如变换字符串的一个字符 for (int j 0; j cur.size(); j) { char original cur[j]; for (char c A; c C; c) { // 假设只能变成A,B,C if (c original) continue; string next cur; next[j] c; // 1. 必须在字典中 if (dict.find(next) dict.end()) continue; // 2. 如果这个状态在当前方向已访问过跳过 if (dist_cur.find(next) ! dist_cur.end()) continue; // 3. 如果这个状态在另一个方向已访问过相遇了 if (dist_other.find(next) ! dist_other.end()) { return cur_dist 1 dist_other[next]; } // 4. 否则加入当前方向的队列 dist_cur[next] cur_dist 1; q.push(next); } } } return -1; // 这一层扩展完没有相遇 }4.2 适用场景与注意事项双向BFS非常适用于知道明确起点和终点且状态转移可逆的问题。比如八数码、单词接龙、某些棋盘游戏。几个关键点相遇判断当从一端扩展出的新状态在另一端的距离记录表中已经存在时即表示相遇。总步数为dist_start[cur] 1 dist_target[next]。注意那个1是因为next状态是从cur扩展出来的边权为1。扩展策略通常选择当前节点数少的队列进行扩展这能保证两个搜索前沿大致同步更快相遇是一种有效的优化。状态判重每个方向需要独立的dist记录或者在一个记录里用正负号区分来源。相遇检查是核心。不可逆操作如果某些操作不可逆例如某些棋子移动后不能原路返回双向BFS可能不适用因为从终点反向搜索时可能无法执行“逆操作”。经验之谈不要盲目使用双向BFS。只有当状态空间极大单向BFS明显会超时或超内存时才考虑它。因为双向BFS的代码复杂度高于单向BFS且需要维护两套状态。在状态空间本身不大比如网格图在100x100以内的情况下单向BFS就足够了双向BFS带来的优化可能抵不上代码复杂度的增加。5. A*搜索用“启发”引导搜索方向A搜索是本章的“智慧担当”。如果说BFS是“地毯式搜索”那A就是“有经验的向导”。它通过一个启发式函数Heuristic Function来估算从当前状态到目标状态的预计代价并优先搜索“预计总代价”最小的状态。这里的“预计总代价” “从起点到当前状态的实际代价g(n)” “从当前状态到目标状态的估计代价h(n)”。A*搜索能保证找到最优解的条件是启发函数h(n)必须是可采纳的Admissible即它永远不会高估从当前状态到目标状态的实际代价。常用的启发函数有曼哈顿距离、欧几里得距离、汉明距离等。5.1 A*算法框架与八数码实例我们以八数码问题为例。状态是一个3x3的排列用字符串表示如”12345678x”。每次操作可以将x与上下左右的数字交换。目标是”12345678x”。启发函数h(n)的选择错误位置数Hamming Distance统计不在目标位置的数字个数。可采纳但不够“聪明”。曼哈顿距离Manhattan Distance计算每个数字当前位置到其目标位置的曼哈顿距离行差列差之和。这是最常用的也是可采纳的。#include iostream #include queue #include unordered_map #include string #include algorithm using namespace std; // 状态结构体用于优先队列 struct State { string s; // 状态字符串 int g; // 从起点到当前状态的实际步数 int h; // 启发函数值曼哈顿距离 int f; // f g h // 重载运算符用于优先队列小顶堆 bool operator(const State other) const { // 注意优先队列默认是最大堆所以我们用 实现最小堆 return f other.f; } }; // 计算曼哈顿距离 int manhattan(const string s) { int distance 0; for (int i 0; i 9; i) { if (s[i] x) continue; int num s[i] - 1; // 数字1~8转换为0~7 // 数字num的目标位置是 (num/3, num%3) // 数字num的当前位置是 (i/3, i%3) distance abs(i / 3 - num / 3) abs(i % 3 - num % 3); } return distance; } // A*搜索主函数 int astar(string start) { string target 12345678x; if (start target) return 0; priority_queueState heap; unordered_mapstring, int dist; // 记录到达某个状态的最小实际代价g // 也可以用一个unordered_mapstring, State来记录更多信息 heap.push({start, 0, manhattan(start), 0 manhattan(start)}); dist[start] 0; // 方向数组和对应的移动描述用于输出路径这里略去路径存储 int dx[4] {-1, 0, 1, 0}, dy[4] {0, 1, 0, -1}; char op[4] {u, r, d, l}; // 上右下左 while (!heap.empty()) { auto t heap.top(); heap.pop(); string state t.s; int step t.g; // 如果出队的状态不是最优的由于堆中可能存在同一状态的不同f值跳过 if (dist[state] step) continue; if (state target) { return step; } // 找到x的位置 int k state.find(x); int x k / 3, y k % 3; for (int i 0; i 4; i) { int a x dx[i], b y dy[i]; if (a 0 a 3 b 0 b 3) { string next_state state; swap(next_state[k], next_state[a * 3 b]); // 计算新状态的实际代价和估计代价 int g_next step 1; int h_next manhattan(next_state); // 如果这个状态未被访问过或者找到了更优的路径 if (dist.find(next_state) dist.end() || g_next dist[next_state]) { dist[next_state] g_next; heap.push({next_state, g_next, h_next, g_next h_next}); } } } } return -1; }5.2 A*算法的核心启发函数与效率权衡A*的效率极度依赖于启发函数h(n)的质量。h(n) ≡ 0A*退化为Dijkstra算法或等权图的BFS只按实际代价g(n)搜索效率最低但保证最优。h(n) ≤ 实际代价可采纳保证找到最优解。h(n)越接近实际代价A*需要扩展的节点就越少效率越高。h(n) 实际代价不可采纳可能找不到最优解但可能更快找到一个解不一定最优。一致性Consistency如果对于任意状态n和其后继状态n’满足h(n) ≤ cost(n, n’) h(n’)则称h(n)是一致的。一致性是可采纳的更强条件能保证A*在扩展一个状态时已经找到了到达该状态的最优路径因此每个状态只需被扩展一次代码中if (dist[state] step) continue这个判断在一致启发函数下可以省略但保留更安全。在八数码问题中曼哈顿距离是一致的吗是的。移动一个数字与x交换一次最多使其曼哈顿距离减少1如果移向目标也可能增加1如果移开或者不变如果横向移动但未改变行/列差。因此对于任何移动|h(n) - h(n’)| ≤ 1 cost(n, n’)满足一致性条件。避坑指南A*搜索的优先队列中可能会多次加入同一个状态因为可能通过不同路径以不同的f值发现它。这就是为什么我们需要dist数组来记录到达某个状态的最小实际代价g。当从堆中取出一个状态时如果发现记录的g值已经小于当前状态的g值说明这个状态已经被以更优的路径访问过了当前这个出队的节点是一个“过时”的副本直接跳过即可。这个检查至关重要否则算法会做大量无用功。6. 策略选择与综合应用如何为你的问题挑选武器学完了四种策略面对具体问题时该如何选择我总结了一个决策流程你可以把它当作检查清单问题是否在求最小步数/最短路径如果不是可能需要DFS或其他算法。图状态转移图的边权是否全为1是优先考虑标准BFS。代码简单效率高。否但边权只有0和1两种考虑双端队列BFS。它比Dijkstra的优先队列实现更高效。否边权为任意正数需要使用Dijkstra算法优先队列BFS。这超出了本章“双端队列”的范畴但思想一脉相承。状态空间是否巨大且起点终点明确是在尝试了BFS发现超时后考虑双向BFS。它能将指数爆炸的搜索树“腰斩”。是否有良好的启发式函数来估算到目标的距离是且需要最优解A*搜索是你的首选。特别是在路径规划、拼图类问题上A*的表现往往远优于BFS。是但可以接受次优解可以考虑使用权重A*如f g ε*h ε1来加快搜索速度但可能牺牲最优性。是否可以结合使用双向A*结合双向BFS和A的思想从起点和终点同时进行A搜索。实现复杂但在某些问题上效果惊人。IDA*迭代加深的A*适用于内存紧张但时间充裕的场景。它用DFS的框架通过迭代加深的深度限制和启发函数来剪枝。为了更直观这里用一个表格对比这几种算法算法核心思想适用条件优点缺点时间复杂度最坏BFS层层推进先到先得边权为1等权图保证最优实现简单状态空间大时效率低O(VE)双端队列BFS0边队头1边队尾边权仅为0或1比Dijkstra高效保证最优仅适用于0-1权图O(VE)双向BFS起点终点同时搜索状态空间大转移可逆大幅减少搜索节点数代码复杂需维护两套状态O(b^{d/2})A*实际代价估计代价有可采纳的启发函数用启发信息引导效率高启发函数设计是关键内存占用可能大O(b^d)但常数小最后再分享一个综合性的解题思路面对一个新的搜索问题我通常会先尝试用标准BFS写一个暴力版本评估其状态数。如果状态数在10^6量级以内BFS通常能过。如果超时分析原因是边权不为1考虑双端队列或Dijkstra。是状态空间爆炸看看能否设计启发函数用A*或者起点终点明确用双向BFS。很多时候竞赛题目的正解就是这些优化策略的组合。多练习培养出对问题模型的直觉你就能快速选出最合适的那把“手术刀”。