7

我需要编写一个 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)))

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

4

2 回答 2

3

我从 Paul Graham 的书：Ansi Common Lisp 中记住了这个算法。这是书中一个练习的解决方案的链接。这应该可以帮助你。

解决方案

于 2010-10-18T13:29:59.230 回答
2

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

  1. 到达终点 -> 返回此路径
  2. 没有更多选择 -> 返回 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))))))
于 2010-10-15T23:55:07.617 回答