搜索算法这块内容，我前前后后给不同背景的人讲过好几轮，也在实际项目里用过不少。说实话，很多人第一次接触搜索算法，脑子里浮现的就是"在数组里找一个数"这种场景，然后觉得这不就是遍历吗，有什么好讲的。但真正做过路径规划、下棋AI、资源调度这类事情的人会知道，搜索算法远不止"找东西"这么简单——它本质上是一套在巨大状态空间里做决策的方法论。你面对的可能是一个棋盘局面、一张地图、一个任务依赖图，甚至是一个组合优化问题，而搜索算法决定了你能不能找到解、找到的解好不好、以及花多长时间找到。
这篇文章我想从实际使用的角度，把搜索算法这条线捋清楚。从最朴素的盲目搜索讲起，到启发式搜索怎么引入领域知识，再到对抗搜索怎么处理有对手的场景，最后聊一聊在实际工程中怎么选、怎么调、怎么避坑。适合有基本数据结构基础、想真正把搜索算法用起来的人。我不会只给你伪代码，而是会解释每一步为什么这么设计，以及我在实操中踩过的那些坑。
1. 搜索算法到底在解决什么问题
1.1 从"找路"说起：状态空间才是核心
很多人理解搜索算法是从"在一个集合里找目标元素"开始的，这其实是最简单的一类搜索——线性搜索或者二分搜索。但人工智能领域说的搜索算法，绝大多数情况下指的是在状态空间中寻找从初始状态到目标状态的路径。
什么叫状态空间？你可以把它想象成一张巨大的图。每个节点代表一种"局面"或者"配置"，每条边代表一次"操作"或者"转移"。比如八数码问题里，每一个棋盘排列就是一个状态，滑动一次方块就是一次状态转移。比如地图导航里，每个路口是一个状态，每条路段是一次转移。比如下棋，每一个棋盘局面是一个状态，每一步落子是一次转移。
这个视角的转换非常关键。一旦你把问题建模成状态空间，搜索算法就有了用武之地。而搜索算法要解决的核心问题就是：在这张可能大到无法完整存储的图上，如何高效地找到从起点到终点的路径。
我见过不少初学者在这一步就卡住了——他们拿到一个问题，不知道怎么定义状态，不知道怎么定义操作，结果搜索算法根本没法用。我的经验是，定义状态时问自己三个问题：当前局面需要哪些信息才能唯一确定？哪些信息是冗余的可以丢弃的？操作之后状态怎么变化？这三个问题回答清楚了，状态空间就建好了。
1.2 盲目搜索和启发式搜索的分水岭
搜索算法大致可以分成两大阵营：盲目搜索（也叫无信息搜索）和启发式搜索（也叫有信息搜索）。
盲目搜索不关心目标在哪里，它只是系统性地遍历状态空间。广度优先搜索（BFS）一层一层往外扩，深度优先搜索（DFS）一条路走到黑，统一代价搜索（UCS）按照路径代价从小到大扩展。这些算法的好处是通用性强，不需要任何领域知识；坏处是效率可能极低，尤其是在状态空间巨大的时候。
启发式搜索就不一样了，它引入了一个启发函数来估计"从当前状态到目标还有多远"。有了这个估计，搜索就有了方向感，不再盲目乱撞。A*算法就是最经典的启发式搜索算法，它在很多场景下能做到既找到最优解又比盲目搜索快得多。
这两者的分水岭就在于：你有没有可用的领域知识来构造启发函数。如果有，启发式搜索几乎总是更好的选择；如果没有，那只能退回到盲目搜索。但实际情况往往是，领域知识是有的，只是你需要花心思把它转化成可计算的启发函数。
1.3 一个容易混淆的点：搜索 vs 优化
这里我要特别提醒一个概念上的区分。搜索算法和优化算法有重叠，但不完全是一回事。
搜索算法关注的是"找到一条从初始状态到目标状态的路径"，它关心的是路径的存在性和质量。优化算法关注的是"在一个解空间里找到使某个目标函数最大或最小的解"，它关心的是解本身的优劣。
举个例子，旅行商问题（TSP）既可以看作搜索问题（搜索所有可能的城市访问顺序），也可以看作优化问题（最小化总路程）。用搜索算法解TSP，你可能会用分支限界法；用优化算法解TSP，你可能会用遗传算法或者模拟退火。
在实际工程中，这两者经常混着用。比如A*算法本身是搜索算法，但它的启发函数设计往往涉及优化思想。理解这个区别，有助于你在面对具体问题时选对工具。
2. 盲目搜索：看似简单，坑却不少
2.1 BFS的适用边界比你想的要窄
广度优先搜索的逻辑很直观：从起点开始，先访问所有距离为1的节点，再访问所有距离为2的节点，以此类推。它保证在边权都相同的情况下找到最短路径。
但BFS的适用边界其实比很多人想的要窄。首先，它要求所有边的代价相同，或者至少你只关心步数而不关心代价。一旦边权不同，BFS找到的"最短路径"可能并不是代价最小的路径，这时候你需要用统一代价搜索（UCS），本质上是用优先队列代替普通队列的Dijkstra算法。
其次，BFS的空间复杂度是指数级的。它需要存储整个 frontier（边界层）的所有节点。在分支因子为b、深度为d的搜索树上，BFS的空间复杂度是O(b^d)。这个数字增长得非常快。我做过一个简单的估算：如果分支因子是10，深度是10，那 frontier 可能包含100亿个节点，内存根本放不下。
所以在实际使用中，BFS适合的是状态空间不大、或者目标深度很浅的场景。一旦深度上去了，BFS基本不可行。
2.2 DFS的空间优势与完备性缺陷
深度优先搜索走的是另一条极端路线：沿着一条路径一直走到底，走不通了再回溯。它的空间复杂度只有O(bm)，其中m是最大深度，比BFS的O(b^d)好太多了。
但DFS有两个致命缺陷。第一，它不保证找到最优解，甚至不保证找到解——如果搜索树有无限深的分支，DFS可能永远陷在里面出不来。第二，即使搜索树是有限的，DFS找到的解也可能离最优解差很远。
我在实际项目里用DFS，基本都是在状态空间是树形结构且深度有限的场景下。比如某些组合枚举问题，或者需要遍历所有可能配置的场景。一旦涉及"找最短路径"或者"找最优解"，我基本不会考虑纯DFS。
有一个改进版本叫迭代加深搜索（IDDFS），它结合了DFS的空间效率和BFS的完备性。做法是：先做深度限制为1的DFS，没找到就做深度限制为2的DFS，以此类推。虽然看起来做了很多重复工作，但由于搜索树底层节点数量远多于上层，重复的代价其实可以接受。IDDFS的空间复杂度是O(bd)，时间复杂度在分支因子有限时和BFS同阶。
2.3 统一代价搜索：Dijkstra在搜索问题中的化身
统一代价搜索（UCS）是按照路径代价从小到大扩展节点的。它维护一个优先队列，每次取出当前累计代价最小的节点进行扩展。这其实就是Dijkstra算法在搜索问题上的应用。
UCS保证找到代价最小的路径，而且不要求边权相同。它的时间复杂度取决于优先队列的实现，用二叉堆的话是O(b^(1+⌊C*/ε⌋))，其中C*是最优解代价，ε是最小边代价。这个数字可能很大，但至少它是完备且最优的。
我在做地图导航相关的项目时，UCS是基础方案。但纯UCS的问题在于它是"均匀向外扩展"的，不会朝着目标方向偏。如果起点和终点之间距离很远，UCS会探索大量无关区域。这就是为什么实际导航系统几乎都用A*而不是UCS。
实操心得：如果你不确定该用BFS还是UCS，记住一个简单规则——边权是否相同。相同就用BFS（更简单更快），不同就用UCS。但如果你有可用的启发函数，直接上A*，别犹豫。
3. 启发式搜索：让搜索有方向感
3.1 启发函数的本质：给搜索装一个指南针
启发式搜索的核心在于启发函数h(n)，它估计从节点n到目标节点的代价。这个估计值不需要精确，但它必须能提供方向性信息。
你可以把启发函数想象成指南针。没有指南针，你在一片大森林里只能系统性地搜索每一条路；有了指南针，你至少知道大致该往哪个方向走。指南针可能不精确（比如受磁场干扰），但只要它大体指向正确方向，就能大幅减少你需要探索的路径。
一个好的启发函数通常来自对问题的松弛。什么叫松弛？就是把原问题的某些约束去掉，让问题变简单，然后在简化问题上求解，得到的代价就是原问题的一个启发估计。比如八数码问题中，曼哈顿距离就是一个经典的启发函数——它假设每个方块可以不受阻碍地直接移动到目标位置，这显然是对原问题的松弛。
3.2 A*算法：最优性与效率的平衡
A*算法是启发式搜索的旗舰算法。它的评估函数是f(n) = g(n) + h(n)，其中g(n)是从起点到n的实际代价，h(n是从n到目标的估计代价。
A的美妙之处在于：**如果h(n)是可采纳的（admissible），即h(n)永远不超过从n到目标的真实代价，那么A保证找到最优解**。如果h(n)还是一致的（consistent），即满足三角不等式h(n) ≤ c(n, n') + h(n')，那么A*在扩展节点时不需要重复检查已扩展的节点，效率更高。
我见过很多人用A*的时候不检查可采纳性，结果启发函数设计得过于激进，导致找到的解不是最优的。这是一个非常隐蔽的坑，因为算法跑起来看起来很正常，只是结果悄悄变差了。
可采纳性的检查方法：对于每个状态n，问自己"从n到目标的真实最小代价是多少？我的h(n)有没有可能超过这个值？"如果有可能超过，那h(n)就不可采纳。
3.3 启发函数的设计：从曼哈顿距离到模式数据库
设计启发函数是一门手艺。太弱了，搜索没方向感，退化成UCS；太强了，可能破坏可采纳性，找不到最优解。理想情况下，你希望h(n)尽可能接近真实代价，但永远不超过它。
常见的启发函数设计方法有几种。第一种是松弛法，前面说的曼哈顿距离就是典型例子。第二种是模式数据库，预先计算某些子问题的最优代价，作为启发估计。比如在十五数码问题中，你可以只考虑部分方块，预计算它们到达目标位置的最小代价，存成数据库。第三种是地标法，选取一些关键节点作为地标，预计算它们到所有其他节点的距离，然后用三角不等式来估计h(n)。
在实际项目中，我通常从简单的启发函数开始，比如曼哈顿距离或者欧几里得距离，然后观察搜索过程中扩展了多少节点。如果扩展节点太多，再考虑用更复杂的启发函数。不要一上来就搞模式数据库，那个实现成本很高，而且不一定值得。
3.4 权重A*：当最优性不是硬需求时
有时候你不需要最优解，你只需要一个"足够好"的解，而且希望尽快找到。这时候可以用权重A*（Weighted A*），把评估函数改成f(n) = g(n) + w * h(n)，其中w > 1。
w越大，搜索越偏向于朝目标方向前进，速度越快，但解的质量可能越差。w=1就是标准A*，w→∞就变成了纯贪心搜索。权重A*不保证最优性，但它保证解的成本不超过最优解的w倍。
我在做实时路径规划的时候用过权重A*。场景是游戏中的NPC寻路，要求每帧都能快速给出路径，对最优性要求不高。把w设成1.5到2之间，速度提升很明显，路径质量下降在接受范围内。
注意：权重A*的w值需要根据具体场景调。w太大可能导致路径绕远或者卡在局部最优，w太小又达不到加速效果。我的经验是从1.2开始试，逐步往上加，观察路径质量和计算时间的权衡。
4. 对抗搜索：当对手也在做决策
4.1 极小极大算法：假设对手永远最优
前面讲的搜索算法都假设环境是静态的，没有对手。但下棋、打牌这类场景中，对手也在做决策，而且对手的目标和你的目标相反。这就是对抗搜索要处理的问题。
极小极大算法（Minimax）是对抗搜索的基础。它构建一棵博弈树，你（MAX玩家）希望最大化评估值，对手（MIN玩家）希望最小化评估值。算法从叶子节点往上回溯，MAX层取子节点的最大值，MIN层取子节点的最小值。
这个算法的假设是：对手永远会做出最优决策。这在理论上是合理的，但在实际中可能过于保守。如果对手是个新手，你按照极小极大策略走可能反而赢得不够多。不过从稳健性角度来说，极小极大是一个合理的基准。
极小极大的时间复杂度是O(b^m)，其中b是分支因子，m是搜索深度。对于围棋这种分支因子超过200的游戏，即使只搜几步，计算量也大到不可接受。所以必须引入剪枝和评估函数。
4.2 Alpha-Beta剪枝：砍掉不影响决策的分支
Alpha-Beta剪枝是极小极大的优化版本。它的核心思想是：如果已经知道某个分支的结果不可能影响最终决策，那就不需要继续搜索这个分支。
具体来说，算法维护两个值：alpha（MAX玩家当前能保证的最好值）和beta（MIN玩家当前能保证的最好值）。当alpha ≥ beta时，说明当前节点不需要再搜了，因为上层玩家不会选择这个分支。
Alpha-Beta剪枝在最好情况下能把时间复杂度降到O(b^(m/2))，相当于在相同时间内能搜索两倍的深度。这个提升非常可观。但它的效果高度依赖于节点扩展顺序——如果先扩展好的节点，剪枝效果就好；如果先扩展差的节点，剪枝效果就差。
所以在实际实现中，通常会配合移动排序（Move Ordering）来提升剪枝效率。比如先搜索历史表现好的移动，或者用浅层搜索的结果来排序。我在实现棋类AI的时候，移动排序带来的性能提升有时候比剪枝本身还大。
4.3 评估函数与搜索深度的权衡
对抗搜索不可能搜到游戏结束，必须在某个深度停下来，用评估函数来估计当前局面的好坏。评估函数的设计直接决定了AI的棋力。
评估函数通常考虑的因素包括：子力价值（比如象棋里的车马炮分值）、位置价值（比如控制中心区域）、结构价值（比如兵形是否整齐）。这些因素的权重需要仔细调整，往往要通过大量对局来自动优化。
搜索深度和评估函数之间存在权衡。搜得深，评估函数的重要性降低，但计算时间长；搜得浅，评估函数的重要性提高，但可能因为评估不准而犯错。在实际中，我通常先用一个粗略的评估函数配合较深的搜索，然后再逐步优化评估函数。
还有一个技巧叫迭代加深，在对抗搜索中也很常用。先做深度为1的搜索，再做深度为2的，以此类推，直到时间用完。这样做的额外好处是，浅层搜索的结果可以用来给深层搜索做移动排序，提升剪枝效率。
5. 搜索算法在实际工程中的选型与调优
5.1 选型决策树：从问题特征出发
面对一个具体问题，怎么选搜索算法？我总结了一个简单的决策流程。
首先问：有没有对手？有对手就用对抗搜索（Minimax + Alpha-Beta），没对手就继续往下问。
然后问：有没有可用的启发函数？有就用A或权重A，没有就用盲目搜索。
接着问：边权是否相同？相同用BFS，不同用UCS。
最后问：内存是否受限？如果内存紧张且深度有限，考虑IDDFS；如果内存充足且需要最优解，用A*。
这个决策树不是绝对的，但能覆盖大部分场景。实际中还需要考虑实现复杂度、时间预算、解的质量要求等因素。
5.2 性能调优：从数据结构到并行化
搜索算法的性能调优有几个常见方向。
数据结构优化是最直接的。优先队列用斐波那契堆还是二叉堆？哈希表用什么哈希函数？这些选择对性能影响很大。我在一个项目中把优先队列从二叉堆换成配对堆，速度提升了将近一倍。
状态去重也很关键。很多问题中，同一个状态可能通过不同路径到达。如果不做去重，搜索会做大量重复工作。用哈希表记录已访问状态是标准做法，但要注意哈希表的内存开销。
并行化是另一个方向。BFS可以按层并行，A的节点扩展也可以并行化，但并行A的负载均衡是个难题。我在多核环境下试过并行A*，加速比并不理想，因为搜索的瓶颈往往在内存访问而不是计算。
剪枝和启发函数优化往往比底层优化更有效。一个好的启发函数能把搜索空间缩小几个数量级，这比任何数据结构优化都管用。
5.3 常见坑与避坑指南
我在实际项目里踩过不少坑，这里列几个典型的。
坑一：启发函数不可采纳导致解变差。这个前面说过，但值得再强调。每次设计完启发函数，都要严格验证可采纳性。一个简单的验证方法是：随机采样一些状态，计算h(n)和真实代价，确保h(n)永远不超过真实代价。
坑二：状态表示不当导致去重失效。如果状态表示包含了冗余信息，同一个逻辑状态可能被表示成不同的形式，去重就失效了。比如八数码问题中，如果你把空格的位置也编码进状态，但空格位置其实可以由其他方块的位置推导出来，那就产生了冗余。状态表示要尽量紧凑且唯一。
坑三：优先队列的 tie-breaking 影响性能。当多个节点有相同的f值时，先扩展哪个节点会影响搜索效率。一个好的 tie-breaking 策略能显著减少扩展节点数。常见的做法是优先扩展h值较小的节点，或者优先扩展g值较大的节点。
坑四：递归实现导致栈溢出。DFS和极小极大算法天然适合递归实现，但递归深度受限于调用栈大小。在深度很大的场景下，必须改成迭代实现或者手动维护栈。
坑五：忽略浮点数精度问题。如果代价是浮点数，比较时要用容差而不是精确相等。否则可能因为精度误差导致优先队列顺序错误，进而影响最优性。
实操心得：每次实现完一个搜索算法，先用小规模测试用例验证正确性，再用大规模用例测试性能。不要一上来就跑大规模数据，出了问题很难定位。
6. 从搜索算法延伸出去：那些相关的技术
6.1 搜索与规划的交叉地带
搜索算法和自动规划（Automated Planning）有很深的渊源。规划问题通常用状态空间来表示，然后用搜索算法来求解。但规划问题往往有更复杂的动作模型和约束条件，所以衍生出了一些专门的搜索技术，比如前向搜索、后向搜索、偏序规划等。
在实际应用中，规划问题常常用启发式搜索来解，启发函数通常来自对规划问题的松弛。比如忽略某些前置条件，或者忽略某些效果，得到一个简化问题，求解简化问题得到启发估计。这和前面说的松弛法是一脉相承的。
6.2 蒙特卡洛树搜索：另一种思路
蒙特卡洛树搜索（MCTS）是另一类重要的搜索算法，它在围棋等游戏中取得了巨大成功。MCTS不依赖于精确的评估函数，而是通过大量随机模拟来估计节点的价值。
MCTS的核心步骤包括：选择、扩展、模拟、回溯。它通过不断迭代来逐步聚焦到有希望的子树。和极小极大不同，MCTS不需要搜索到固定深度，而是根据计算预算动态分配搜索资源。
我在一些决策问题中用过MCTS，它的好处是不需要设计复杂的评估函数，只要有模拟器就行。但它的缺点是收敛速度可能较慢，而且对模拟策略的质量很敏感。
6.3 搜索算法在组合优化中的应用
很多组合优化问题可以用搜索算法来解。比如背包问题、图着色问题、调度问题等。这些问题通常用分支限界法（Branch and Bound）来解，它本质上是一种带剪枝的搜索。
分支限界法的核心是：维护一个当前最优解，然后在搜索过程中，如果某个分支的下界已经超过了当前最优解，就剪掉这个分支。下界的计算通常用松弛法，这和启发函数的设计思路是一致的。
我在做资源调度的时候用过分支限界法，效果不错。但它的性能高度依赖于下界的紧致程度和分支策略。下界越紧，剪枝越有效；分支策略越好，越早找到好的可行解，从而更早开始剪枝。
搜索算法这条线，从最基础的BFS/DFS到A*再到对抗搜索和MCTS，覆盖了相当广的问题空间。我自己的体会是，真正重要的不是记住每个算法的伪代码，而是理解它们背后的设计哲学——如何在探索和利用之间做权衡，如何用领域知识来引导搜索，如何在有限资源下做出足够好的决策。这些思想在搜索算法之外的地方也同样适用。
