recursion - CLISP dfs 获取程序堆栈溢出

Question

我是 Lisp 的新手，我正在尝试使用简单的 dfs(深度优先搜索)解决一个 8 难题。但是我遇到程序堆栈溢出。我的代码:

(setq used (list))

(defun is_used (state lst) 
  (cond
    ((null lst)   nil)
    ((equalp (car lst) state)   t) 
    (t   (is_used state (cdr lst)))))

(defun move (lst direction)
  (let* ( (zero (find_zero lst)) 
          (row  (floor zero 3)) 
          (col  (mod zero 3)) 
          (res  (copy-list lst)))
     (cond
        ((eq direction 'L) 
           (if (> col 0) 
               (rotatef (elt res zero) (elt res (- zero 1)))))
        ((eq direction 'R) 
           (if (< col 2) 
               (rotatef (elt res zero) (elt res (+ zero 1)))))
        ((eq direction 'U) 
           (if (> row 0) 
               (rotatef (elt res zero) (elt res (- zero 3)))))
        ((eq direction 'D) 
           (if (< row 2) 
               (rotatef (elt res zero) (elt res (+ zero 3))))))
     (if (equalp res lst) 
         (return-from move nil))
     (return-from move res))
  nil)

(defun dfs (cur d prev)
  ; (write (length used))
  ; (terpri)
  (push cur used)
  (let* ((ways '(L R U D)))
    (loop for dir in ways
          do (if (move cur dir)
                 (if (not (is_used (move cur dir) used))
                     (dfs (move cur dir) (+ d 1) cur))))))

state 这里是 9 个原子的列表。

在未注释 (write (length used)) 的情况下，它会打印 723 - 在堆栈溢出发生之前 used 中的项目数。

现在，在解决 8-puzzle 之前，我只想遍历所有可能的状态(恰好有 9!/2 = 181440 种可能的状态)。当然，这可能需要一些时间，但是我怎样才能避免这里的堆栈溢出呢？

Answer 1

这是一些 AI 编程书籍中解释的典型问题。如果您需要搜索大量/无限数量的状态，则不应使用递归。 CL 中的递归受堆栈深度的限制。一些实现可以优化尾递归 - 但随后您需要构建您的代码，以便它是尾递归的。

通常，该数据结构将称为议程。它让各州仍然有待探索。如果您查看一个州，就会将所有州从那里进行探索推上议程。确保议程以某种方式排序(这可能决定它是深度优先还是广度优先)。然后从议程中取出下一个状态并检查它。如果达到目标，那么你就完成了。如果在找到目标之前议程是空的，那么就没有解决方案。否则循环...