如何在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))))

网络看起来像'((a，b) ( b，c))，其中第一项是节点，其他所有东西都是它的邻居(例如，节点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。这是书中一个习题的解决方案的链接。这应该会对你有帮助。

Solution

Answer 2

我认为你需要检查三个案例：

1. end达到->返回此路径
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))))))