Probabilistic Focal Search: Accelerating Bounded-Suboptimal Search via Lower-Bound Advancement

论文概要

研究领域: ML 作者: Minh Vu Duc, Trung Le Huu, Hà Minh Hoàng 发布时间: 2026-09-11 arXiv: 2509.05828

中文摘要

有界次优搜索旨在以最优解的 \(w\) 倍范围内寻找解，同时减少搜索开销。Focal Search (FS) 在 FOCAL 集合（满足阈值 \(w f_{\min}\) 的边界节点）内使用启发式引导，但其确定性策略可能导致 \(f_{\min}\) 在多轮扩展中保持不变。本文提出概率Focal Search (PFS)，以概率 \(p\) 遵循FS引导选择，以概率 \(1-p\) 扩展OPEN集中 \(f\) 值最小的节点。后者分支推动下界前进，扩大FOCAL集合并纳入可能通向可行解的节点。通过平衡引导与下界推进，该机制在FOCAL准入延迟限制进度时能减少获得有界解的时间。作为迁移实验，我们将同一调度器应用于Dynamic Potential Search，得到概率Dynamic Potential Search (PDPS)。我们在N-Puzzle、Pancake Sorting和旅行商问题(TSP)上对比PFS与FS，并在广义覆盖TSP (GCTSP)上评估其任意时间扩展，使用多个 \(w\) 和 \(p\) 值。实验表明，当 \(f_{\min}\) 长期平台期延迟有效FOCAL准入时收益最大，概率因子可减少约90%或更多的节点扩展（如N-Puzzle和TSP）。对于任意时间算法族，Anytime PFS (APFS)在GCTSP上优于所有测试算法。当确定性搜索已高效前进时（如Pancake Sorting）收益较小，表明概率因子在FOCAL准入为搜索瓶颈时最有用。PDPS迁移显示该机制也适用于势能引导，但其共同成功效应仍依赖于领域和边界。

原文摘要

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 th...

#论文 #arXiv #ML #小凯