常见的lisp中的迭代加深

Question

我已经编写了一个迭代加深算法,除非我添加循环检查,否则算法会返回一个比它应该更深的解决方案.但是当我没有检查周期时它确实可以正常工作,但这需要很长时间.任何人都可以发现这个bug吗？

(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
          ;; when i remove the next line, it works correctly
          (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)
  "Iterative deepening search"
  (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)))) ;solve problem up to cutoff
        (if (null  solution) 
            (incf cutoff);if solution is not found, increment the depth
            (return solution))))))

(defun visited-p (node table)
  "Checks if state in node was visited before by checking
if it exists in the table"
  (nth-value 1 (gethash (node-state node) table)))

编辑:这是扩展功能

(defun expand (node actions)
  "Expands a node, returns a list of the new nodes"
  (remove-if #'null (apply-actions node actions)));apply all actions on all nodes

(defun apply-actions (node actions)
  "Applies all actions to a state, returns a list of new states"
  (mapcan #'(lambda (action) 
              (mapcar #'(lambda (tile) (funcall action tile node))
                     (node-state node)))
          actions))

这是其中一项行动,除了微小的变化外,它们都是相同的

(defun slide-right (tile node)
  "slide the tile one cell to the right. returns nil if not possible, 
  otherwise returns a node with the new state"
  (when (can-slide-right-p tile (node-state node));if can slide right
      (and visualize (format t "~%slide ~A to the right" (tile-label tile)))
      (let*  ((newstate (mapcar #'copy-tile (node-state node)));copy the current state
             (depth (node-depth node))
             (newcol (incf (tile-col (find tile newstate :test #'equalp))));update state
             (cost (1+ (node-cost node))))
        (make-node :state newstate ;create new node with the new state
                   :parent node 
                   :depth (1+ depth) 
                   :action (concatenate 'string
                                        "slide "
                                        (tile-label tile)
                                        " right" )
                   :cost cost))))

谓词

(defun can-slide-right-p (tile state)
  "returns T if the specified tile can be sled one cell to the right"
  (let  ((row (tile-row tile)) 
        (end (+ (tile-col tile) (tile-length tile))) ;col at which tile ends after being sled
        (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)
  "returns T if the specified tile spans the specified cell"
  (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)
  "Tests if the specified horizontal tile spans the specified cell"
  (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)
  "Tests if the specified vertical tile spans the specified cell"
  (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)))))

Answer 1

当通向目标的第一路径比包括相同状态的任何其他较短路径长时,具有周期检测的有限深度优先搜索可以返回更长的路径.

设D为目标状态:

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

如果深度限制为2,则首先访问顶部分支,将访问B和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)))))