Wie finde ich den längsten Pfad zwischen zwei Knoten in Lisp?

Question

Ich muss eine Lisp-Funktion programmieren, die den längsten Pfad zwischen zwei Knoten findet, ohne Knoten erneut zu besuchen. Wenn jedoch Start- und Endknoten gleich sind, kann dieser Knoten erneut besucht werden. Die Funktion muss sowohl rekursive als auch Tiefensuche sein.

Ich habe versucht, dafür stundenlang zu bekommen, und kann keine Lösung finden. Ich kenne die allgemeine Gliederung der Funktion, kann sie aber nicht richtig programmieren. In einigen Code und meist pseudo-Code:

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

Das Netz sieht so etwas wie ‚((ab) (bc)), wobei das erste Element ist der Knoten, und alles andere ist seine Nachbarn (zB Knoten a hat Nachbar b, Knoten b hat Nachbar c).

Ja, das ist für die Hausaufgaben, also wenn Sie sich nicht wohl fühlen, eine Lösung oder einen Teil davon zu veröffentlichen, tun Sie es nicht. Ich bin nur neu bei Lisp und hätte gerne ein paar Tipps/Hilfe um einen guten Start zu bekommen.

Dank

Edit: Nun, das war ich diese bekommen konnte:

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

Es richtige Lösungen produziert, mit der Ausnahme, wenn die Start- und End-Knoten ist gleich. Ich kann nicht herausfinden, wie man eine Suche durchführt, auch wenn sie gleich sind.

Answer 1

Ich denke, man drei Fälle überprüfen müssen:

1. Ende erreicht -> Rückkehr diesen Weg
2. nicht mehr Auswahl -> Rückkehr null
3. finden längste Weg der Nachbarn

Code Umriss:

(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

I h Ave erinnerte sich an diesen Algorithmus aus Paul Grahams Buch: Ansi Common Lisp. Hier ist die Verknüpfung der Lösung einer Übung aus Buch. Dies sollte dir helfen.

Solution