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

Question

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

(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 в противном случае
'Член? проверка наличия узла в списке посещений

Представление Graph использует соседние объекты, созданные с использованием ссылок на узлы с помощью letrec, поэтому я использую силу в 'соседях': Например:
(letrec ([узел1 (список «NY») (задержка (список узел2, узел3)))], где узел2 и узел3 определены как узел1

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

Answer 1

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

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

Я ответил здесь .

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

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

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

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

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