Lisp - 爬山算法

Question

好的，我有一个Lisp实现的BFS（广度优先搜索），我想把它转换成做爬山算法。

这是我的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 函数来扩展最接近的节点，但我似乎无法编写一个确定哪个节点最接近的函数。

谢谢帮助！

- snivek

---

我认为函数（输入、输出、算法）和数据类型的文档非常好。你觉得呢？例如，我不知道“list of list of start”是什么意思，以及为什么它只有两个而不是五个列表函数应用程序。等等。 - Rainer Joswig

使用单向链表实现的队列末尾添加元素是不好的。 - Rainer Joswig

抱歉代码有点模糊，我添加了一些注释来澄清它。 - snivek

Answer 1

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

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

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

- Rainer Joswig