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))))))

最后，这里是“成本”和“更便宜”函数：

(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 以及额外的参数 <代码>更便宜。）

将给出正确的结果：

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 函数中检查邻居（这也意味着您必须传递节点列表）。