¿Cómo encontrar el camino más largo entre dos nodos en Lisp?

Question

Necesito programar una función Lisp que encuentre la ruta más larga entre dos nodos, sin volver a visitar ningún nodo. Sin embargo, si el nodo de inicio y fin es el mismo, este nodo se puede volver a visitar. La función debe ser recursiva y búsqueda de profundidad en primer lugar.

He estado tratando de conseguir esto durante horas y no puedo encontrar una solución. Conozco el esquema general de la función, pero no puedo programarla correctamente. En un cierto código y en su mayoría pseudo-código:

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

La red se ve algo como '((ab) (bc)), donde el primer elemento es el nodo, y todo lo demás es sus vecinos (por ejemplo, el nodo A tiene vecino b, nodo b tiene vecino c).

Sí, esto es para tareas, por lo que si no se siente cómodo publicando una solución, o parte de ella, no lo haga. Soy nuevo para Lisp y me gustaría obtener algunos consejos/ayuda para comenzar decente.

Gracias

EDIT: Bueno, lo más que pude conseguir fue la siguiente:

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

Produce soluciones correctas, excepto cuando el inicio y el nodo final son los mismos. No puedo descifrar cómo realizar una búsqueda incluso cuando son iguales.

Answer 1

creo que es necesario comprobar tres casos:

1. ha llegado al final -> volver este camino
2. hay más opciones -> respuesta negativa
3. encontrar camino más largo de los vecinos

Esquema del código:

(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 recordó este algoritmo del libro de Paul Graham: Ansi Common Lisp. Aquí está el enlace de la solución de un ejercicio del libro. Esto debería ayudarte.

Solution