有界次优搜索的目标是找到一个代价不超过最优解 $w$ 倍的解，同时尽可能减少搜索工作量。焦点搜索（Focal Search, FS）在满足阈值 $w f_{\min}$ 的前沿节点集合 FOCAL 中使用启发式引导，但其确定性策略往往导致 $f_{\min}$ 在多次扩展中保持不变，从而限制了 FOCAL 的扩张。
我们提出 概率焦点搜索（Probabilistic Focal Search, PFS）：以概率 $p$ 采用 FS 的引导选择，以概率 $1-p$ 扩展 OPEN 中的最小 $f$ 节点。后者的作用是推动下界 $f_{\min}$ 前进，使 FOCAL 规模增大，进而允许更多可能通向可行解的节点进入 FOCAL。通过在引导与下界推进之间取得平衡，PFS 能在 FOCAL 入选受阻时显著缩短获得有界解的时间。
作为二次实验，我们将相同的调度器移植到 动态潜力搜索（Dynamic Potential Search），得到 概率动态潜力搜索（Probabilistic Dynamic Potential Search, PDPS）。我们在 N‑Puzzle、煎饼排序和旅行商问题（TSP）上对 PFS 与传统 FS 进行基准测试，并在广义覆盖 TSP（GCTSP）上评估其 anytime 变体。实验使用多组 $w$ 与 $p$ 参数。
结果表明：当 $f_{\min}$ 长时间停滞导致 FOCAL 入选受阻时，PFS 的收益最大；在这些情形下，节点扩展数可降低约 90% 以上（如 N‑Puzzle 与 TSP）。在 anytime 系列中，Anytime Probabilistic Focal Search (APFS) 在 GCTSP 上的表现优于所有对比算法。相反，在 Pancake Sorting 等 deterministic 搜索已经能够快速推进下界的任务中，概率因子的提升有限，说明其价值主要体现在 FOCAL 入选成为瓶颈的场景。PDPS 的实验结果显示该机制同样可以迁移到潜力引导的搜索，但其效果仍受具体领域和界限设置的影响。
点评：概率焦点搜索通过在确定性引导和下界推进之间引入随机调度，有效缓解了 FOCAL 入选的瓶颈，在多数基准上实现了显著的搜索效率提升，尤其适用于 $f_{\min}$ 易出现长平台期的问题。