概率焦点搜索让节点扩展减少90%，突破有界次优搜索瓶颈！
Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement
📖 AI 总结
本文提出概率焦点搜索（PFS），一种用于有界次优搜索的新算法。传统焦点搜索（FS）在阈值 w·f_min 限定的 FOCAL 集合内依据启发式选择扩展节点，但其确定性策略可能导致 f_min 长期停滞，使 FOCAL 无法纳入新的有潜力的节点。PFS 以概率 p 沿用 FS 的启发式引导选择，以概率 1-p 扩展 OPEN 表中 f 值最小的节点，从而推动下界前进、扩大 FOCAL，平衡引导与下界推进。作者在 N-Puzzle、煎饼排序和旅行商问题上对比 PFS 与 FS，并在广义覆盖 TSP 上评估其任意时间版本 APFS。结果显示，当 f_min 长时间停滞、FOCAL 准入成为瓶颈时，PFS 可将节点扩展数减少约 90% 甚至更多；而在确定性搜索本身推进高效的场景（如煎饼排序）中收益较小。此外，该调度机制可迁移至动态势能搜索，形成 PDPS，但其效果依赖具体问题域与界值。
🔑 关键词速览
| Bounded-Suboptimal Search | 有界次优搜索：允许解的质量在最优解的一定因子范围内，以换取更低的搜索开销。 |
| Focal Search (FS) | 焦点搜索：一种有界次优搜索算法，在满足阈值 w f_min 的 FOCAL 集合内利用启发式选择节点扩展。 |
| Probabilistic Focal Search (PFS) | 概率焦点搜索：本文提出的算法，以概率 p 遵循 FS 引导选择，以概率 1-p 扩展最小 f 节点以推进下界。 |
| f_min | 当前 OPEN 表中最小 f 值，作为有界次优搜索的阈值基准，其推进可扩大 FOCAL 集合。 |
| Anytime Probabilistic Focal Search (APFS) | 任意时间概率焦点搜索：PFS 的任意时间扩展，能在搜索过程中随时返回可行解并持续改进。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅