Re: [racket-users] continuations for search
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. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/CABNTSaG0QVorRohByDurLjU__2z%3DSgkCzOjz5C5Q9DYTVRZiwQ%40mail.gmail.com.
Re: [racket-users] continuations for search
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. -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/4ed3134c-54fd-5747-486d-c45ce93a99bb%40neilvandyke.org.
[racket-users] continuations for search
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 -- You received this message because you are subscribed to the Google Groups "Racket Users" group. To unsubscribe from this group and stop receiving emails from it, send an email to racket-users+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/racket-users/20190912002933.4dcep2dqcsjgiib2%40topoi.pooq.com.