Проблема с внедрением поиска в глубину в схеме

Question

Я пытаюсь реализовать поиск в глубине в схеме, но я могу заставить его работать только частично.Это мой код:

 (define (depth-first-search graph node neighbour path dest)
  (cond ((null? neighbour) #f)
        ((equal? node dest) path)
        ((member (car neighbour) path) (depth-first-search graph node (cdr neighbour) path dest))
        ((memq (car neighbour) (car graph)) (depth-first-search (cdr graph) (car neighbour) (memq (car neighbour) (car graph)) (append path (list (car neighbour))) dest))
        (else depth-first-search (cdr graph) path dest)))

А это мой график, структура данных:

  (define complete-graph
  '((a b c d e)
    (b a c)
    (c a b f)
    (d a e h)
    (e a d)
    (f c g i)
    (g f h i j) 
    (h d g j)
    (i f g j)
    (j g h i)))

Вот как я называю процедуру:

(depth-first-search complete-graph (caar complete-graph) (cdar complete-graph) (list (caar complete-graph)) 'd)

КомуПроцедура должна вернуть полный путь от начального узла к месту назначения (в виде списка), но кажется, что он работает только с некоторыми начальными и конечными узлами.Если я начну с 'a и' c, он вернет правильный список '(abc), но если я попытаюсь с' a и 'd, я получу #f взамен.Так что, вероятно, что-то не так с возвратом в алгоритм.Но я слишком долго смотрел на код и не могу найти проблему ..

Answer 1

Предполагая, что узел 'a имеет дочерние элементы' (bcde), узел 'b имеет дочерние элементы' (ac), узел ... Сначала вам понадобится функция, которая расширяет узел до его дочерних элементов.

(define (expand graph node)
  (let ((c (assq node graph)))
    (if c (cdr c) '())))

Второе: вы должны запомнить все посещенные узлы.В общем, шляпа отличается от пути (возможно, это не имеет значения в этом примере).Третье: вам нужно запомнить все узлы, которые вы хотите посетить (результат процесса расширения узла).Поэтому определите вспомогательную функцию

(define (dfs* graph visited border path dest)

Если не осталось ни одного узла для посещения, значит, дороги не существует.

  (cond ((null? border) #f)

Если первый элемент на границе равен нашему месту назначения, томы счастливы

        ((eq? (car border) dest) (cons (car border) path))

Давайте проверим все посещенные узлы.Если первый узел в границе был посещен ранее, тогда продолжайте без расширения узла

        ((memq (car border) visited)
         (dfs* graph visited (cdr border) path dest))

В противном случае разверните первый узел границы

        (else (dfs* graph
                   (cons (car border) visited)
                   (append (expand graph (car border)) (cdr border))
                   (cons (car border) path)
                   dest))))

Вызовите эту вспомогательную функцию с начальными значениями для посещения, границыи путь:

(define (dfs graph src dst)
  (dfs* graph '() (list src) '() dst)

Для первого поиска дыхания: добавьте расширенный узел в конце границы

Редактировать: a) посещенные и пути совпадают, вы можете удалить один из них b) путь возвращается в обратном порядке в) Процедура неверна, путь содержит все посещенные узлы.Но постобработка результата dfs * сделает эту работу.

Answer 2

Вы не хотите изменять график при выполнении поиска в глубину, только текущий узел. Если вы хотите делать все чисто функционально, сделайте так, чтобы ваша функция выглядела так:

(define (depth-first-search graph node dest path)
  (let dfs ((node node) (path path))
    (let ((recur (lambda (node) (dfs node (cons node path)))))
      ; Write code here
      ; Recursive calls should use recur, not dfs or depth-first-search
      ...)))

(возвращает путь или #f в качестве результата). Вы можете использовать ormap (в Racket или SRFI-1) для перебора всех соседей узла, возвращая первое значение, которое не является #f.