Lisp中如何找到两个节点之间的最长路径？

Question

我需要编写一个 Lisp 函数来查找两个节点之间的最长路径，而无需重新访问任何节点。但是，如果起始节点和结束节点相同，则可以重新访问该节点。该函数需要递归和深度优先搜索。

我已经尝试了几个小时来解决这个问题，但无法想出解决方案。我知道该功能的大致轮廓，但无法正确编程。在一些代码中，大部分是伪代码：

(defun longest-path (start end net &optional (current-path nil))  
    (cond ((and (eql start end)
                (not (null current-path)))
          (list start))
          (t
           (find neighbors of start/node)
           (remove any previously traveled neighbors to avoid loop)
           (call longest-path on these neighbors)
           (check to see which of these correct paths is longest))))

网络看起来像 '((ab) (bc)) ，其中第一项是节点，其他所有内容都是它的邻居（例如，节点 a 有邻居 b，节点 b 有邻居c).

是的，这是为了家庭作业，所以如果您不愿意发布解决方案或其任何部分，请不要发布。我是 Lisp 的新手，想要一些提示/帮助来获得一个良好的开始。

谢谢

编辑：嗯，我能得到的最多的是：

(defun longest-path (start end net &optional (current-path nil))
  (cond ((and (eql start end)
              (not (null current-path)))
         (list start))
        (t
         (push start current-path)
         (let ((neighbors (cdr (assoc start net))))
           (let ((new-neighbors (set-difference neighbors current-path)))
             (let ((paths (mapcar #'(lambda (node)
                                      (longest-path node end net current-path))
                            new-neighbors)))
               (let ((longest (longest paths)))
                 (if longest
                     (cons start longest)
                   nil))))))))


(defun longest (lst)
  (do ((l lst (cdr l))
       (r nil (if (> (length (car l)) (length r))
                  (car l)
                r)))
      ((null l) r)))

它会产生正确的解决方案，除非起始节点和结束节点相同。即使它们相同，我也不知道如何执行搜索。

Answer 1

我记得 Paul Graham 的书《Ansi Common Lisp》中的这个算法。这是书中一项练习的解决方案的链接。这应该对你有帮助。

解决方案

Answer 2

我认为你需要检查三种情况：

1. 结束 ->返回此路径
2. 不再有选择 -> return nil
3. 找到邻居的最长路径

代码概要：

(defun longest-path (node end-node net current-path)
  (cond ((eql node end-node)
         (or current-path (list node end-node)))
        ((null (node-neighbors node net))
         ())
        (t
         (let* ((neighbors (node-neighbors node net))
                (not-visited-neighbors (set-difference neighbors current-path))
                (paths (mapcar (lambda (next-node)
                                 (longest-path next-node end-node net
                                               (cons node current-path)))
                               not-visited-neighbors)))
           (first (sort paths #'> :key #'length))))))