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

我需要能编写发现两个节点之间的最长路径Lisp的功能，无需任何重温节点。但是，如果开始和结束节点相同，则可以重新访问此节点。该功能需要同时是递归和深度优先搜索。如何找到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）），其中第一项是节点，其他一切都是它的邻国（如节点的有邻居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)))

它产生正确的解决方案时，除起点和终点节点是相同的。即使他们是相同的，我也不知道如何执行搜索。

来源

2010-10-15 Jay

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

年底达到 - >返回这个路径
没有更多的选择 - >回零
发现邻居的最长路径

代码大纲：

(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-15 23:55:07

嗨，感谢您的帮助。我试过你的代码，但没有得到正确的解决方案。例如，如果我尝试了（最长路径'a'c'（（a b）（b c））nil），我会得到（B A）。相反，我应该得到（A B C）。 – Jay 2010-10-17 16:50:20

我h大卫从Paul Graham的书中回忆了这个算法：Ansi Common Lisp。这是书中一个练习解决方案的链接。这应该对你有所帮助。

Solution

来源

2010-10-18 13:29:59 asdr

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

回答

相关问题