Yönlendirilmiş bir grafikte tüm yolları bulma döngüleri

Question

Yönlendirilmiş bir grafikte iki düğüm arasındaki tüm yolları bulmayı gerektiren bir sorun üzerinde çalışıyorum. Grafikte döngü olabilir. Bu özel uygulama yaklaşımının yinelemeli bir DFS olduğuna dikkat edin.

• BFS düzgünce düğümler arasındaki pathing ilişkilerin bu tür yönetmek için bir yol var gibi görünmüyor - aşağıdaki gibi ben kabul ettik

  Çeşitli yaklaşımlardır.

• Sonlandırma düğümü bulunduğunda yolu geçmek için DFS yinelemeli algoritma için kolay bir mekanizma göremiyorum. (Belki bir monad şey türünü uygularsam yeterli olabilirdi).

• GRAPH-PARENT rutini oluşturma. Bu, mevcut koda iyi bir miktarlık (& hata) ekler.

Soyut ne olması gereken bir ağaç kökü olarak başlangıç ​​düğümle, oluşturulması gerekiyorsa, ve tüm yapraklar sonlandırma düğümleri vardır. Yapraktan köke giden her yol bir yasal yoldur. Yinelemeli bir DFS'nin izleyeceği şey budur.

Burada yapılabileceğine eminim ama nasıl yapılacağını tam olarak göremiyorum.

Bu algoritma için GRAPH-EQUAL ve GRAPH-NEXT'ın rasgele nesneler için tanımlanabildiği bir protokol tanımladım.

Hata ayıklama düğümü türü SEARCH-NODE'dur ve veri erişim aracı ARAMA-VERİ-VERİ'dir.

(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

(sonlu grafik varsayılarak) sınırlı zamanda kenarların alfabe boyunca düzenli ifadeler olarak bir grafik (devir olduğunda bile) tüm yolları dönebilir bir algoritma için A Very General Method for Computing Shortest Paths bakınız.

Answer 2

Yol listesinin (mark-list) düğümlerle birlikte iletilmesi gerekir, çünkü bu durum durumun bir parçasıdır. Bu kodda path olarak yeniden adlandırdım:

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