Tracing and Returning a Path in Depth First Search

Question

Tracing and Returning a Path in Depth First Search

Así que tengo un problema que quiero usar la búsqueda de profundidad primero para resolver, devolviendo la primera ruta que encuentra DFS. Aquí está mi función DFS (incompleta):

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

Las variables startState y goalState son simplemente una tupla de coordenadas x, y. el problema es una clase con una variedad de métodos. Los importantes aquí son getSuccessors (que devuelve los hijos de un estado dado en forma de una lista de 3 tuplas de elementos. para esta parte del problema, sin embargo, solo el primer elemento de la tupla, (child[0]), que devuelve el estado del hijo en coordenadas x, y, es importante) e isGoalState (que proporciona las coordenadas x, y del estado objetivo).

Así QUE CREO (difícil de probar en este punto), que esta función, dada la implementación adecuada de todo lo demás, volverá una vez que haya alcanzado un estado de meta. Por favor, hágamelo saber si me estoy perdiendo algo. Mi mayor problema, sin embargo, es QUÉ devolver. Quiero que la salida de una lista de todos los estados que se necesita para llegar a la estado objetivo, en orden desde el principio hasta el final. No parece que simplemente devolver mi pila haga el truco, ya que la pila incluirá muchos niños no visitados. Tampoco mi lista visitada producirá nada útil, ya que es concebible que pueda llegar a callejones sin salida, tener que retroceder, pero aún tener las tuplas sin salida en la lista visitada. ¿Cómo conseguiría la lista que deseo?

24

python algorithm artificial-intelligence

Author: user1427661, 2012-10-12

Source

4 answers

No es específico para su problema, pero puede modificar este código y aplicarlo a diferentes escenarios, de hecho, puede hacer que la pila también mantenga la ruta.

Ejemplo:

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

7

Author: XueYu,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2016-09-07 17:40:42

Este enlace debería ayudarte mucho ... Es un artículo extenso que habla extensamente sobre una búsqueda DFS que devuelve una ruta... y siento que es mejor que cualquier respuesta que yo o cualquier otra persona pueda publicar

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

4

Author: Joran Beasley,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2012-10-12 17:17:06

Acabo de implementar algo similar en PHP.

La idea básica detrás es la siguiente: ¿Por qué debo mantener otra pila, cuando existe la pila de llamadas , que en cada punto de la ejecución refleja la ruta tomada desde el punto de entrada. Cuando el algoritmo alcanza el objetivo, simplemente necesita viajar hacia atrás en la pila de llamadas actual, lo que resulta en leer el camino tomado hacia atrás. Aquí está el algoritmo modificado. Observe las secciones 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;
}

1

Author: user2555221,
Warning: date(): Invalid date.timezone value 'Europe/Kyiv', we selected the timezone 'UTC' for now. in /var/www/agent_stack/data/www/ajaxhispano.com/template/agent.layouts/content.php on line 61
2013-07-06 00:05:36

score 32 · Accepted Answer

Tiene razón - no puede simplemente devolver la pila, de hecho contiene una gran cantidad de nodos no visitados.

Sin embargo, manteniendo un mapa (diccionario): map:Vertex->Vertex tal que parentMap[v] = the vertex we used to discover v, puede obtener su ruta.

La modificación que tendrá que hacer es más o menos en el bucle for:

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

Más tarde, cuando encuentre su destino, puede obtener la ruta de la fuente al destino (pseudo código):

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

Tenga en cuenta que el orden se invertirá, se puede resolver presionando all elementos a una pila y luego imprimir.

Una vez respondí una pregunta similar (aunque no idéntica IMO) con respecto a encontrar la ruta real en BFS en este hilo

Otra solución es usar una versión recursiva de DFS en lugar de la pila iterativa+, y una vez que se encuentre un destino, imprimir todos los nodos current en la copia de seguridad recursiva - pero esta solución requiere un rediseño del algoritmo a uno recursivo.

P.d. Tenga en cuenta que DFS podría no encontrar una ruta a la objetivo (incluso si se mantiene un conjunto visited) si el gráfico contiene una rama infinita.
Si desea un algoritmo completo (siempre encuentra una solución si existe) y óptimo (encuentra el camino más corto), es posible que desee usar BFS o Profundización Iterativa DFS o incluso Un* Algoritmo si tiene alguna función heurística