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

    start = problem.getStartState()
    stack = Stack()
    visited = []
    stack.push(start)
    if problem.isGoalState(problem.getStartState):
        return something
    while stack:
        parent = stack.pop()
        if parent in visited: continue
        if problem.isGoalState(parent):
            return something
        visited.append(parent)
        children = problem.getSuccessors(parent)
        for child in children:
            stack.push(child[0])

Переменные startState и goalState - это просто набор координат x, y. Проблема в классе с различными методами. Важными из них здесь являются getSuccessors (который возвращает потомков данного состояния в виде списка из трех кортежей элементов. Для этой части проблемы, однако, только первый элемент кортежа, (child [0]), который возвращает состояние дочернего элемента в координатах x, y, важно) и isGoalState (который предоставляет координаты x, y состояния цели).

Поэтому я ДУМАЮ (сложно проверить в данный момент), что эта функция при правильной реализации всего остального вернется, как только достигнет целевого состояния. Пожалуйста, дайте мне знать, если я что-то упустил. Моя самая большая проблема, однако, это то, что вернуться. Я хочу, чтобы он выводил список всех состояний, необходимых для достижения состояния цели, в порядке от начала до конца. Это не похоже на простое возвращение моего стека, так как в стеке будет много непосещенных потомков. Мой список посещений также не принесет ничего полезного, так как вполне возможно, что я смогу зайти в тупик, вернуться назад, но все равно иметь тупиковые кортежи в списке посещений. Как мне получить список, который мне нужен?