Схема Найти все возможные пути для неориентированного графа - PullRequest
Новая
       19

Схема Найти все возможные пути для неориентированного графа

1 голос
/ 18 октября 2011

У меня проблема с распечаткой всех возможных путей.В настоящее время я могу распечатать только один путь, и если (path-demo "J" "I"), программа выдаст эту ошибку mcdr: ожидает аргумент типа <mutable-pair>;учитывая #f

 (define net
  '(("A" "B")
    ("B" "A" "C")
    ("C" "B" "D")
    ("D" "C" "E" "F")
    ("F" "I" "D")
    ("I" "F")
    ("E" "D" "J")
    ("J" "E" "G")
    ("G" "J" "H"))) 

 (define (path-demo start finish)
         (for-each (lambda (x) (display x) (display " "))
                   (cons "Route:" (shortest-path start finish net))))

 (define (shortest-path start end net)
    (bfs end (list (list start)) net))

 ;; Breadth-first search
  (define (bfs end queue net)
    (display queue) (newline) (newline) ; entertainment
    (if (null? queue)
      '()
      (let ((path (car queue)))
       (let ((node (car path)))
         (if (equal? node end) ;; Graham used CL eql
             (reverse path)
             (bfs end 
                  (append (cdr queue)
                          (new-paths path node net))
                  net))))))

 (define (new-paths path node net)
   (map (lambda (n) (cons n path)) (cdr (assoc node net))))

;;
(path-demo "J" "I")

Ответы [ 2 ]

1 голос
/ 22 октября 2011

В своем определении сети вы забыли перечислить узлы, к которым подключен H.

При возникновении ошибки узел и сеть имеют следующие значения: 

node: H 
net: ((A B) (B A C) (C B D) (D C E F) (F I D) (I F) (E D J) 
      (J E G) (G J H)))

Таким образом 

(assoc node net))

вернет #f, потому что H не имеет ассоциаций в сети. И это приводит к ошибке из CDR: 

cdr: expects argument of type <pair>; given #f
0 голосов
/ 18 октября 2011

Вполне вероятно, что следующее возвращает #f: 

(cdr (assoc node net))

Относительно комментария (для форматирования): 

(define (new-paths path node net)
   (write node)
   (newline)
   (map (lambda (n) (cons n path)) (cdr (assoc node net))))
...