Random-first search?

Question

The two most common ways to traverse a graph are breadth-first search and depth-first search. Both of these search algorithms follow a common template:

• Create a worklist W, seeded with the start node s.
• While the worklist isn't empty:
  • Remove the first element of the worklist; call it v.
  • If v is not visited:
    • Mark v as visited.
    • For each node u directly connected to v, add u to W.

In a breadth-first search, the worklist W is implemented as a FIFO queue, while in depth-first search it's a LIFO stack. If W is a priority queue, you get uniform-cost search.

A while back I asked a question about a data structure for choosing random elements out of a bag. If you implement the above worklist W using this random bag, then you get a "random-first search" algorithm that randomly explores the nodes in the graph starting with the initial node.

My question is this: are there any known algorithms that use this type of search? That is, are there algorithms that work by generating a random spanning tree of the graph in this fashion?

Answer 1

Automatic puzzle generation is an application for which random-first search is a useful strategy.

Suppose you wish to generate an instance of a combinatorial puzzle like Sudoku. One approach is to generate a random, completely solved, instance, and then remove numbers as long as there's still a unique solution. How do you generate that random solved instance in the first place? You start with an empty grid and apply a random-first solving algorithm. In fact, it proves to be fairly easy to use the same code for both generation and solution, by switching between random-first and best-first strategies for picking the next number to try.

This is exactly what we did when writing the Nintendo DS game Zendoku, and I wrote a detailed article about our approach.

See also this answer discussing maze generation using randomized Prim's algorithm.

Answer 2

This is exactly an implementation of the best-first search given a random heuristic.