recursion - 递归最佳优先搜索并找到最佳路径

Question

在递归最佳优先搜索中，我将如何修改它，以便能够追溯路线？

我是否需要一个数据结构来跟踪在上次递归中断后哪些节点被展开？

我已经在 LISP 和 RBFS 本身中实现了启发式和辅助功能(图形解析器、距离计算)。现在，为了打印最佳路径，我有一个每个递归步骤的所有返回值(结果)的列表。

参见 RBFS - Recursive Best-First Search Algorithm (PDF, slide 4) .

我的 LISP 代码:

(defun rbfs (state cost f-limit goal)
  (let ((node (first state))
        (f (second state)))
    (if (equal node goal)
        (list node cost)
        (let ((successors
               (loop
                   :for city :in (expand node)
                   :collect (list city (max (+ cost (getdistance city node)
                                               (getlineardistance city goal)) f))
                   :into successors
                   :finally (sort successors #'my-comparator)))
              (result (list)))
          (if (< (length successors) 2)
              (list fail inf)
              (loop
                 :for best :=  (first successors)
                 :and alternative :=  (second successors)
                 :if (> (second best) f-limit) :do (list fail (second best))
                 :else :if (not (equal node fail) )
                 :do (list node cost)
                 :collect (rbfs best
                                (+ cost (getdistance (first best) node) )
                                (min f-limit (second alternative) ) goal)))))))

现在，这段代码的问题是递归永远不会展开。使用 (trace rbfs) 我得到类似第 1、2、3、4、5 次调用的信息，然后它再次重复第 5 次调用。

所以真正的问题是如何在循环中打破递归;)

Answer 1

你能这样写你的代码吗(在 common-lisp 中):

(defun rbfs (<your-arguments> lst)
    (let ((city (car lst)))
    (append lst (get-successors city))
    (cond ((null lst) NIL)
          ((not (null (goal-test city))) (<return the path>))
          (t (rbfs <your-arguments> (sort (cdr lst)))))))

(defun get-successors (city)
    (<expand the city node here and returning a list>))

(defun goal-test (city)
    (<judge using your h(n) function>))

这是您想要的形式吗？而且您可能不需要其他数据结构，因为您需要的只是在递归中传递参数。