Comment trouver le chemin le plus long entre deux nœuds dans Lisp?

Question

J'ai besoin de programmer une fonction Lisp qui trouve le chemin le plus long entre deux nœuds, sans revoir les nœuds. Cependant, si les nœuds de début et de fin sont les mêmes, ce nœud peut être revisité. La fonction doit être à la fois récursive et profondeur-première-recherche.

J'ai essayé d'y arriver pendant des heures et je n'arrive pas à trouver une solution. Je connais les grandes lignes de la fonction, mais je ne peux pas la programmer correctement. Dans certains code et la plupart du temps 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)))) 

Le filet ressemble à quelque chose comme « ((ab) (bc)), où le premier élément est le nœud, et tout le reste est ses voisins (par exemple, noeud un a voisin b, le noeud b a le voisin c).

Oui, c'est pour les devoirs, donc si vous ne vous sentez pas à l'aise de poster une solution, ou une partie de celle-ci, ne le faites pas. Je suis juste nouveau à Lisp et voudrais quelques conseils/aide pour commencer décemment.

Merci

Edit: Eh bien, le plus que je pouvais obtenir était le suivant:

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

Il produit des solutions correctes, sauf si le début et le noeud final sont les mêmes. Je n'arrive pas à comprendre comment effectuer une recherche, même si elles sont identiques.

Answer 1

Je pense que vous devez vérifier trois cas:

1. atteint la fin -> retourner ce chemin
2. pas plus de choix -> retour nul
3. trouver le plus long chemin de voisins

Code:

(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 se souvient de cet algorithme tiré du livre de Paul Graham: Ansi Common Lisp. Voici le lien de la solution d'un exercice du livre. Cela devrait vous aider.

Solution