3

我正在尝试修改现有的爬山函数，该函数采用两个节点名称（例如 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))))
4

1 回答 1

2

我不太确定，这里有什么问题。在您的中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（这也意味着您必须传递节点列表）。

于 2011-10-11T21:31:46.120 回答