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

Итак, у меня есть проблема, которую я хочу использовать для поиска по глубине, возвращая первый путь, который находит 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 состояния цели).

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

 SMKS01 сент. 2016 г., 18:02
Желаем удачи в вашей домашней работе с Pacman AI;)ai.berkeley.edu/project_overview.html

Ответы на вопрос(4)

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

Пример:

     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']

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

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

 Joran Beasley12 окт. 2012 г., 19:58
Хорошо, это более общий разговор о графиках ... но если вы изучите его, то это действительно DFS ... и он имеет утку, поэтому они могут копировать / вставлять и просматривать результаты в отличие от OP ...
 amit12 окт. 2012 г., 19:59
(Удален предыдущий слишком резкий комментарий, это перефразировка) ОП спрашивает оконкретный вопрос о DFS - ответ с общей ссылкой не кажется мне ответом. По крайней мере, направьте его к соответствующей части в статье, которая отвечает на вопрос, по вашему мнению.
 Joran Beasley12 окт. 2012 г., 20:38
все дело в возвращении путей ... в этом и был вопрос, ... который сказал, что ваш ответ с учетом его конкретного вопроса, безусловно, отвечает ОП ... но эта статья все еще, вероятно, является хорошим материалом для чтения для него ... она предоставляет очень хорошая функция исследования графа, которая ясна и лаконична ...

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;
}
Решение Вопроса

он действительно содержит много не посещенных узлов.

Однако, поддерживая карту (словарь):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]

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

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

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

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

 14wml15 мар. 2017 г., 05:43
@amit Это на самом деле не работает, если узлы имеют ребра, которые являются двойными сторонами (то есть Edge (u, v) и Edge (v, u) существуют).
 user142766112 окт. 2012 г., 20:08
в то время как вылечить! = Нет: newList.append (curr) curr = parentMap [curr]. А потом печатать (newList.reverse ())? Извините за отсутствие разрывов строк, не могу сделать их в комментариях.
 amit12 окт. 2012 г., 20:10
@ user1427661: (1) Вы иногда используетеcure и иногдаcurr - это должен быть один из них. (2) Да, это должно сработать (3) Прочитайте мои правки относительно выбора DFS в качестве вашего алгоритма - вы должны знать о его недостатках.
 user142766112 окт. 2012 г., 20:06
Хорошее решение. , , Для получения правильного заказа, будет ли что-то подобное работать?
 14wml15 мар. 2017 г., 06:20
for child in children вместо того, чтобы делатьparentMap[child] = parent вам нужно проверить, был ли дочерний элемент уже добавлен в parentMap (т.е.if(!parentMap.containsKey(child)){parentMap.put(child, parent);})

Ваш ответ на вопрос