Может ли поиск в глубину с использованием стека вернуть путь к цели?

Question

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

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

Я не могу позволить узлам иметь свойство пути позади них, так как это домашнее задание.

Я был в тупике на этом более недели!

Answer 1

Всякий раз, когда вы извлекаете узел из стека, вам нужен способ получения пути, который привел к этому узлу.

Одним из решений является вставка в стек (node, path) вместо просто значений node. Если path является чисто функциональным списком, как в Haskell, это хорошее решение, но в Python это может быть не так идиоматично. Кроме того, хотя путь, строго говоря, не хранится внутри узла, это решение, вероятно, не соответствует духу вопроса.

Другим решением является поддержка отдельного стека, который содержит путь к ранее посещенному узлу. Стек первой глубины содержит кортежи (node, depth), где depth - глубина узла в поиске. Перед добавлением node в конец пути элементы выталкиваются с пути до тех пор, пока длина пути не будет равна depth.

Answer 2

"A node must be called directly by its parent so that it can receive the path behind it," <- Кажется, все в порядке. </p>

whereas when this node is pushed onto a stack, it loses the path so far. <- Мне не о чем беспокоиться. </p>

Что вы можете сделать, так это рекурсивно построитьдо стека с чем-то вроде

def makepath(someGraph, from, to):
    if(from == to)
        return ""

    nextNode= <...> #find out next node in path here
    return makepath(someGraph, nextNode, to) + str(nextNode)