如何找到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中兩個節點之間最長的路徑？

回答

相關問題