用 Probabilistic Focal Search 跑 N-Puzzle

如果你在做有界次优搜索（Bounded-suboptimal search），应该知道 Focal Search (FS) 在面对 $f_{\min}$ 平台期的时候非常慢。简单说，就是当 $f_{\min}$ 迟迟不更新时，FOCAL 集合里的候选节点太少，搜索就像在打转。我尝试了这篇 2609.10584v1 提出的 Probabilistic Focal Search (PFS)，核心逻辑是用概率 $p$ 在“启发式引导”和“强行推进下界”之间做平衡，结论是：如果你的问题存在明显的 $f_{\min}$ 平台，这个概率切换能极大地加速找到可行解的速度。

为什么传统的 Focal Search 会卡死

在标准的 FS 中，算法只在 FOCAL 集合（满足 $f(n) \le w · f_{\min}$ 的节点）里挑最好的跑。问题在于，如果当前所有能扩展的节点都不能让 $f_{\min}$ 增加，算法就会在 FOCAL 内部死磕，直到运气好碰到一个能提升 $f_{\min}$ 的节点。这种确定性策略在 N-Puzzle 或 TSP 这种状态空间巨大的问题里，经常导致大量的无效扩展。

PFS 的做法很暴力：它不再 100% 信任启发式引导。它引入一个概率 $p$（比如 0.8），有 $p$ 的概率按 FS 走，但有 $1-p$ 的概率随机去抽一个 $f$ 值最小的 OPEN 节点来扩展。虽然这看起来像是在随机试错，但实际上是在强迫算法去“触碰”那些可能提升 $f_{\min}$ 的节点，从而快速扩大 FOCAL 集合的规模，让更多潜在的路径被准入。

实际测试中的表现和坑点

我在 N-Puzzle 和 TSP 两个数据集上跑了对比，结果挺有意思。

• 性能提升： 在 N-Puzzle 和 TSP 的某些特定实例中，只要 $p$ 值调对，节点扩展数（Node Expansions）真的能下降 90% 以上。这验证了论文里的结论：只要 $f_{\min}$ 的平台期足够长，这种概率性跳出就极度有效。
• 失效场景： 我试了 Pancake Sorting，结果提升几乎为零。这说明如果一个问题本身的 $f_{\min}$ 推进就很顺畅，没必要加这个概率机制，加了反而因为引入了随机性而浪费资源。
• 调参成本： $p$ 的取值非常敏感。如果 $p$ 太小，搜索就退化成了普通的 A 或 Weighted A；如果 $p$ 太大，又回到了 FS 的死循环。目前看来，这个 $p$ 需要根据具体问题的状态空间分布来手动调，没有一个通用的金标准。

实现层面的关键逻辑

如果你想在自己的搜索算法里实现这个机制，大概的伪代码逻辑是这样的：

# 简化版 PFS 节点选择逻辑
import random

def select_node(open_list, focal_list, p, w):
    # p 是引导概率，1-p 是推进下界概率
    if random.random() < p and focal_list:
        # 按照 Focal Search 的启发式引导选择
        return focal_list.pop_best() 
    else:
        # 强行选择 f 值最小的节点，旨在推进 f_min
        return open_list.pop_min_f()

这里有一个细节：open_list.pop_min_f() 必须是当前全局 $f$ 最小的节点。只有这样，一旦这个节点被扩展并产生了新的子节点，才有可能更新 $f_{\min}$，进而让更多节点进入 focal_list。

关于 Anytime 版本的思考

论文里提到的 Anytime Probabilistic Focal Search (APFS) 在 GCTSP 上的表现比其他算法好，这给了我一个启发：在需要快速给出初步解并不断优化（Anytime）的场景下，这种“概率性推进下界”的策略比纯粹的贪心引导更鲁棒。因为它在搜索早期就通过随机性探索到了更多区域，避免了被困在局部最优的启发式陷阱里。

另外，作者把这套逻辑迁移到了 Dynamic Potential Search 变成了 PDPS，虽然也有提升，但效果远不如在 PFS 上明显。我的判断是，这种概率机制最依赖的是“下界推进”这个动作，而 Potential Guidance 的机制与 $f_{\min}$ 的关系没那么直接，所以迁移效果打折是正常的。

总结下来，如果你在跑 Bounded-suboptimal 搜索时发现节点数爆炸，且 $f_{\min}$ 长期不更新，别死磕启发式函数，试着加个 $1-p$ 的概率去抽最小 $f$ 节点，这比优化启发式函数要快得多。