search - Lisp - 修改 A* 以检查最佳成本，接收目标节点列表

Question

我正在尝试修改现有的爬山函数，它采用两个节点名称(例如 A 和 E)，并且有一个递归使用的可选参数(队列)。我试图定义一个“更便宜”的函数来评估一条路径是否比另一条路径便宜。此外，我试图传递一个目标节点列表，而不是一个目标节点，该函数在到达其中一个节点后停止评估。

问题是我的函数除了我输入的起始节点和一个空列表外不会返回任何东西。

这是我的网络/图表和相关成本:

(setf (get 's 'coordinates) '(0 3)
      (get 'a 'coordinates) '(4 6)
      (get 'b 'coordinates) '(7 6)
      (get 'c 'coordinates) '(11 9)
      (get 'd 'coordinates) '(2 0)
      (get 'e 'coordinates) '(9 2)
      (get 'f 'coordinates) '(11 3))


(setf (get 's 'cost) 0
      (get 'a 'cost) 16
      (get 'b 'cost) 4
      (get 'c 'cost) 10
      (get 'd 'cost) 5
      (get 'e 'cost) 12
      (get 'f 'cost) 14)

这是我修改后的爬山函数:

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'(lambda (p1 p2)
                                                      (cheaper p1 p2 
                                                               finish)))
                                            (rest queue))))))

最后，这里是“cost”和“cheaper”函数:

(defun cost (path)
  (apply '+ (mapcar #'(lambda (x) (get x 'cost)) path)))


(defun cheaper (p1 p2)
  (< (cost p1)
     (cost p2)))  

编辑:抱歉，这里是“扩展”:

(defun extend (path)
  (print (reverse path))
  (mapcar #'(lambda (new-node) (cons new-node path))
          (remove-if #'(lambda (neighbor) (member neighbor path))
                     (get (first path) 'neighbors))))

Answer 1

我不太确定，这里有什么问题。在您的 expand 中，使用了一个 neighbor 属性，您的问题中没有给出。如果为每个节点都定义了此属性，则您的代码有效。

假设每个节点都与另一个节点相邻，中间没有另一个节点(这是唯一对您的数据有意义的选项，因为替代方案，即只制作相切节点(即 +/-1 的节点一个或两个坐标)邻居，在您的示例中根本不会产生任何邻居):

(setf (get 's 'neighbors) '(a d)
      (get 'a 'neighbors) '(s b d)
      (get 'b 'neighbors) '(a c e)
      (get 'c 'neighbors) '(b)
      (get 'd 'neighbors) '(s a e)
      (get 'e 'neighbors) '(b d f)
      (get 'f 'neighbors) '(e))

(defun hill-climb (start finish &optional (queue (list (list start))))
  (cond ((endp queue) nil)
        ((member (first (first queue)) finish)
         (reverse (first queue)))
        (t (hill-climb start finish (append (sort (extend (first queue))
                                                  #'cheaper)
                                            (rest queue))))))

(缺失的部分与您的帖子中的相同。只有细微的调整，例如删除 lambda，以及 cheaper 的额外参数。)

将给出正确的结果:

CL-USER> (hill-climb 's '(b))

(S) 
(S D) 
(S D E) 
(S D E B)
CL-USER> (hill-climb 's '(b d))

(S) 
(S D)

如果您不能引入新属性，则必须在 expand 函数中检查邻居(这也意味着您必须传递节点列表)。