Expected Runtime Comparisons Between Breadth-First Search and Constant-Depth Restarting Random Walks

当贪心搜索算法遇到局部最小值或高原时，搜索通常会陷入广度优先搜索（BrFS），或者使用局部搜索技术来尝试找到一条出路。在这项工作中，我们正式分析了BrFS和常数深度重启随机游走（RRW）的性能——这两种方法常用于寻找高原/局部最小值的出口——以更好地理解每种方法何时最适用。特别地，我们正式推导了在给定目标深度下的一组均匀分布的目标情况下，BrFS的预期运行时间。然后，我们证明了如果在目标深度有足够的目标，RRW将比BrFS更快地在树上找到出口。我们将这个阈值称为交叉点。我们的边界表明，交叉点随着树的分支因子、目标深度和随机游走深度误差的增加而线性增长，而树的大小则随着分支因子和目标深度的指数增长。最后，我们讨论了这个边界的实际影响和适用性。

分析BFS和RRW算法在解决局部最小值问题时的性能表现，探讨两种算法的适用场景。

通过数学分析得出RRW算法在树形结构中的表现优于BFS算法的阈值，即RRW算法更适用于目标深度处有足够目标的情况。

论文通过数学分析得出了RRW算法在树形结构中的表现优于BFS算法的阈值，这一阈值与树的分支因子、目标深度和随机游走深度误差成正比，而树的大小则与分支因子和目标深度成指数关系。论文提供了实验结果和开源代码，值得深入研究。

与本文相关的研究包括：1. "Local search strategies for satisfiability testing"；2. "Restart strategies for local search"；3. "Analysis of simple local search algorithms on random instances of satisfiability problems"。