Мне нужно запрограммировать функцию 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)), где первый элемент - это узел, а все остальное - его соседи (например, узелa имеет соседа b, узел b имеет соседа c).
Да, это домашняя работа, поэтому, если вам неудобно публиковать решение или какую-либо его часть, не делайте этого.Я просто новичок в Лиспе и хотел бы получить несколько советов / помощи, чтобы получить достойное начало.
Спасибо
Редактировать: Ну, самое большее, что я мог получить, это:
(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)))
Он дает правильные решения, за исключением случаев, когда начальный и конечный узлы совпадают.Я не могу понять, как выполнить поиск, даже если они одинаковы.