3

好的，我有一个 BFS 的 Lisp 实现，我正在尝试将其转换为爬山搜索。

这是我的 BFS 代码的样子：

; The list of lists is the queue that we pass BFS.  the first entry and 
; every other entry in the queue is a list.  BFS uses each of these lists and 
; the path to search.  

(defun shortest-path (start end net)   
  (BFS end (list (list start)) net))

;We pass BFS the end node, a queue containing the starting node and the graph 
;being searched(net)   

(defun BFS (end queue net)
  (if (null queue) ;if the queue is empty BFS has not found a path so exit
      nil
      (expand-queue end (car queue) (cdr queue) net)))

(defun expand-queue (end path queue net)
  (let ((node (car path)))
    (if (eql node end)   ; If the current node is the goal node then flip the path
                         ; and return that as the answer
        (reverse path)
        ; otherwise preform a new BFS search by appending the rest of 
        ; the current queue to the result of the new-paths function
        (BFS end (append queue (new-paths path node net)) net))))

; mapcar is called once for each member of the list new-paths is passed
; the results of this are collected into a list
(defun new-paths (path node net)
  (mapcar #'(lambda (n) (cons n path))
         (cdr (assoc node net))))

现在，我知道我需要扩展似乎最接近目标状态的节点，而不是像在 BFS 中那样总是扩展左节点。
我使用的图表如下所示：

(a (b 3) (c 1))  
(b (a 3) (d 1))

我有一个转换函数可以使它与上述 BFS 实现一起工作，但现在我需要使用这种图形格式将其转换为爬山。

我只是不确定从哪里开始，并且一直在尝试无济于事。我知道我主要需要更改expand-queue函数以扩展最近的节点，但我似乎无法制作一个函数来确定哪个节点最近。

谢谢您的帮助！

4

1 回答 1

0

将内容附加到列表的末尾是错误的。这是列表中最昂贵的操作。整个列表被复制，然后附加另一个列表。您在递归过程中使用它，这意味着每次扩展节点以创建新路径时都会完成。

如果您将项目放在队列中，则需要查看执行此操作的顺序。在广度优先的情况下，在进入下一个级别之前，先访问一个级别中的每个节点。爬山需要您使用加权函数对“最佳”候选者进行排序。因此，您需要某种函数从当前节点和下一个候选节点计算数值。然后您需要对候选者进行排序并首先展开“最佳”节点。对于 LIFO（后进先出）队列，这意味着最有希望的节点需要最后推送，以便它成为第一个被扩展的节点。请注意，LIFO 队列非常适合单链表。FIFO（先进先出）并非如此。

计算机科学的一个典型思想是数据抽象。如果 LIFO QUEUE 是这样的数据结构，您需要定义 MAKE-LIFO-QUEUE、EMPTY-QUEUE-P 等函数，然后使用这些函数代替 LIST、NULL 等，它们的目的是数据结构更清晰。这会使您的代码更长，但是由于 Lisp 列表是通用的并且可以（ab-）用于各种使用场景，因此仅查看列表操作并不能清楚地说明它们的意图。这对于更复杂的图形算法尤其重要。

于 2011-04-30T10:38:50.770 回答