概率焦点搜索：通过下界推进加速有界次优搜索

arXiv:2609.10584v1 公告类型：新 摘要：有界次优搜索在最优因子 $w$ 内寻求解决方案，同时减少搜索工作。焦点搜索 (FS) 在 FOCAL 中使用启发式指导，前沿节点符合阈值 $w f_{\min}$，但其确定性策略可能使 $f_{\min}$ 在许多扩展中保持不变。我们引入概率焦点搜索（PFS），它遵循概率为 $p$ 的 FS 引导选择，并以概率 $1-p$ 扩展最小-$f$ OPEN 节点。后一个分支鼓励下界前进，扩大 FOCAL 并接纳可能导致可行解决方案的节点。通过平衡指导和下限进展，当进展受到延迟的 FOCAL 准入限制时，该机制可以减少获得有界解决方案的时间。作为二次传输实验，我们将相同的调度器应用于动态电位搜索，产生概率动态电位搜索（PDPS）。我们在 N-Puzzle、Pancake Sorting 和 Traveling Salesperson Problem (TSP) 上对 PFS 与 FS 进行基准测试，并使用多个 $w$ 和 $p$ 值评估其在广义覆盖 TSP (GCTSP) 上的任意扩展。在这些基准测试中，当 $f_{\min}$ 处于长期稳定状态延迟有用的 FOCAL 准入时，会产生最大的收益；在这样的设置中，概率因子可以将节点扩展减少约 90% 或更多（例如，在 N-Puzzle 和 TSP 上）。对于随时算法系列，随时概率焦点搜索 (APFS) 在评估 GCTSP 上的随时方法方面优于所有测试的算法。我们还观察到，当确定性搜索已经有效推进时（例如煎饼排序），收益较小，这表明当 FOCAL 准入是搜索瓶颈时，概率因子最有用。 PDPS 转移表明，该机制也转移到潜在的指导，尽管其共同成功效应仍然依赖于域和绑定。