我编写了一个迭代加深算法，当我添加循环检查时，算法返回的解比应该的更深。但当我不检查循环时，它确实能正确工作，但耗时太长。谁能帮我找出这个错误？

(defun rec-depth-limited (problem node cutoff closed)  (if (= cutoff 0)    (if (funcall (problem-goalp problem) node)          node)    (if (visited-p node closed)        nil        (progn          ;; 当我删除下一行时，它能正确工作          (setf (gethash (node-state node) closed) t)          (loop for child in (expand node (problem-actions problem)) do            (let ((result (rec-depth-limited problem child (1- cutoff) closed)))                (if result                    (return result))))))))(defun iterative-deepening (problem)  "迭代加深搜索"  (let ((cutoff 0))    (loop      (format t "~%cut-off: ~A" cutoff)      (let ((solution (rec-depth-limited                             problem                             (make-node :state (problem-state problem))                              cutoff                              (make-hash-table :test #'equalp)))) ;解决问题直到cutoff        (if (null  solution)             (incf cutoff);如果没有找到解，增加深度            (return solution))))))(defun visited-p (node table)  "检查节点中的状态是否之前被访问过，通过检查它是否存在于表中"  (nth-value 1 (gethash (node-state node) table)))

编辑：这是expand函数

(defun expand (node actions)  "扩展一个节点，返回新节点的列表"  (remove-if #'null (apply-actions node actions)));对所有节点应用所有动作(defun apply-actions (node actions)  "对一个状态应用所有动作，返回新状态的列表"  (mapcan #'(lambda (action)               (mapcar #'(lambda (tile) (funcall action tile node))                     (node-state node)))          actions))

这是一个动作，它们除了细微的变化外都是相同的

(defun slide-right (tile node)  "将瓷砖向右滑动一个单元格。如果不可能，返回nil，否则返回一个带有新状态的节点"  (when (can-slide-right-p tile (node-state node));如果可以向右滑动      (and visualize (format t "~%slide ~A to the right" (tile-label tile)))      (let*  ((newstate (mapcar #'copy-tile (node-state node)));复制当前状态             (depth (node-depth node))             (newcol (incf (tile-col (find tile newstate :test #'equalp))));更新状态             (cost (1+ (node-cost node))))        (make-node :state newstate ;创建带有新状态的新节点                   :parent node                    :depth (1+ depth)                    :action (concatenate 'string                                        "slide "                                        (tile-label tile)                                        " right" )                   :cost cost))))

谓词

(defun can-slide-right-p (tile state)  "如果指定的瓷砖可以向右滑动一个单元格，则返回T"  (let  ((row (tile-row tile))         (end (+ (tile-col tile) (tile-length tile))) ;瓷砖滑动后结束的列        (orient (tile-orientation tile)))    (and (equal orient 'H)         (or (tile-is-mouse tile) (< end *board-w*))         (empty-cell-p row end state))))(defun spans-cell-p (row col tile)  "如果指定的瓷砖跨越指定的单元格，则返回T"  (if (equal (tile-orientation tile) 'H)      (horizontally-spans-cell-p row col tile)      (vertically-spans-cell-p row col tile)))(defun horizontally-spans-cell-p (row col tile)  "测试指定的水平瓷砖是否跨越指定的单元格"  (let ((tile-col (tile-col tile))        (tile-row (tile-row tile))        (tile-len (tile-length tile)))    (and (= tile-row row) (>= col tile-col) (< col (+ tile-col tile-len)))))(defun vertically-spans-cell-p (row col tile)  "测试指定的垂直瓷砖是否跨越指定的单元格"  (let  ((tile-col (tile-col tile))        (tile-row (tile-row tile))        (tile-len (tile-length tile)))    (and (= tile-col col) (>= row tile-row) (< row (+ tile-row tile-len)))))

回答：

带有循环检测的有限深度优先搜索可能会在第一个通向目标的路径比包含相同状态的任何其他较短路径更长时返回更长的路径。

设D为目标状态：

A -- B -- C -- D \  C -- D

深度限制为2时，如果首先访问上面的分支，B和C将被访问并保存到哈希表中。当访问下面的分支时，它不会扩展到C之后，因为C被标记为已访问。

一个可能的解决方案是将哈希值设置为找到该状态的最小深度。这使得状态在某个深度及以后被标记为已访问，但如果以更小的深度再次访问，它将有可能再次扩展。

(defun visited-p (node table)  (let ((visited-depth (gethash (node-state node) table)))    (and visited-depth         (>= (node-depth node) visited-depth))))(defun set-visited (node table)  (let ((visited-depth (gethash (node-state node) table)))    (setf (gethash (node-state node) table)          (if visited-depth              (min visited-depth (node-depth node))              (node-depth node)))))