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

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

(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, поэтому я использую force в «соседях»: например:
(letrec ([node1 (list «NY» (delay (list node2 node3)))], где node2 и node3 определены как node1

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


recursion scheme racket
person John Retallack    schedule 05.05.2010    source источник
comment
Похоже, что этот пост является просто расширением:stackoverflow. com/questions/2773878/. Вам следует подумать о закрытии одного из них.   -  person Davorak    schedule 05.05.2010

Ответы (2)


arrow_upward
1
arrow_downward

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

РЕДАКТИРОВАТЬ: Возможно, лучшим способом было бы просто реструктурировать вашу функцию. Я думаю, что это сложнее, чем должно быть. Вы просто делаете обход в глубину, верно? Не совсем поиск? Вы можете попробовать нечто подобное, используя явный стек для отслеживания посещенных узлов и список посещенных узлов:


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

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

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

person ajduff574    schedule 05.05.2010
comment
Если я верну список посещений, как я могу получить его при выходе из рекурсии здесь: (исследовать следующий (посещенный минус-узел)))]), могу ли я определить локальную переменную в ведьме для ее хранения, если да, то как? если я верну его при выходе из рекурсии здесь: [(равно? следующий #f) (начать (отобразить (автомобильный узел)) (отобразить) (посещенный минус-узел)] и я делаю (отобразить (исследовать следующий (посещенный минус-узел) )) он напечатает пустоту, почему так? - person John Retallack; 05.05.2010
comment
что представляет дерево в (вспомогательное дерево? - person John Retallack; 05.05.2010
comment
Извините, я изначально написал функцию, думающую деревьями, а не графами. Вы бы передали график функции, так как вам понадобится график, чтобы найти соседей. Я отредактировал код, чтобы было понятнее. - person ajduff574; 05.05.2010
comment
Я думаю, что знаю, что такое параметры, но я не могу понять, где вы помещаете узлы в стек, не должен ли алгоритм быть чем-то вроде: получить узел из стека, пометить как посещенный, поместить всех непосещенных соседей в стек, повторить пока стек не станет пустым - person John Retallack; 05.05.2010
comment
Вы можете поместить узлы в стек в списке параметров. Например, один параметр может быть примерно таким: (добавить соседей (стек cdr)) Представляет собой новый стек, состоящий из старого стека за вычетом текущего узла, а соседи помещаются наверх. - person ajduff574; 06.05.2010
comment
Я полагаю, что также стоит упомянуть, что вы можете исключить внутренний оператор if, если вы никогда не помещаете посещенные узлы в стек. Я предполагаю, что мы просто помещаем всех соседей в стек. - person ajduff574; 06.05.2010
comment
Я понял, но до сих пор не понимаю, как это решит проблему со списком посещений, не потеряю ли я элементы из него при возврате из рекурсии? - person John Retallack; 06.05.2010
comment
Я должен сделать мой последний комментарий более ясным. Я предполагаю, что мы помещаем в стек всех соседей, пока текущий узел не был посещен. Если вы хотите отфильтровать посещенных соседей перед их отправкой, вы можете удалить самый внутренний оператор if, поскольку текущий узел никогда не будет посещен (помните, мы получаем его из стека). Существует даже функция схемы под названием фильтр, которую можно использовать для удаления всех посещенных соседей из списка соседей. Однако этот подход может быть немного сложнее. - person ajduff574; 06.05.2010
comment
Он не потеряет элементы, если вы вернете его. Если вы подставите посещенный вместо '() прямо перед первым комментарием, будет возвращен список посещенных, как он был, когда вы закончили посещение. Поскольку мы всегда возвращаем результат помощника, этот список посещений будет распространяться через рекурсивные вызовы, и dft фактически вернет список посещений. - person ajduff574; 06.05.2010
comment
для замены посещенного не должен ли вспомогательный вызов быть вложенным в другой вспомогательный вызов, что-то вроде (стек вспомогательного графа (помощник...))? - person John Retallack; 06.05.2010
comment
Нет. Вы можете представить вызовы примерно так: dft -> helper -> helper -> helper -> helper. dft вызывает помощника. Затем хелпер вызывает хелпер, который вызывает хелпер, который вызывает хелпер, который возвращает список посещений. Поскольку все предыдущие функции просто возвращают результаты того, что они вызывали, список посещений передается вверх как возвращаемое значение этих вызовов. - person ajduff574; 06.05.2010
comment
Однако вам придется изменить список посещений, который вы передаете во вспомогательные функции. Таким образом, один из параметров будет выглядеть примерно так: (cons currentNode посетил). - person ajduff574; 06.05.2010
comment
Я сделал это, это работает, за исключением того, что график имеет циклы, я не могу понять, почему это так - person John Retallack; 06.05.2010
comment
Возможно, вы передаете неверные параметры вспомогательной функции. Убедитесь, что если узел был посещен, вы не заталкиваете соседей в стек. Также убедитесь, что вы помещаете текущий узел в список посещенных, если это еще не сделано: (против текущего посещенного узла). - person ajduff574; 06.05.2010
comment
Извините, я также только что заметил ошибку в моем коде. Возможно, вам придется поменять местами оператор let с первым оператором if. Я отредактировал свой ответ, чтобы отразить это. - person ajduff574; 06.05.2010

arrow_upward
0
arrow_downward

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

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

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

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

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

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

person Davorak    schedule 05.05.2010
comment
Затем вам нужно вернуть список в стеке с каждого уровня, чтобы вы могли получить к нему доступ на том, что выше возврата. - person Davorak; 05.05.2010