Отслеживание и возвращение пути в глубину Первый поиск

Итак, у меня есть проблема, которую я хочу использовать для поиска первого глубины, возвращая первый путь, который находит 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 (который возвращает дочерние элементы заданного состояния в виде списка из 3-х кортежей элементов. Однако для этой части проблемы используется только первый элемент кортежа (child [0]), который возвращает состояние дочернего элемента в координатах x, y) и isGoalState (который предоставляет координаты x, y состояния цели).

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

Ответ 1

Вы правы - вы не можете просто вернуть стек, он действительно содержит много невидимых узлов.

Однако, поддерживая карту (словарь): map:Vertex->Vertex такой, что parentMap[v] = the vertex we used to discover v, вы можете получить свой путь.

Модификация, которую вам нужно будет сделать, в значительной степени находится в цикле for:

    for child in children:
        stack.push(child[0])
        parentMap[child] = parent #this line was added

Позже, когда вы нашли свою цель, вы можете получить путь от источника к цели (псевдокод):

curr = target
while (curr != None):
  print curr
  curr = parentMap[curr]

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

Я однажды ответил на аналогичный (хотя и не идентичный ИМО) вопрос относительно нахождения фактического пути в BFS в этой теме

Другим решением является использование рекурсивной версии DFS, а не итеративного + стека, и как только цель будет найдена, распечатайте все узлы current в резервной копии рекурсии - но это решение требует редизайна алгоритма для рекурсивного один.

P.S. Обратите внимание, что DFS может не найти путь к цели (даже если поддерживается набор visited), если граф содержит бесконечную ветвь.
Если вы хотите, чтобы полный (всегда находит решение, если он существует) и оптимальный алгоритм (находит самый короткий путь), вы можете использовать BFS или Итеративное углубление DFS или даже A * Алгоритм если у вас есть эвристическая функция

Ответ 2

эта ссылка должна помочь вам много... Это длинная статья, в которой много говорится о поиске DFS, которое возвращает путь... и я чувствую, что это лучше, чем любой ответ, который я или кто-либо еще может опубликовать

http://www.python.org/doc/essays/graphs/

Ответ 3

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

Пример:

     A
   /    \
  C      B
  \     / \
   \    D E
    \    /
       F


graph = {'A': set(['B', 'C']),
         'B': set(['A', 'D', 'E']),
         'C': set(['A', 'F']),
         'D': set(['B']),
         'E': set(['B', 'F']),
         'F': set(['C', 'E'])}




def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    visited = set()
    while stack:
        (vertex, path) = stack.pop()
        if vertex not in visited:
            if vertex == goal:
                return path
            visited.add(vertex)
            for neighbor in graph[vertex]:
                stack.append((neighbor, path + [neighbor]))

print (dfs_paths(graph, 'A', 'F'))   #['A', 'B', 'E', 'F']

Ответ 4

Я только что реализовал нечто подобное в PHP.

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

/**
 * Depth-first path
 * 
 * @param Node $node        Currently evaluated node of the graph
 * @param Node $goal        The node we want to find
 *
 * @return The path as an array of Nodes, or false if there was no mach.
 */
function depthFirstPath (Node $node, Node $goal)
{
    // mark node as visited
    $node->visited = true;

    // If the goal is found, return immediately
    if ($node == $goal) {
        return array($node);
    }

    foreach ($node->outgoing as $edge) {

        // We inspect the neighbours which are not yet visited
        if (!$edge->outgoing->visited) {

            $result = $this->depthFirstPath($edge->outgoing, $goal);

            // If the goal is found, return immediately
            if ($result) {
                // Insert the current node to the beginning of the result set
                array_unshift($result, $node);
                return $result;
            }
        }
    }

    return false;
}