[论文] Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via...

论文概要

研究领域: cs.AI 作者: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng, Trung Thanh Nguyen, Phuong Khanh Nguyen, Huynh Thi Thanh Binh 发布时间: 2026-09-13 arXiv: 2609.10584

中文摘要

有界次优搜索旨在以最优解的 \(w\) 倍因子内找到解，同时减少搜索开销。焦点搜索（FS）在 FOCAL 集合（满足阈值 \(w f_{\min}\) 的前沿节点）内使用启发式引导，但其确定性策略可能导致 \(f_{\min}\) 在多步扩展中保持不变。我们提出概率焦点搜索（PFS），以概率 \(p\) 遵循 FS 的引导选择，以概率 \(1-p\) 扩展最小 \(f\) 的 OPEN 节点。后者鼓励下界前进，扩大 FOCAL 并允许可能导致可行解的节点进入。通过平衡引导和下界推进，该机制可在 FOCAL 准入延迟限制进展时减少获得有界解的时间。我们还将相同调度器应用于动态势搜索，得到概率动态势搜索（PDPS）。在 N-Puzzle、煎饼排序和旅行商问题（TSP）上的基准测试表明，当长 \(f_{\min}\) 平台延迟有用 FOCAL 准入时，概率因子可减少约 90% 或更多的节点扩展。对于随时算法族，随时概率焦点搜索（APFS）在评估 GCTSP 的随时方法方面优于所有测试算法。

原文摘要

Bounded-suboptimal search seeks a solution within a factor \(w\) of optimal while reducing search effort. Focal Search (FS) uses heuristic guidance within FOCAL, the frontier nodes eligible under the threshold \(w f_{\min}\), but its deterministic policy may leave \(f_{\min}\) unchanged for many expansions. We introduce Probabilistic Focal Search (PFS), which follows the FS guided choice with probability \(p\) and expands a minimum-\(f\) OPEN node with probability \(1-p\). The latter branch encourages the lower bound to advance, enlarging FOCAL and admitting nodes that may lead to feasible solutions. By balancing guidance and lower-bound advancement, this mechanism can reduce time to a bounded solution when progress is limited by delayed FOCAL admission. As a secondary transfer experiment, we apply the same scheduler to Dynamic Potential Search, yielding Probabilistic Dynamic Potential Search (PDPS). We benchmark PFS against FS on N-Puzzle, Pancake Sorting, and the Traveling Salesperson Problem (TSP), and evaluate its anytime extension on the Generalized Covering TSP (GCTSP), using multiple \(w\) and \(p\) values. Across these benchmarks, the largest gains occur when long \(f_{\min}\) plateaus delay useful FOCAL admissions; in such settings, the probabilistic factor may reduce node expansions by about 90\% or more (e.g., on N-Puzzle and TSP). For the anytime algorithm family, Anytime Probabilistic Focal Search (APFS) outperforms all tested algorithms in evaluating anytime methods on GCTSP. We also observe that the benefit is smaller when the deterministic search already advances efficiently (e.g., Pancake Sorting), indicating that the probabilistic factor is most useful when FOCAL admission is a search bottleneck. The PDPS transfer shows that the mechanism also transfers to potential guidance, although its common-success effects remain domain- and bound-dependent.

---

*自动采集于 2026-09-13*

#论文 #arXiv #AI #小凯