dfs-root-restart.sps

#!r6rs

(import (rnrs (6)))

;; Performs a depth-first search without a get-previous-state function, by enumerating
;; the paths and restarting at the root for each new path.
;; Requires only the memory of the current state and a O(depth-max) memory of other things.
;; num-actions: positive-integer?
;;   Number of children per node.
;; get-start-state: none/c -> state?
;;   Returns a new starting state at the root.
;; get-next-state: state? action? -> state?
;;   Returns the next state given the current state and action.
;; visit-state: state? -> void/c
;;   Visits the state. Called only on the first visit to the current *node* (not state).
(define (root-restart-dfs num-actions depth-max get-start-state get-next-state visit-state)
  (let root-loop ((last-path '()))
    (define state (get-start-state))
    (define new-path
      (let loop ((depth 0) (remaining-path last-path))
        (cond ((= depth depth-max)
               (visit-state state)
               '())
              (else
               (when (null? remaining-path)
                 ; First time this node is visited.
                 (visit-state state))
               (let-values (((act new-remaining-path)
                             (if (null? remaining-path)
                                 (values 0 '())
                                 (values (car remaining-path) (cdr remaining-path)))))
                 (set! state (get-next-state state act))
                 (let ((new-path (loop (+ depth 1) new-remaining-path)))
                   (if (null? new-path)
                       ; The child tells us it was the last action,
                       ; so we try to increase the action number at the current node
                       (if (= (+ act 1) num-actions)
                           ; This is also the last action at the current node,
                           ; so signal it to the parent by return nil.
                           '()
                           ; Not the last action at the current node, so just add 1.
                           (cons (+ act 1) new-path))
                       ; Else, keep the same action in this node.
                       (cons act new-path))))))))
    (unless (null? new-path)
      (root-loop new-path))))

(root-restart-dfs
 3 3
 ; get-start-state
 (lambda ()
   '())
 ; get-next-state
 (lambda (state act)
   (cons act state))
 ; visit-state
 (lambda (state)
   (display (reverse state))
   (newline)))

This outputs:

{0}
{0 0}
{0 0 0}
{0 0 1}
{0 0 2}
{0 1}
{0 1 0}
{0 1 1}
{0 1 2}
{0 2}
{0 2 0}
{0 2 1}
{0 2 2}
{1}
{1 0}
{1 0 0}
{1 0 1}
{1 0 2}
{1 1}
{1 1 0}
{1 1 1}
{1 1 2}
{1 2}
{1 2 0}
{1 2 1}
{1 2 2}
{2}
{2 0}
{2 0 0}
{2 0 1}
{2 0 2}
{2 1}
{2 1 0}
{2 1 1}
{2 1 2}
{2 2}
{2 2 0}
{2 2 1}
{2 2 2}