Tutti i percorsi tra 2 nodi nel grafico

Question

Devo eseguire un programma di ricerca non esaustivo (Breadth-first-Search) che prende due nodi e restituisce tutti i percorsi tra di loro.

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()); 
        } 
       } 
      } 
     } 

mio problema è che ho solo due percorsi invece di tutti e io non so cosa modificare nel mio codice per farli tutti. L'input del mio problema si basa su questa mappa:

Answer 1

Nell'algoritmo BFS non è necessario fermarsi dopo aver trovato una soluzione. Un'idea è quella di impostare i dati nulli per tutte le città visitate tranne la prima e lasciare che la funzione funzioni un po 'più a lungo. Non ho tempo per scriverti uno snippet ma se non lo capisco scriverò almeno uno pseudocodice. Se non hai capito la mia idea, pubblica un commento con la tua domanda e cercherò di spiegarti meglio.

Answer 2

Suona come i compiti. Ma il tipo divertente.

Quello che segue è pseudocodice, è la profondità prima invece di respiro prima (così dovrebbe essere convertito in un algoritmo di tipo di coda, e può contenere bug, ma il jist generale dovrebbe essere chiaro

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; 
} 

Edit:. Is in realtà questa è la risposta alla domanda che stai cercando? Oppure utilizza l'algoritmo di Dijkstra: http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

Answer 3

Larghezza prima la ricerca è uno strano modo per generare tutti i possibili percorsi per il seguente motivo: dovresti tenere traccia di ogni singolo percorso nel file BFS aveva attraversato il nodo, non che fosse stato attraversato del tutto.

prendere un semplice esempio

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

Vogliamo tutti i percorsi da 1 a 5. Abbiamo la fila 1, poi 2 e 3, poi 4, quindi 5. Abbiamo perso il fatto che ci sono due percorsi da 4 a 5.

Vorrei suggerire di provare a farlo con DFS, anche se questo potrebbe essere risolvibile per BFS con qualche pensiero. Ogni cosa accodata sarebbe un percorso, non un singolo nodo, così si potrebbe vedere se quel percorso avesse visitato ciascun nodo. Questo è uno spreco di memoria, grazie

Answer 4

Un percorso è una sequenza di vertici in cui nessun vertice viene ripetuto più di una volta. Data questa definizione, è possibile scrivere un algoritmo ricorsivo che deve funzionare come segue: passare quattro parametri alla funzione, chiamarlo F(u, v, intermediate_list, no_of_vertices), dove u è la sorgente corrente (che deve cambiare come si ricorre), è la destinazione, intermediate_list è una destinazione elenco di vertici che devono essere inizialmente vuoti e ogni volta che utilizziamo un vertice, lo aggiungeremo all'elenco per evitare di utilizzare un vertice più di una volta nel nostro percorso e no_of_vertices è la lunghezza del percorso che vorremmo trova, che deve essere limitato da 2 e superiore delimitata da V, il numero di vertici. In sostanza, la funzione restituirà un elenco di percorsi la cui origine è u, la destinazione è v e la cui lunghezza di ciascun percorso è no_of_vertices. Creare una lista vuota iniziale ed effettuare chiamate a F(u, v, {}, 2), F(u, v, {}, 3), ..., F(u, v, {}, V), ogni volta che si unisce l'output di F con l'elenco in cui intendiamo archiviare tutti i percorsi. Prova ad implementare questo, e se hai ancora problemi, scriverò lo pseudo-codice per te.

Modifica: risoluzione del problema precedente tramite BFS: la prima ricerca di Larghezza è un algoritmo che può essere utilizzato per esplorare tutti gli stati di un grafico. È possibile esplorare il grafico di tutti i percorsi del grafico dato, usando BFS, e selezionare i percorsi che si desidera. Per ogni vertice v, aggiungere i seguenti stati alla coda: (v, {v}, {v}), in cui ogni stato è definito come: (current_vertex, list_of_vertices_already_visited, current_path).Ora, mentre la coda non è vuota, inserire l'elemento superiore della coda, per ogni spigolo e dello , se il vertice di coda x non esiste già nello list_of_vertices_already_visited, inserire il nuovo stato (x, list_of_vertices_already_visited + {x}, current_path -> x) nella coda e elaborare ogni percorso mentre lo si disattiva dalla coda. In questo modo è possibile cercare l'intero grafico dei percorsi per un grafico, diretto o indiretto.