Каковы некоторые истинные предложения по реализации Итеративной глубины в первом поиске? - PullRequest
Новая
       78

Каковы некоторые истинные предложения по реализации Итеративной глубины в первом поиске?

0 голосов
/ 26 января 2020

Итак, из того, что я вижу, я, как и большинство людей, был уверен, что итеративная версия DFS похожа на итеративную BFS, за исключением двух отличий: замените очередь на стек и пометьте узел как обнаруженный после POP, а не после PU SH.

В последнее время меня действительно озадачили два вопроса:

  • В некоторых случаях это приведет к разным результатам, но действительно ли необходимо помечать узел как посещенный после того, как мы обработали POP? Почему неправильно делать это после того, как мы PU SH? Насколько я понимаю, это приведет к тому же самому следствию, что мы делаем это для BFS ... чтобы не было дубликатов в нашей очереди / стеке.
  • Теперь самое важное: у меня сложилось впечатление, что это Реализация итеративной DFS совсем не является истинной DFS: если мы думаем о рекурсивной версии, то она довольно компактна, поскольку не хранит всех возможных соседей на одном уровне (как мы это делаем в итерационной версии), она выбирает только один и идет с ним, а затем он возвращается и идет на второй. В качестве крайнего примера рассмотрим граф с одним узлом в центре и соединенным с 100 листовыми узлами. В рекурсивной реализации, если мы начнем со среднего узла, базовый стек увеличится до максимум 2 ... один для среднего узла и один для каждого листа, который он посещает. Если мы сделаем это так, как мы поступили с итеративной версией, стек вырастет до 1000 элементов. Это не кажется правильным.

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

1 Ответ

3 голосов
/ 26 января 2020

Вопрос 1: Если вы отметили + отметку перед пу sh, он использует меньше места, но меняет порядок посещения узлов. Вы посетите все, хотя.

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

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

func DFS(start):
    let visited = EMPTY_SET
    let stack = EMPTY_STACK

    visited.add(start)
    visit(start)
    stack.push( (start,0) )

    while(!stack.isEmpty()):
        let (parent, pos) = stack.pop()
        if (pos < parent.numChildren()):

            let child = parent.child[pos]
            stack.push(parent,pos+1)

            if (!visited.contains(child)):
                visited.add(child)
                visit(child)
                stack.push( (child,0) )

Вы можете видеть, что это немного сложнее, и записи, которые вы помещаете в стек sh, являются кортежами, что в некоторых случаях раздражает. Часто мы будем использовать два стека параллельно вместо создания кортежей для pu sh, или мы будем вставлять / извлекать две записи за раз, в зависимости от того, как должны быть представлены узлы и позиции дочернего списка.

...