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

Daniel Platnick, Richard Anthony Valenzano

When greedy search algorithms encounter a local minima or plateau, the search typically devolves into a breadth-first search (BrFS), or a local search technique is used in an attem…