概率聚焦搜索PFS：让有界次优搜索提速90%的新机制

有界次优搜索的效率瓶颈在哪里

在路径规划、拼图求解、旅行商问题（TSP）这类经典搜索问题中，找到最优解往往代价高昂。**有界次优搜索（Bounded-Suboptimal Search）**提供了一个务实的折中方案：它不追求绝对最优，而是保证找到的解在最优解的 $w$ 倍范围内，以此大幅降低搜索开销。

聚焦搜索（Focal Search, FS）是这一领域的经典方法。它维护一个名为 FOCAL 的候选集合，其中包含所有满足阈值 $w f_{\min}$ 的前沿节点，然后在这个受限集合内用启发式函数进行引导选择。这种设计的初衷是兼顾解的质量与搜索速度。

问题在于，FS 的确定性策略存在一个隐蔽的短板：在许多次扩展中，下界 $f_{\min}$ 可能长时间保持不变。这意味着 FOCAL 集合无法扩大，一些可能通往可行解的节点迟迟无法被纳入候选，导致搜索陷入低效的"平台期"。

PFS 的核心思路：用概率打破平台期

这篇 arXiv 论文提出的概率聚焦搜索（Probabilistic Focal Search, PFS），正是针对上述瓶颈设计。它的机制相当简洁：

• 以概率 $p$ 遵循 FS 的启发式引导选择（保持原有的搜索质量导向）；
• 以概率 $1-p$ 扩展 OPEN 列表中 $f$ 值最小的节点。

第二个分支是关键所在。扩展最小 $f$ 节点会推动下界 $f_{\min}$ 前进，从而扩大 FOCAL 集合，让更多可能通往可行解的节点进入候选范围。换句话说，PFS 在"启发式引导"与"下界推进"之间做了一个动态平衡。

这种设计的精妙之处在于：当搜索进展受限于 FOCAL 迟迟无法纳入有用节点时，概率化的下界推进能够显著缩短抵达有界解的时间。而当确定性搜索本身已经高效推进时，这个机制的介入几乎不会带来负担。

实验结果：最高节省90%以上的节点扩展

研究团队在多个经典基准上对 PFS 与 FS 进行了对比，涵盖 N 数码问题（N-Puzzle）、煎饼排序（Pancake Sorting）和旅行商问题（TSP），并使用了多组不同的 $w$ 和 $p$ 取值。

结果呈现出清晰的规律：当长时间的 $f_{\min}$ 平台期拖延了有用的 FOCAL 纳入时，PFS 带来的收益最大。在 N-Puzzle 和 TSP 这类场景中，概率因子可以将节点扩展量减少约 90% 甚至更多。这是一个相当可观的效率提升。

相比之下，在煎饼排序问题上收益明显更小。原因在于该问题中确定性搜索本就能高效推进，FOCAL 纳入并不构成瓶颈。这个对比恰恰印证了论文的核心论点：概率因子的价值高度依赖于 FOCAL 纳入是否是搜索的瓶颈所在。

迁移到 Anytime 与势能引导算法

PFS 的机制并不局限于聚焦搜索本身。论文将同样的调度策略迁移到了另外两个方向，验证其通用性。

Anytime 扩展：APFS

研究者为 PFS 设计了 anytime 扩展版本——Anytime Probabilistic Focal Search（APFS），并在广义覆盖旅行商问题（GCTSP）上进行评估。结果显示，APFS 在所有参与测试的 anytime 方法中表现最优。对于需要"随时可给出当前最好解"的应用场景，这一结果具有实际意义。

势能引导迁移：PDPS

作为次要的迁移实验，作者将同一调度器应用于动态势能搜索（Dynamic Potential Search），得到概率动态势能搜索（Probabilistic Dynamic Potential Search, PDPS）。实验表明，该机制确实能够迁移到势能引导的框架中，不过其带来的"共同成功"效应仍然取决于具体领域和界限设置，并非在所有情况下都稳定生效。

对搜索算法研究的启示

PFS 的贡献不在于设计一个复杂的新框架，而在于用一个轻量的概率机制，精准命中了聚焦搜索的结构性弱点。它揭示了一个值得关注的洞见：在有界次优搜索中，下界推进本身就是一种有价值的"探索"行为，而确定性策略往往忽视了这一点。

从工程角度看，这类方法的吸引力在于改造成本低——只需在原有搜索循环中引入一个概率分支，就能在特定场景下获得数量级的效率提升。同时，实验也诚实地指出了它的适用边界：当搜索本身没有平台期瓶颈时，收益有限。这种对适用条件的清晰界定，反而增强了方法的实用参考价值。

对于从事路径规划、组合优化和多智能体寻路的研究者与工程师而言，PFS 提供了一个值得纳入工具箱的低成本优化思路，尤其适用于那些容易陷入 $f_{\min}$ 平台期的问题域。