Todas las rutas entre 2 nodos en el gráfico

Question

Tengo que hacer un programa de búsqueda desinformado (Breadth-first-Search) que toma dos nodos y devuelve todas las rutas entre ellos.

public void BFS(Nod start, Nod end) { 
      Queue<Nod> queue = new Queue<Nod>(); 
      queue.Enqueue(start); 
      while (queue.Count != 0) 
      { 
       Nod u = queue.Dequeue(); 
       if (u == end) break; 
       else 
       { 
        u.data = "Visited"; 
        foreach (Edge edge in u.getChildren()) 
        { 
         if (edge.getEnd().data == "") 
         { 
          edge.getEnd().data = "Visited"; 
          if (edge.getEnd() != end) 
          { 
           edge.getEnd().setParent(u); 
          } 
          else 
          { 
           edge.getEnd().setParent(u); 
           cost = 0; 
           PrintPath(edge.getEnd(), true); 
           edge.getEnd().data = ""; 
           //return; 
          } 
         } 
         queue.Enqueue(edge.getEnd()); 
        } 
       } 
      } 
     } 

Mi problema es que solo me dan dos caminos en lugar de todos y yo no sé qué para editar en mi código para llegar a todos ellos. La entrada de mi problema se basa en este mapa:

Answer 1

En el algoritmo BFS no debe detenerse después de encontrar una solución. Una idea es establecer datos nulos para todas las ciudades que visitas excepto la primera y deja que la función se ejecute un poco más. No tengo tiempo para escribirte un fragmento, pero si no lo consigues escribiré al menos un pseudocódigo. Si no entendiste mi idea publica un comentario con tu pregunta y trataré de explicarlo mejor.

Answer 2

Suena a tarea. Pero el tipo divertido.

La siguiente es pseudocódigo, es la profundidad primero en lugar de la respiración primero (por lo que debe ser convertido a un algoritmo de tipo de cola, y puede contener errores, pero la jist general debería ser claro

class Node{ 
    Vector[Link] connections; 
    String name; 
} 

class Link{ 
    Node destination; 
    int distance; 
} 

Vector[Vector[Node]] paths(Node source, Node end_dest, Vector[Vector[Node]] routes){ 
    for each route in routes{ 
    bool has_next = false; 
    for each connection in source.connections{ 
     if !connection.destination in route { 
     has_next = true; 
     route.push(destination); 
     if (!connection.destination == end_dest){ 
      paths(destination, end_dest, routes); 
     } 
     } 
    } 
    if !has_next { 
     routes.remove(route) //watch out here, might mess up the iteration 
    } 
    } 
    return routes; 
} 

Editar:. Está esta es realmente la respuesta a la pregunta que está buscando o si realmente desea encontrar el camino más corto? Si es el último, use el algoritmo de Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

La primera búsqueda de amplitud es una forma extraña de generar todos los caminos posibles la siguiente razón: necesitaría hacer un seguimiento de si cada ruta individual en el BFS había atravesado el nodo, no es que hubiera sido atravesado en absoluto.

poner un ejemplo sencillo

1----2 
\ \ 
    3--- 4----5 

Queremos que todos los caminos de 1 a 5. Poner en cola 1, a continuación, 2 y 3, luego 4, luego 5. Hemos perdido el hecho de que hay dos rutas a través de 4 a 5.

Sugeriría intentar hacer esto con DFS, aunque esto puede ser solucionable para BFS con algo de reflexión. Cada cosa en cola sería una ruta, no un solo nodo, por lo que uno podría ver si esa ruta había visitado cada nodo. Esto es una pérdida de memoria sabia, thoug

Answer 4

Una ruta es una secuencia de vértices donde no se repite más de un vértice. Dada esta definición, puede escribir un algoritmo recursivo que funcionará de la siguiente manera: Pase cuatro parámetros a la función, llámelo F(u, v, intermediate_list, no_of_vertices), donde u es la fuente actual (que cambiará a medida que recursemos), v es el destino, intermediate_list es un lista de vértices que inicialmente estarán vacíos, y cada vez que usemos un vértice, lo agregaremos a la lista para evitar usar un vértice más de una vez en nuestra ruta, y no_of_vertices es la longitud de la ruta que nos gustaría find, que estará limitado por 2, y superior limitado por V, el número de vértices. Esencialmente, la función devolverá una lista de rutas cuya fuente es u, el destino es v, y cuya longitud de cada ruta es no_of_vertices. Cree una lista vacía inicial y realice llamadas a F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V), fusionando cada vez la salida de F con la lista donde tenemos la intención de almacenar todas las rutas. Intenta implementar esto, y si aún tienes problemas, te escribiré el seudocódigo.

Editar: Resolver el problema anterior con BFS: la primera búsqueda de ancho es un algoritmo que se podría utilizar para explorar todos los estados de un gráfico. Puede explorar el gráfico de todas las rutas del gráfico dado, usando BFS, y seleccionar las rutas que desee. Para cada vértice v, agregue los siguientes estados a la cola: (v, {v}, {v}), donde cada estado se define como: (current_vertex, list_of_vertices_already_visited, current_path).Ahora, mientras la cola no está vacía, extraiga el elemento superior de la cola, para cada borde e del , si el vértice de cola x no existe en el list_of_vertices_already_visited, inserte el nuevo estado (x, list_of_vertices_already_visited + {x}, current_path -> x) en la cola, y procesa cada ruta a medida que la extraes de la cola. De esta forma puede buscar todo el gráfico de rutas para un gráfico, ya sea dirigido o no dirigido.