Lisp'deki iki düğüm arasındaki en uzun yol nasıl bulunur?

Question

Herhangi bir düğüm yeniden incelemeden iki düğüm arasındaki en uzun yolu bulan bir Lisp işlevi programlamam gerekir. Yine de, başlangıç ​​ve bitiş düğümü aynıysa, bu düğüm yeniden gözden geçirilebilir. Fonksiyonun hem özyinelemeli hem de derinlemesine ilk arama olması gerekir.

Saatlerdir bunu yapmaya çalışıyorum ve bir çözüm bulamıyorum. Fonksiyonun genel hatlarını biliyorum, ancak doğru şekilde programlayamıyorum. Bazı kod ve çoğunlukla sözde kod:

(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)))) 

net ilk öğe düğümdür '((ab) (bc)), gibi görünür ve her şeyi komşuları (örneğin düğüm bir sahiptir komşu b, düğüm b komşusu var c).

Evet, bu ev ödevi için uygun bir çözüm veya herhangi bir parçasını rahat hissetmiyorsanız, yapmayın. Ben sadece Lisp için yeni ve iyi bir başlangıç ​​elde etmek için bazı ipuçları/yardım isterim.

Teşekkür

Düzenleme: Eh, ben alabilir en şuydu:

(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))) 

Bu başlangıç ​​ve bitiş düğümü aynı olduğunda hariç doğru çözümler üretir. Aynı oldukları zaman bile nasıl arama yapılacağını anlayamıyorum.

Answer 1

senden üç vaka kontrol etmek gerek: - Bu yolu

başka seçenek dönmek> -

1. sonuna ulaşıldığında
2. nil> dönüşü komşularının en uzun yolu bulmak

Kod açıklaması:

(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)))))) 

Answer 2

Ben h ave bu algoritmayı Paul Graham'ın kitabından hatırladı: Ansi Common Lisp. İşte kitaptan bir alıştırma çözümünün bağlantısı. Bu sana yardım etmeli.

Solution