Tìm tất cả các đường dẫn trong biểu đồ được chỉ dẫn bằng các chu kỳ

Question

Tôi đang nghiên cứu một vấn đề đòi hỏi phải tìm tất cả các đường dẫn giữa hai nút trong biểu đồ được chỉ dẫn. Biểu đồ có thể có chu kỳ.

Lưu ý rằng phương pháp triển khai cụ thể này là một DFS lặp lại.

Một số cách tiếp cận tôi đã xem xét như sau -

• BFS không xuất hiện để có một cách để gọn gàng quản lý loại này của mối quan hệ pathing giữa các nút.

• Tôi không thấy cơ chế dễ dàng cho thuật toán đệ quy DFS để vượt qua đường dẫn khi tìm thấy nút chấm dứt. (Có khả năng nó có thể được thực hiện, nếu tôi thực hiện một loại có lẽ đơn nguyên của điều).

• Tạo thói quen GRAPH-PARENT. Điều đó sẽ thêm một số lượng khá churn (& lỗi) trong mã hiện có.

Tóm lại, cần phải tạo ra một cây, với nút bắt đầu là gốc và tất cả các lá là nút chấm dứt. Mỗi con đường từ lá đến gốc là một con đường hợp pháp. Đó là điều mà một DFS đệ quy sẽ theo dõi.

Tôi chắc chắn rằng nó có thể được thực hiện ở đây, nhưng tôi không thấy chính xác làm thế nào để làm điều đó.

Tôi đã xác định giao thức cho thuật toán này, trong đó GRAPH-EQUAL và GRAPH-NEXT có thể được xác định cho các đối tượng tùy ý.

Loại nút gỡ lỗi là TÌM KIẾM-NODE và có trình truy cập dữ liệu SEARCH-NODE-DATA.

(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

Xem A Very General Method for Computing Shortest Paths cho một thuật toán mà có thể trả lại tất cả những con đường trong một đồ thị (ngay cả khi có chu kỳ) là cụm từ thông qua bảng chữ cái của các cạnh trong thời gian hữu hạn (giả sử một đồ thị hữu hạn).

Answer 2

Bạn cần phải chuyển danh sách đường dẫn (mark-list) cùng với các nút, vì đó là một phần của tiểu bang. Tôi đã đổi tên nó là path trong mã này:

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