espacio extra para búsqueda recursiva en profundidad para almacenar rutas

Question

Estoy utilizando la búsqueda de profundidad para identificar rutas en un gráfico ponderado dirigido, mientras reviso los nodos que pertenecen a un ciclo, y establezco condiciones de corte basadas en la distancia total recorrida, o se detiene desde el nodo de origen.

Según tengo entendido, la recursividad no se requiere una estructura de pila explícita de primera búsqueda en profundidad, así que me preguntaba si podría simplificar aún más mi código de abajo de alguna manera hacer sin la pila explícita:

public class DFSonWeightedDirectedGraph { 

    private static final String START = "A"; 
    private static final String END = "E"; 
    private int pathLength = 0; 
    private int stops = 0; 

    public static void main(String[] args) { 
     //this is a directed weighted graph 
     WeightedDirectedGraph graph = new WeightedDirectedGraph(); 
     graph.addEdge("A", "B", 15); 
     graph.addEdge("A", "D", 15); 
     graph.addEdge("A", "E", 27); 
     //(...) more edges added 


     Stack<String> visited = new Stack<String>();   
     visited.push(START); 

     new DFSonWeightedDirectedGraph().depthFirst(graph, visited); 
    } 

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) { 

     Collection<Map.Entry<String, Integer>> tree_of_children 
      = graph.get_tree_of_children(visited.peek()); 

     for (Map.Entry<String, Integer> child : tree_of_children) { 


      if(pathLength + child.getValue()>= 20){ 
       continue; 
      }  


      visited.push(child.getKey()); 
      pathLength += child.getValue(); 
      stops += 1;   

      if (child.getKey().equals(END)) { 
       printPath(visited); 
      } 

      depthFirst(graph, visited); 
      visited.pop(); 
      pathLength -= child.getValue(); 
      stops -= 1; 
     } 
    } 

    private void printPath(Stack<String> visited) { 
     for (String node : visited) { 
      System.out.print(node); 
      System.out.print(" "); 
     } 
     System.out.println("[path length: "+pathLength + 
       " stops made: " + stops +"]"); 
    } 
} 

Sin embargo , otras implementaciones recursivas sin una estructura de pila explícita generalmente tienen en cuenta nodos ya visitados, coloreándolos en blanco, gris o negro. Entonces, en mi caso, donde se permite volver a visitar, y la ruta necesita ser registrada, ¿es absolutamente necesaria una pila explícita? Gracias por cualquier sugerencia de alternativas más simples.

Answer 1

Si tiene que guardar la ruta, necesita una estructura de datos para esto. Tu pila está bien; podrías reemplazarlo con otra estructura de datos, pero no deshacerte de ella.

Si estaría bien imprimir directamente la ruta (y no grabarla), no necesita una pila. Luego puede cambiar la firma del método para obtener solo el gráfico y el nodo real (y tal vez la longitud del camino real y las "paradas").

Answer 2

Editar: Esta respuesta está completamente fuera del tema y fue publicada en base a la interpretación errónea de la pregunta.

Hay varias cosas incorrectas con su implementación de DFS. Sí, visita todos los nodos en profundidad y finalmente logra encontrar una ruta entre START y END, pero no intenta verificar los nodos ya visitados y mantiene una pila sin ningún motivo real. La única razón por la que no cae en ciclos de recursión infinita es porque limita la longitud máxima de la ruta, y aún tardará mucho tiempo en gráficos que tienen varias rutas distintas entre todos los pares de vértices.

Lo único que está usando la pila es pasar el nodo que se va a visitar junto a la función dfs. Simplemente puede deshacerse de la pila y pasar el nodo directamente.

Así, en lugar de

private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) { 
    ... 
    visited.push(child); 
    ... 
    depthFirst(graph, visited); 

Simplemente puede escribir esto como

private void depthFirst(WeightedDirectedGraph graph, String node) { 
    ... 
    //visited.push(child); <-- No longer needed 
    ... 
    depthFirst(graph, child); 

Está utilizando una estructura de datos (pila) que ha llamado 'visitado' y sin embargo no se utiliza eso para almacenar/marcar qué nodos ya se han visitado para evitar volver a visitarlos.

Puede modificar su código existente para tener un conjunto llamado visitado (convertirlo en una variable global/de clase o pasarlo a lo largo de llamadas recursivas como hizo con su pila) donde mantiene todos los nodos ya visitados y solo llama a depthFirst() en esos nodos que aún no están en ese conjunto.

Eso debería hacer que su código de algo como esto

private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) { 
    visited.add(node); // mark current node as visited 
    ... 
    //visited.push(child); <-- No longer needed 
    ... 
    if (!visited.contains(child)){ // don't visit nodes we have worked on already 
     depthFirst(graph, child); 
    } 

Hasta ahora, mi respuesta ha sido tratar de modificar el código para hacer que funcione. Pero me parece que necesita obtener una mejor idea de lo que realmente es un DFS y cómo realmente funciona. Leer el capítulo correspondiente sobre cualquier buen libro de Algoritmo/Teoría de Gráficos te ayudará mucho. Recomendaría CLRS (tiene un capítulo muy bueno sobre cruces de gráficos simples), pero cualquier buen libro debería serlo.Un DFS recursivo simple y correcto se puede implementar de una manera mucho más simple utilizando matrices, sin tener que recurrir a pilas o conjuntos.

Edit: No mencioné cómo podría recuperar la ruta después de reemplazar la pila. Esto se puede hacer fácilmente mediante el uso de un mapa que almacena el padre de cada nodo a medida que se explora. La ruta (si se encuentra alguna) se puede obtener usando una función recursiva printPath (String node), que imprime el nodo que se le pasó y se llama de nuevo a su padre.

Answer 3

Simplemente agregue un campo adicional a la estructura del nodo, que es un campo "visitado". Este será el más rápido. Tienes que desmarcar todos los nodos después (o antes de hacer la búsqueda).

O bien, simplemente hash la identificación del nodo en una tabla hash. Esto será más rápido de verificar que una pila. Si no tiene una identificación para el nodo, es una buena idea crear una, para ayudar con la depuración, salida, etc.

Necesita espacio adicional, pero agregar un campo booleano a cada nodo requerirá el menor espacio, ya que será 1 bit por nodo, frente a 1 puntero por nodo para una pila.

Realmente no necesita un corte de distancia, ya que está buscando un gráfico finito y solo visita cada nodo una vez, por lo que visitará como máximo N nodos en un gráfico de nodos. Necesitaría un límite de profundidad si estuviera buscando un espacio infinito, como cuando hace una búsqueda de espacio de estado (un ejemplo es un intérprete de prólogo que busca una prueba).

Answer 4

No necesita los nodos visitados. Simplemente pase su nodo hijo actual al método recursivo en lugar del parámetro de nodos visitados, y use el valor de retorno para llevar la ruta.

Si puede procesar el elemento de ruta por elemento, es decir, reescriba printPath() para que se pueda llamar una vez por elemento, solo se requiere el tipo de clave como tipo de devolución. Si desea recibir toda la ruta, necesita una lista de valores clave como tipo de devolución.

En realidad, está relativamente cerca de la solución. Solo use la pila de llamadas de métodos recursivos para representar la ruta.