लिस्प में दो नोड्स के बीच सबसे लंबा रास्ता कैसे खोजें?

Question

मुझे एक लिस्प फ़ंक्शन प्रोग्राम करने की आवश्यकता है जो दो नोड्स के बीच सबसे लंबा पथ पाता है, बिना किसी नोड्स की समीक्षा किए। हालांकि, अगर प्रारंभ और अंत नोड समान हैं, तो इस नोड को फिर से देखा जा सकता है। फ़ंक्शन को रिकर्सिव और गहराई-प्रथम-खोज दोनों होना चाहिए।

मैं इसे घंटों तक प्राप्त करने की कोशिश कर रहा हूं, और समाधान के साथ नहीं आ सकता। मैं फ़ंक्शन की सामान्य रूपरेखा जानता हूं, लेकिन इसे सही ढंग से प्रोग्राम नहीं कर सकता। में कुछ कोड और ज्यादातर छद्म कोड:

(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)), जहां पहले आइटम नोड है, तरह दिखता है और बाकी सब कुछ अपने पड़ोसियों (जैसे नोड एक है पड़ोसी बी, नोड बी पड़ोसी सी है)।

हां, यह होमवर्क के लिए है, इसलिए यदि आप समाधान पोस्ट करने में सहज महसूस नहीं करते हैं, या इसके किसी भी हिस्से में नहीं हैं। मैं लिस्प के लिए बस नया हूं और एक सभ्य शुरुआत पाने के लिए कुछ सुझाव/सहायता चाहूंगा।

धन्यवाद

संपादित करें: ठीक है, ज्यादातर मैं मिल सकता है यह था:

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

यह सही समाधान का उत्पादन को छोड़कर जब आरंभ और अंत नोड एक ही हैं। मैं यह नहीं समझ सकता कि खोज कैसे करें जब भी वे वही हों।

Answer 1

मैं तुम्हें तीन मामलों की जांच करने की जरूरत है लगता है: -> इस पथ

कोई अन्य विकल्प नहीं लौटने -

1. अंत तक पहुँच> वापसी
2. शून्य पड़ोसियों के सबसे लंबे समय तक रास्ता ढूंढने

कोड रूपरेखा:

(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

मैं एच आवे ने पॉल ग्राहम की पुस्तक: अंसी कॉमन लिस्प से इस एल्गोरिदम को याद किया। पुस्तक से एक अभ्यास के समाधान का लिंक यहां दिया गया है। यह आपकी मदद करनी चाहिए।

Solution