★ FEATURED ARTICLE 其实我第一次意识到“搜索优化”这事有多重要是在一场算法比赛里被一道“看起来很简单”的题卡了三个小时。题面一句话给定一张网格地图走迷宫最短路径。我当时想都不想直接BFS结果运行超时。旁边的大佬只加了两行看起来不起眼的预处理跑得飞快。那时候我才明白搜索谁都会写但把搜索写得又快又稳才真正考验算法功底。这篇内容聚焦的是“对搜索的优化”围绕的核心关键词就是算法、搜索、优化。我会从剪枝策略、搜索顺序调整、记忆化、双向搜索这几个最实用的方向展开结合竞赛里常踩的坑和工程里能用上的技巧。适合三类人看准备算法面试或比赛的选手做路径规划、爬虫、推荐系统等业务的开发者以及刚开始学搜索算法、想知道“代码能跑和能跑得飞快”差距在哪的同学。1. 搜索优化的整体框架先搞清楚你优化的是什么1.1 搜索复杂度到底高在哪很多人一提到搜索优化第一反应就是“加剪枝”。但剪枝只是手段之一如果连搜索慢的根源都没找到剪枝往往只是东一榔头西一棒子。搜索算法——我主要指深度优先搜索DFS、广度优先搜索BFS这类暴力搜索——慢的本质是它把整个状态空间几乎都走了一遍。状态空间有多大决定了时间上限。比如说走迷宫每个格子有四个方向不考虑重复访问的话状态数量是4的N次方这种指数级别。而所谓“优化搜索”本质上做的是四件事缩小状态空间换一种状态表示方式让同一问题用更少的节点表示。减少访问节点数通过剪枝提前排除不可能通向目标的路径。降低单次转移成本用更高效的数据结构或预处理让每个状态展开得更快。更快找到目标调整搜索顺序让目标尽早出现在搜索树靠前的位置。这四个方向可以作为任何搜索优化方案的分析框架。拿到一道搜索题先思考“我慢在哪”再决定用哪种手段。1.2 用迷宫问题理解四种优化方向我用一个简单迷宫例子说明。假设有一个10x10矩阵0表示空地1表示障碍物求从左上角到右下角的最短路径。缩小状态空间如果你记录的是“当前坐标已经走过的路径”那么状态数爆炸性地多如果你改为记录“当前坐标”并用visited数组标记已访问那状态数最多100个复杂度从指数降为O(100)。减少访问节点数如果终点在右下角你从左上开始搜索时优先扩展“更靠近右下角”的节点——这就是A*的思路可以少访问一堆和终点方向完全相反的死胡同。降低单次转移成本比如预处理每个格子到终点的曼哈顿距离然后查表而不是每次计算。或者把二维坐标编码成一个整数减少节点入队时对象创建的开销。更快找到目标这就是搜索顺序调整。BFS天然按层次展开但不代表所有场景都必须BFSDFS配合迭代加深IDDFS往往能更快找到出口。我很喜欢把搜索优化类比成“在图书馆找一本书”暴力搜索是走到每一排书架前把每本书都抽出来翻一遍优化就是先看图书分类号缩小范围剪枝先去大概率放这本书的区域启发式再用索引快速定位预处理。所以在写代码之前先把你的状态图在纸上画出来。弄清楚节点代表什么、转移边有几条、目标在哪再谈优化否则就是瞎忙活。2. 剪枝策略搜索优化的核心手段2.1 可行性剪枝与最优性剪枝两类剪枝的判定逻辑剪枝是搜索优化里最直观、收益也最明显的手段。但剪枝不是瞎剪它是根据当前状态的信息判断“这棵子树里不可能存在答案”于是提前回溯。剪枝大致分两类第一类叫可行性剪枝。意思是当前状态虽然合法但继续往下走永远不可能到达目标状态。典型例子是八数码问题中的奇偶性判断如果打乱后的序列逆序对的奇偶性和目标不一致那这个状态无论怎么走都无解直接干回。迷宫也可以做类似判断如果当前点已经被障碍物包围且不是终点那继续向下扩展纯属浪费。第二类叫最优性剪枝。通常用于求解最优化问题。当搜索进行到某个状态时如果已经走的步数或代价已经大于等于当前已找到的最优解那这棵子树直接砍掉。因为就算后面走得再顺它也不可能比当前答案更好。这道题用DFS回溯求解的话很多新手容易漏掉这个剪枝然后看着程序在数据大一点时卡死。举个例子在N皇后问题中“当前已放置的皇后数剩余最大可放置数 目标皇后数”就是可行性剪枝“当前已放置皇后数 当前最优解”就是最优性剪枝。2.2 上下界剪枝估算“当前状态到目标的最短距离”上下界剪枝是更精细的一类剪枝它其实算最优性剪枝的增强版。思路是为“从当前状态到目标状态还需要多少步”做一个快速的下界估计。如果“当前已走步数下界估计”已经大于等于当前最优解剪掉。这个“下界估计”不需要非常精确但必须满足一个要求它必须是一个乐观估计也就是说真实需要的步数不可能比这个估计值更少。否则你把可能包含最优解的分支剪掉了答案就不对了。最常用的下界估计方式是曼哈顿距离和欧几里得距离。比如15-puzzle(数字华容道)问题当前状态下每个数字格子到其目标格子的曼哈顿距离之和就是到达目标状态步数的一个下界。因为每走一步最多只能让一个数字的曼哈顿距离减少1所以总距离修正是最优解的一个下界。实践经验是剪枝判断本身也有开销。有些剪枝条件写起来很复杂每次状态转移都要额外计算反而把搜索拖慢了。所以我的原则是先做开销低、效果好的剪枝比如简单的越界判断、已访问判断再做开销高、效果显著的剪枝比如启发式下界。在搜索优化里算法本身不是越复杂越好而是要在剪枝收益和计算开销之间找到平衡。2.3 剪枝时机与剪枝顺序的工程细节代码层面的剪枝顺序也有讲究。我在实测中总结出一个规律同样的剪枝条件调换一下判断顺序时间差异可能达到两倍。原因很简单不同剪枝条件的计算开销差异很大。边界检查通常只需要一次数组下标比较几乎不耗时间而启发式函数可能需要遍历所有剩余元素求和。所以在DFS循环体里应该先用便宜的快判断把明显不行的分支拦下来再用贵重的剪枝去处理剩下的分支。举个例子我在解数独时每个空格子填数字钱的剪枝顺序判断格子是否在棋盘范围内O(1)判断数字是否已经出现在同一行/列/宫格O(1)到O(9)如果还在用MRV启发式则计算该格子剩余候选数的数量O(9)如果把后两步对调每次都要计算候选数但其中有大量数字其实早就被行列冲突拦下来了白白浪费计算。最后提一个很多博主不会讲但非常实用的小技巧对剪枝条件打点。在调试搜索优化时用一个全局计数器记录在每个剪枝点被剪掉的分支数量输出观察。哪类剪枝实际上一次都没触发过删掉它。哪类剪枝砍掉的节点数最多把它放在更靠前的位置。我用这个方法一次性把一道搜索题从4秒优化到了0.3秒。3. 搜索顺序与启发式设计同样的算法不同的命运3.1 为什么搜索顺序会影响搜索树大小很多初学者不理解同一个DFS为什么换一下邻居节点的遍历顺序性能差别就这么大关键在于搜索过程中一旦找到可行解或最优解很多剪枝条件就开始生效。如果你的搜索顺序能更早找到一个较优解那么之后的最优性剪枝就能砍掉更多分支。反过来如果每次都先去搜索那些几乎不可能出解的分支那么不仅找到较优解的时间晚整棵搜索树也会变得又深又大。最典型的是数独求解。如果你从(0,0)开始按顺序填碰上候选数很多的格子一个格子就有十几种选择整个搜索树疯涨。但如果你每次都先填候选数最少MRVMinimum Remaining Values的那个格子一旦某个格子没有候选数字立刻回溯剪枝效率会高得惊人。这就是搜索顺序优化的核心思路优先扩展“最受约束”或“最有希望”的分支让搜索树变得更瘦、更浅。3.2 启发式评估函数从BFS到A*的关键一步在带权图、路径规划这类问题里纯BFS搜最短路径当然没问题但它只会一层一层向外扩展完全没有方向感。A*算法在BFS的基础上给每个节点引入了一个评估函数f(n) g(n) h(n)其中g(n)表示从起点到当前节点的实际代价h(n)表示从当前节点到目标节点的估计代价。每次从优先队列里取f值最小的节点扩展相当于让搜索始终“朝着目标方向走”。h(n)的设计决定了A能不能找到最优解。如果h(n)小于等于节点到目标的真实代价A保证找到最优路径这样的启发式函数称为“可采纳启发式”。最常用的设计就是曼哈顿距离和欧几里得距离。我在写A做游戏寻路时踩过一个隐蔽的坑地图上有权重不同的地形比如沼泽地代价高道路代价低我当时直接用曼哈顿距离除以最大速度作为启发式在某些地形组合下h(n)会高估真实代价导致A找到的路径并不是最短的。后来改成用“起点到终点的直线欧几里得距离”作为统一下界才恢复正确。所以写A*的朋友务必检查两个东西一是h(n)是否满足可采纳性二是优先队列中元素的比较是否稳定避免相同f值节点反复弹出。3.3 迭代加深DFSIDDFS用时间换空间的搜索优化很多搜索场景你不用BFS因为BFS占用内存跟队列长度成正比太深的状态空间会直接内存爆炸。但DFS呢它可能一头扎进一条路径的尽头绕很远。这时可以试试IDDFS。迭代加深的思路很朴素先限定DFS深度为1搜一遍没找到再把深度限制加为2搜一遍不断扩展深度直到找到目标。听起来重复搜索很多次很浪费但实际上深度限制为d的那次搜索前面所有小于d的层都重新扫了一遍总复杂度大约是O(b^d)级别跟BFS同阶。但好处是什么是内存占用只有O(d)比BFS的O(b^d)小太多了。我看很多人不太敢用IDDFS其实它配合启发式上限估计之后效果非常好。我做过一个拼图小游戏状态空间巨大BFS根本不现实但IDDFS加上曼哈顿距离剪枝几十秒就能出解。遇到“状态数多但目标深度不深”的搜索建议优先考虑这个方案。4. 记忆化搜索与状态压缩从指数级到多项式级的跃迁4.1 记忆化搜索把重复计算变成查询DFS慢的另一大原因是同一个子问题会被反复计算无数次。拿经典的斐波那契数列来说裸递归算fib(40)需要上亿次调用而加了记忆化之后只需要算40个状态。记忆化搜索的本质就是在DFS的递归过程中把已经求解过的子问题答案缓存起来。下一次遇到相同状态时直接查表返回不再重复递归推演。这样就把一棵指数型的搜索树压缩成一个有向无环图DAG每个状态只被计算一次。在实际比赛里我几乎每天都会用到记忆化搜索。经典题目是“滑雪问题”给定一个矩阵求最长递减路径。朴素DFS是每个点都作为起点搜一遍复杂度O(n^2 * m^2)。加了记忆化之后每个点最多搜一次复杂度降到O(n*m)。差距是指数级到多项式级的差别。4.2 状态压缩把复杂状态编码成整数索引记忆化搜索的一个难点在于DFS里的“状态”往往不是一个整数而是一个组合。比如TSP旅行商问题状态是“当前在城市i且已经访问过的城市集合是S”。怎么存这个状态做法是状态压缩。用一个二进制整数表示访问集合比如visited 0b1011表示城市0、1、3已经被访问过假设最多20个城市。然后用一个二维数组dp[1n][n]来记录“当前在城市j且已访问集合为mask”时的最短路径。这样状态数从n!级别直接降到2^n * n级别。配合记忆化搜索20个城市的TSP问题可以在不到一秒内跑完。你要是用纯排列的DFS去搜20个城市大约20!种排列这基本上是不可能的任务。状态压缩的工程细节二维数组的大小是(1n) x n注意int溢出。如果n比较大可以使用哈希表(map)代替数组牺牲一点速度换内存。还有尽量用位运算来操作状态比如判断第i位是否为1用(mask i) 1置1用mask | (1 i)而不是把它转成字符串否则每次状态转移都要重新解析白花开销。4.3 八数码问题的康托展开状态编码的进阶做法如果你处理的是一个全排列类的状态比如八数码棋盘上1~8的排列也可以用康托展开把一个排列映射成一个唯一的整数id。这样dp数组就变成了一个一维数组状态判断和去重都非常高效。康托展开的原理不复杂对于一个长度为n的排列计算它在所有排列中的字典序序号。公式是X a1*(n-1)! a2*(n-2)! ... an*0!其中ai表示第i位右边有多少个数字小于当前数字。展开和逆展开都是O(n^2)预处理阶乘之后甚至可以更快。很多同学一听“康托展开”觉得理论太深其实实操起来就是二十几行代码。我个人的看法是如果搜索的状态是“全排列”类型且n不超过10即10!个状态以内用康托展开或直接用数组映射都能接受但如果n稍微大一点同时状态比较稀疏那就用哈希表灵活得多。5. 双向搜索与Meet in the Middle指数级搜搜的两个奇招5.1 双向BFS从起点和终点同时发起进攻双向BFS的原理很简单。普通的BFS从起点单向扩展如果目标深度是d分支因子是b则状态数是b^d。双向BFS则同时从起点和目标点出发各扩展b^(d/2)个节点两边相遇时总状态数大约为2*b^(d/2)。“大约”二字用在这里是因为实际情况取决于图的具体结构但数量级差距是非常明显的。举例迷宫问题如果深度20层分支数4单向BFS要访问约1万亿个状态但双向BFS每边只需访问4^10约100万个状态两边同时搜索的时候总访问量在200万上下。实际跑起来那就是从超时到0.1秒的差距。双向BFS的工程要点一是要交替扩展两个队列不能把一边全部扩展完再扩展另一边否则就退化成了两个单向BFS二是要设计好“相遇”的判断通常是在扩展某一层的节点时检查该节点是否在另一个方向的vis数组中被访问过三是两边的扩展深度要尽量均衡防止大量节点堆积在某一边。5.2 Meet in the Middle把搜索空间一分为二再合并有一类题目叫“子集和问题”给一个包含40个数的数组问是否存在一个子集的和恰好为target。如果直接枚举所有子集2^40约1万亿种情况你会怀疑人生。Meet in the Middle的做法是把40个数拆成前20个和后20个分别枚举两组的所有子集和各2^20约100万个。然后把第一组的子集和排序对于第二组的每个子集和sum在第一组的排序数组中二分查找是否存在target - sum。整个复杂度从2^40降到2^20 * log(2^20)实际操作中大数组也可以秒出结果。这招的核心思想是不要试图一口气走完整条路先走一半再走一半然后把两条半路的成果拼接起来。这跟双向BFS是一个思路的双胞胎。5.3 双向搜索的适用条件与避坑清单不是所有搜索都能双向。我用一张表整理一下场景的适用性搜索类型适用条件典型案例双向BFS已知起点和目标状态边权相同迷宫最短路径、单词接龙Meet in the Middle搜索过程可拆成两半合并代价小子集和、排列组合计数IDDFS目标深度不确定内存受限拼图类游戏、博弈搜索A*有启发式函数边权任意非负路径规划、游戏AI常见的坑有以下三个第一双向BFS的“相遇”判断写错比如只在一边的vis中查找导致错过相遇点第二Meet in the Middle合并阶段排序去重没做好重复枚举导致答案重复统计第三状态空间过大的时候仍然强行双向连一半的状态都存不下。这些都属于“看起来会写、一写就错”的典型问题建议先在小数据上验证正确性再上大数据。6. 从竞赛题到工程应用搜索优化思路的延伸6.1 搜索引擎的“预剪枝”倒排索引与相关度排序很多人觉得搜索优化只是算法竞赛里的概念离工程很远。实际上日常用到的搜索引擎就是搜索优化思想的极致体现。你搜一个关键词搜索引擎不可能把整个互联网上所有网页都遍历一遍再给你排序。它做的是“预剪枝”通过倒排索引先根据关键词锁定一小批包含该词的文档再由相关度算法对这些文档排序返回给用户。倒排索引本质上就是一种预处理把“文档到词”的映射反过来变成“词到文档”的映射。这和搜索里的预处理来降低转移成本是同一个思路。做工程里如果遇到需要频繁在大量数据中查找某个特征的场景都可以考虑构建索引或映射表而不是每次搜索时遍历全量数据。6.2 路径规划与游戏AIA*与启发式搜索的日常形态地图App的路径规划、游戏里的NPC寻路底层基本都是A*算法或它的变体。在做这些工程时除了要维护好启发式函数还需要做平滑、避障、层次化路径搜索等优化这又是搜索优化的延伸领域。我给一个小建议在工程中不要一上来就写复杂优化。先把朴素的搜索跑通再逐步加上“缓存”“剪枝”“启发式”这些增强并测量每一步对性能的提升。很多人喜欢直接上最复杂的优化结果debug极其痛苦而且优化变多后往往不知道是哪个改动带来的性能提升。6.3 KMP与二分被忽略的搜索优化鼻祖严格来说KMP字符串匹配算法和二分查找也可以看作搜索优化。它们做的事都是在搜索过程中利用已知信息跳过大量不可能匹配的位置。二分查找相当于利用数组有序性每次减半搜索空间KMP利用“已匹配前缀的后缀等于模式串的前缀”这个信息让文本指针永不回溯。它们都属于“减少访问节点数”这一方向的极致体现。建议学搜索优化的时候把这几种经典算法放在一起对比着看你会发现它们的内核高度一致拒绝盲目穷举利用信息排除无关分支。7. 实操总结搜索优化的调试与复盘方法最后这部分我想分享一些很实操的方法论。这些内容不是书本上写的公式而是我在一次次被超时和Wrong Answer折磨之后攒出来的经验。7.1 先跑小样本验证正确性再优化优化搜索算法前最重要的一件事是先确认你的朴素算法逻辑是对的。很多同学的搜索本来就写错了比如访问数组忘记标记回溯、边界判断漏了角落格子、状态转移错了一位然后拿着错误程序去做性能优化越改越乱。我的步骤永远是小样例如3x3迷宫、6个数字的子集和先跑朴素的DFS或BFS确保输出正确结果。加优化后重新跑同一组小样例答案一致才说明优化没有改变算法行为。7.2 量化观察统计搜索节点数很多有经验的选手优化搜索时不会只看时间他们会加入统计变量来观察“搜索树被剪掉多少分支”。这比看时间更准确因为时间受机器负载和编译器优化影响波动较大。我之前做一道搜索优化题用计数器输出“扩展节点数、被剪枝的分支数、回溯次数”然后针对性地调整剪枝条件和搜索顺序。不到二十分钟节点数从80万降到3万执行时间从2.4秒降到0.15秒。这种“数据驱动”的优化方式比拍脑袋改代码有效得多。7.3 一次只改一个变量搜索优化里很容易出现“我加了一堆优化性能反而变差”的情况。原因往往是某个复杂的剪枝计算成本太高或者启发式函数与另一个剪枝条件相互冲突。解决方式是一次只引入一个优化变量用控制变量法对比前后差异。如果某个优化在数据测试中让性能变差了说明它不适合当前问题果断回退不要舍不得删。7.4 温度笔记记录优化矩阵我会维护一张表格记录不同搜索优化方案在不同类型题目上的表现。比如“数独类题目MRV优先 可行性剪枝效果最好”“最优路径类题目A* 曼哈顿距离 双向扩展效果最好”“组合计数类题目Meet in the Middle 排序去重效果最好”。下次遇到类似的新题先翻之前的记录直接使用经过验证的优化组合。这大大减少了重复试错的成本。好了这次的分享就到这里。说到底搜索优化最核心的思维习惯是不把搜索当作“碰运气式的穷举”而是时刻思考“我怎么知道这棵子树肯定不含答案”。希望这篇文章带给你的不只是几个具体的技巧更是一套分析搜索问题的框架。下次再碰到“运行超时”的报错先别急着焦虑按这篇文章的方法一步步排查你会发现自己越来越能掌控搜索的节奏。
阅读完成 · 觉得有帮助？
