Схема глубины первого поиск функции графа

Question

Это домашнее задание вопрос, я пытаюсь сделать Depth-первой функцию поиска в схеме, Вот код, который я написал до сих пор:

(define explore 
(λ(node visited) 
    (let* ([neighbors    (force (cdr node))] 
     [next  (nextNode visited neighbors)] 
     [is-visited  (member? node visited)]) 

    (cond 

     ;if I have no unvisited neighbours print current node and go up one level 
     [(equal? next #f) 
     (begin 
     (display (car node)) 
     (display " "))] 

     ;if current node is not visited and I have unvisited neighbors 
     ;print current node,mark as visited and visit it's neighbors 
     [(and (equal? is-visited #f) (not (equal? next #f))) 
     (begin 
     (display (car node)) 
     (display " ") 
     (explore next (cons node visited)))]) 

    ;go and visit the next neighbor 
    (if (not (equal? (nextNode (cons next visited) neighbors) #f)) 
    (explore (nextNode (cons next visited) neighbors) (cons node visited)))))) 

«узел» является текущим узлом
«посетил» список в ведьму я следить за узлы, которые я посетил
«NextNode» является функцией, которая возвращает первый непосещенные соседа, если любой или #f иначе
«члена? ' тест выполняется, если узел находится в посещаемой списке

Представление графа используется смежно с использованием ссылки на узлы с letrec так вот почему я использую силу в «соседей»: Eg:
(letrec ([node1 (список " NY »(delay (list node2 node3)))], где node2 и node3 определены как node1

Проблема, с которой я имею дело, заключается в том, что мои посещаемые списки теряют следы некоторых узлов, которые я посетил, когда я прихожу из рекурсии Как я могу это исправить?

Answer 1

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

EDIT: Возможно, лучший способ - просто перестроить свою функцию. Я думаю, что это сложнее, чем нужно. Вы просто делаете первый шаг, верно? Не совсем поиск? Вы могли бы попробовать что-то больше, как это, используя явный стек для отслеживания узлов, чтобы посетить, и список узлы посетил:

(define dft 
    (lambda (graph) 
    (helper graph '(1) '()))) 

(define helper 
    (lambda (graph stack visited) 
    (if (empty? stack) 
     '() ;we're done. you've got a nice list of visited nodes now, what will you do with it? Return it? 
     (let ([currentNode (car stack)]) 
     (if (member? currentNode visited) 
      (helper graph 
        ;what do you think the next two parameters are? 
        ) 
      (begin 
       (display currentNode) 
       (helper graph 
         ;what do you think the next two parameters are? 
        )))))) 

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

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

Answer 2

Я ответил here.

Один из способов сделать это - просто вернуть список, чтобы у вас был доступ к нему на более высоких уровнях рекурсии.

Другим методом является сохранение вашего списка в переменной вне рекурсии. Другими словами, не сохраняются в стеке. Поскольку для этого не рекомендуется использовать глобальную переменную, нам нужно иметь некоторую локальную рекурсию.

Следующий код - это глупый способ изменить список, но он иллюстрирует технику, о которой я говорю.

(define (letrecreverse lst) 
    (letrec ((retlist '()) 
      (reverse (lambda (lst) 
         (if (null? lst) 
          '() 
          (begin 
          (set! retlist (cons (car lst) retlist)) 
          (reverse (cdr lst))))))) 
    (reverse lst) 
    retlist)) 

(letrecreverse '(1 2 3 4)) 
;outputs '(4 3 2 1) 

Можете ли вы принять эту технику для своих целей?