continuations for search

[Hendrik Boom]

Depth-first searches are easy to code by simple recursion.

Breadth-first searches are good for finding short solutions and not getting
caught in infinite recursions.

Are there any ready-made tools in Racket for turning depth-first search
code into breadth-first by strategic use of continuations?

That is, at strategic points in the depth-first search you spawn
continuation instead of going deeper and save that continuation into a
stable somewhere so as to ride it again later?

-- hendrik

[Neil Van Dyke]

I don't recall seeing that implemented in Racket/Scheme, but, in class,
years ago, Leslie Kaelbling mentioned using Scheme captured
continuations for AI search backtracking, as I mentioned (and Matthias
has good comments in that thread):
https://groups.google.com/d/msg/racket-users/jHPtw3Gzqk4/AAqsc-x-AgAJ

That might've been in the class for which we were using a draft of the
Russell&Norvig text; I don't know whether it was mentioned in there. 
IIRC, Leslie at the time was coming from Stanford AI Lab tradition (West
Coast tradition OG, to MIT's East Coast).

For most purposes, perhaps one would probably want to write a search two
different ways: one that takes advantage of Scheme's first-class
continuations, and one that doesn't; and compare them (both performance
and ease of implementation).

I don't know how relevant to performance it would be that we almost
never see first-class continuations being leveraged directly in users'
code (outside of the implementation of a Scheme itself), and how that
might have affected priorities in the Scheme implementation.  The
implementor of a particular Scheme could say.

[Laurent]

Hendrik,

There is also the all too often forgotten iterative deepening depth-first search algorithm:

https://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

which has the advantages of both, at a very small cost in search time compared to doing depth-first search with the right cut-off depth bound from the start.

There are several other considerations to ponder regarding which algorithm is the right one (backward model, state size, duplicate checking, cost of continuations, size growth of the search tree, etc.), but I'll abstain for now unless you want more details.