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.Lisp'deki iki düğüm arasındaki en uzun yol nasıl bulunur?
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.
Merhaba, yardımlarınız için teşekkürler. Kodunuzu denedim, ancak doğru çözümleri almadım. Örneğin, eğer denediysem (en uzun yol 'a' c '((a b) (b c)) sıfır) Ben alırdım (B A). Bunun yerine, (A B C) almalıyım. – Jay