चक्र

Question

के साथ निर्देशित ग्राफ़ में सभी पथ ढूंढना मैं एक समस्या पर काम कर रहा हूं जिसके लिए निर्देशित ग्राफ में दो नोड्स के बीच सभी पथ ढूंढने की आवश्यकता है। ग्राफ में चक्र हो सकते हैं।

ध्यान दें कि यह विशेष कार्यान्वयन दृष्टिकोण एक पुनरावर्तक डीएफएस है।

• BFS एक तरह से बड़े करीने से नोड्स के बीच पथ का रिश्ते इस तरह का प्रबंधन करने के लिए प्रतीत नहीं होता है -

  कई दृष्टिकोण मैं माना जाता है इस प्रकार हैं।

• मुझे डीएफएस रिकर्सिव एल्गोरिदम के लिए एक आसान तंत्र नहीं दिख रहा है जब टर्मिंग नोड पाया जाता है। (अगर मैं शायद एक मोनैड प्रकार की चीज को लागू करता हूं तो यह काफी संभव हो सकता है)।

• एक ग्राफ-पेरेंट दिनचर्या बनाना। मौजूदा कोड में यह मंथन की अच्छी मात्रा (& बग) जोड़ देगा।

Abstractly, क्या होने की जरूरत है एक पेड़, उत्पन्न करने रूट के रूप में प्रारंभ नोड के साथ की जरूरत है, और सभी लीफ़्स समाप्त नोड्स रहे हैं। पत्ती से रूट तक प्रत्येक मार्ग एक कानूनी मार्ग है। यही एक रिकर्सिव डीएफएस पता लगाएगा।

मुझे यकीन है कि यह यहां किया जा सकता है, लेकिन मुझे नहीं लगता कि यह कैसे करना है।

मैंने इस एल्गोरिदम के लिए एक प्रोटोकॉल परिभाषित किया है जहां ग्राफ-इक्वाल और ग्राफ-नेक्स को मनमानी वस्तुओं के लिए परिभाषित किया जा सकता है।

डीबग नोड प्रकार एक खोज-NODE है, और इसमें डेटा एक्सेसर खोज-नोडे-डेटा है।

(defun all-paths (start end) 
    (let ((stack (list start)) 
     (mark-list (list start)) ;I've chosen to hold marking information local to all-paths, instead of marking the objects themselves. 
     (all-path-list '()))  ; Not used yet, using debug statements to think about the problem 
    (do () ;; intializing no variables 
    ;; While Stack still has elements 
     ((not stack))   
     (let ((item (pop stack))) 
    ;; I'm looking at the item. 
    (format t "I: ~a~%" (search-node-data item)) 
    (cond ((graph-equal item end) 
      (format t "*Q: ~a~%" (loop for var in stack collect (search-node-data var))) 
      ;;Unmark the terminal node so we can view it it next time. 
      (setf mark-list (remove item mark-list)))) 

     (loop for next in (graph-next item) 
      do   
      (cond ((not (in next mark-list :test #'graph-equal)) 
        ;; mark the node 
        (push next mark-list) 
        ;;Put it on the stack 
        (push next stack)))))))) 

Answer 1

एक एल्गोरिथ्म है कि एक ग्राफ (यहां तक ​​कि जब वहाँ चक्र हैं) परिमित समय में किनारों की वर्णमाला से अधिक नियमित अभिव्यक्ति के रूप में में सभी रास्तों लौट सकते हैं (एक परिमित ग्राफ कल्पना करते हुए) के लिए A Very General Method for Computing Shortest Paths देखें।

Answer 2

आपको नोड्स के साथ पथ सूची (mark-list) पास करने की आवश्यकता है, क्योंकि यह राज्य का हिस्सा है। मैंने इस कोड में path का नाम बदल दिया है:

(defun all-paths (start end) 
    (let ((stack (list '(start (start)))) ; list of (node path) elements 
     (all-path-list '())) 
    (do () 
     ((not stack))   
     (let ((item (pop stack))) 
     (let ((node (first item)) 
       (path (second item))) 
      (format t "I: ~a~%" (search-node-data node)) 
      (cond ((graph-equal node end) 
       (format t "*Q: ~a~%" 
         (loop for var in path 
           collect (search-node-data var))))) 
      (loop for next in (graph-next node) 
       do   
       (cond ((not (in next path :test #'graph-equal)) 
         (push (list next (cons next path)) stack)))))))))