Trova tutti i percorsi possibili da un vertice in un grafo ciclico diretto in Erlang

StackOverflow https://stackoverflow.com/questions/7834702

Domanda

Vorrei implementare una funzione che trovi tutti i possibili percorsi a tutti i possibili vertici da un vertice sorgente V in un grafo ciclico diretto G.

Le prestazioni ora non contano, vorrei solo capire l'algoritmo. Ho letto la definizione dell'algoritmo di ricerca Depth-first, ma non ho la piena comprensione di cosa fare.

Non ho alcun pezzo di codice completo da fornire qui, perché non sono sicuro di come:

  • memorizzare i risultati (insieme ad A-> B-> C-> dovremmo anche memorizzare A-> B e A-> B-> C);
  • rappresenta il grafico (digrafo? elenco di tuple?);
  • quante ricorsioni usare (lavorare con ogni vertice adiacente?).

Come posso trovare tutti i percorsi possibili da un dato vertice sorgente in un grafo ciclico diretto a Erlang?

UPD: Sulla base delle risposte fino ad ora devo ridefinire la definizione del grafico: è un grafo non aciclico. So che se la mia funzione ricorsiva colpisce un ciclo è un ciclo indefinito. Per evitarlo, posso semplicemente controllare se un vertice corrente è nell'elenco del percorso risultante - in caso affermativo, interrompo l'attraversamento e restituisco il percorso.

UPD2: Grazie per i commenti stimolanti! Sì, devo trovare tutti i percorsi semplici che non hanno loop da un vertice di origine a tutti gli altri.

In un grafico come questo:

Grafico non aciclico

con il vertice sorgente A l'algoritmo dovrebbe trovare i seguenti percorsi:

  • A, B
  • A, B, C
  • A, B, C, D
  • A, D
  • A, D, C
  • A, D, C, B

Il codice seguente fa il lavoro, ma è inutilizzabile con i grafici che hanno più di 20 vertici (immagino che sia qualcosa di sbagliato con la ricorsione - richiede troppa memoria, non finisce mai): 

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
            dfs(Neighbours,[Source],[],Graph,Source),
ok.


dfs([],Paths,Result,_Graph,Source) ->
    ?DBG("There are no more neighbours left for vertex ~w~n", [Source]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source) ->
    ?DBG("///The neighbour to check is ~w, other neighbours are: ~w~n",[Neighbour,Other_neighbours]),
    ?DBG("***Current result: ~w~n",[Result]),
    New_result = relax_neighbours(Neighbour,Paths,Result,Graph,Source),

        dfs(Other_neighbours,Paths,New_result,Graph,Source).


relax_neighbours(Neighbour,Paths,Result,Graph,Source) ->
     case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("Found an unvisited neighbour ~w, path is: ~w~n",[Neighbour,Paths]),
            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("The neighbours of the unvisited vertex ~w are ~w, path is:
                ~w~n",[Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,[Neighbour|Paths],Result,Graph,Source);
            true ->
                [Paths|Result]

        end.

<”UPD3:

Il problema è che il normale algoritmo di ricerca in profondità prima andrà prima su uno dei percorsi: (A, B, C, D) o (A, D, C, B) e non andrà mai sul secondo percorso.

In entrambi i casi sarà l'unico percorso - ad esempio, quando il DFS regolare torna indietro da (A, B, C, D) risale ad A e controlla se D (il secondo vicino di A) è visitato . E poiché il DFS regolare mantiene uno stato globale per ogni vertice, D avrebbe lo stato "visitato".

Quindi, dobbiamo introdurre uno stato dipendente dalla ricorsione: se torniamo indietro da (A, B, C, D) fino ad A, dovremmo avere (A, B, C, D) nell'elenco dei risultati e dovremmo avere D contrassegnato come non visitato come all'inizio dell'algoritmo.

Ho provato a ottimizzare la soluzione a quella ricorsiva in coda, ma il tempo di esecuzione dell'algoritmo è ancora irrealizzabile: ci vogliono circa 4 secondi per attraversare un piccolo grafico di 16 vertici con 3 bordi per vertice: 

dfs(Graph,Source) ->
    ?DBG("Started to traverse graph~n", []),
            Neighbours = digraph:out_neighbours(Graph,Source),
    ?DBG("Entering recursion for source vertex ~w~n", [Source]),
    Result = ets:new(resulting_paths, [bag]),
Root = Source,
            dfs(Neighbours,[Source],Result,Graph,Source,[],Root).


dfs([],Paths,Result,_Graph,Source,_,_) ->
    ?DBG("There are no more neighbours left for vertex ~w, paths are ~w, result is ~w~n", [Source,Paths,Result]),
    Result;

dfs([Neighbour|Other_neighbours],Paths,Result,Graph,Source,Recursion_list,Root) ->
    ?DBG("~w *Current source is ~w~n",[Recursion_list,Source]),
    ?DBG("~w Checking neighbour _~w_ of _~w_, other neighbours are: ~w~n",[Recursion_list,Neighbour,Source,Other_neighbours]),



?    DBG("~w Ready to check for visited: ~w~n",[Recursion_list,Neighbour]),

 case lists:member(Neighbour,Paths) of 
        false ->
            ?DBG("~w Found an unvisited neighbour ~w, path is: ~w~n",[Recursion_list,Neighbour,Paths]),
New_paths = [Neighbour|Paths],
?DBG("~w Added neighbour to paths: ~w~n",[Recursion_list,New_paths]),
ets:insert(Result,{Root,Paths}),

            Neighbours = digraph:out_neighbours(Graph,Neighbour),
            ?DBG("~w The neighbours of the unvisited vertex ~w are ~w, path is: ~w, recursion:~n",[Recursion_list,Neighbour,Neighbours,[Neighbour|Paths]]),
                dfs(Neighbours,New_paths,Result,Graph,Neighbour,[[[]]|Recursion_list],Root);
            true -> 
            ?DBG("~w The neighbour ~w is: already visited, paths: ~w, backtracking to other neighbours:~n",[Recursion_list,Neighbour,Paths]),
ets:insert(Result,{Root,Paths})

end,

        dfs(Other_neighbours,Paths,Result,Graph,Source,Recursion_list,Root).

Qualche idea per eseguirlo in tempi accettabili?

È stato utile?

Soluzione

Modifica: Ok ho capito ora, vuoi trovare tutti i percorsi semplici da un vertice in un grafo diretto. Quindi una ricerca approfondita con backtracking sarebbe adatta, come hai capito. L'idea generale è quella di andare da un vicino, poi andare da un altro (non uno che hai visitato) e continuare finché non raggiungi un vicolo cieco. Quindi torna indietro all'ultimo vertice in cui ti trovavi e scegli un vicino diverso, ecc. Devi sistemare bene le parti poco pronte, ma non dovrebbe essere troppo difficile. Per esempio. ad ogni passo è necessario etichettare i vertici "esplorati" o "inesplorati" a seconda che li abbiate già visitati prima. Le prestazioni non dovrebbero essere un problema, un algoritmo implementato correttamente dovrebbe richiedere forse O (n ^ 2) tempo. Quindi non so cosa stai sbagliando, forse stai visitando troppi vicini? Per esempio. forse stai rivisitando i vicini che hai già visitato e girando in loop o qualcosa del genere.

Non ho letto veramente il tuo programma, ma la pagina Wiki su Depth-first Search ha un breve e semplice programma in pseudocodice che puoi provare a copiare nella tua lingua. Memorizza i grafici come elenchi di adiacenza per renderlo più semplice.

Modifica: Sì, scusa, hai ragione, la ricerca DFS standard non funzionerà così com'è, è necessario regolarla leggermente in modo da rivisitare i vertici che ha visitato in precedenza. Quindi puoi visitare tutti i vertici tranne quelli che hai già memorizzato nel tuo percorso corrente. Questo ovviamente significa che il mio tempo di esecuzione è stato completamente sbagliato, la complessità del tuo algoritmo sarà alle stelle. Se la complessità media del tuo grafico è d + 1, allora ci saranno approssimativamente d * d * d * ... * d= d ^ n possibili percorsi. Quindi, anche se ogni vertice ha solo 3 vicini, ci sono ancora parecchi percorsi quando si supera i 20 vertici. Non c'è davvero modo di aggirarlo, perché se vuoi che il tuo programma esegua l'output di tutti i percorsi possibili, allora dovrai emetterli tutti d ^ n.

Mi interessa sapere se ne hai bisogno per un'attività specifica o se stai solo cercando di programmarlo per interesse. In quest'ultimo caso, dovrai solo accontentarti di grafici piccoli e scarsamente collegati.

Altri suggerimenti

Non capisco la domanda. Se ho il grafico G= (V, E)= ({A, B}, {(A, B), (B, A)}), ci sono infiniti percorsi da A a B {[A, B], [ A, B, A, B], [A, B, A, B, A, B], ...}. Come posso trovare tutti i possibili percorsi a qualsiasi vertice nel grafico ciclico?

Modifica:

Hai anche provato a calcolare o indovinare la crescita dei possibili percorsi per alcuni grafici? Se hai un grafico completamente connesso otterrai

  • 2 - 1
  • 3 - 4
  • 4 - 15
  • 5-64
  • 6 - 325
  • 7 - 1956
  • 8 - 13699
  • 9 - 109600
  • 10 - 986409
  • 11 - 9864100
  • 12 - 108505111
  • 13 - 1302061344
  • 14 - 16926797485
  • 15 - 236975164804
  • 16 - 3554627472075
  • 17 - 56874039553216
  • 18 - 966858672404689
  • 19 - 17403456103284420
  • 20 - 330665665962403999

Sei sicuro di voler trovare tutti i percorsi per tutti i nodi? Significa che se si calcola un milione di percorsi in un secondo, ci vorrebbero 10750 anni per calcolare tutti i percorsi a tutti i nodi in un grafo completamente connesso con 20 nodi. È il limite massimo per il tuo compito, quindi penso che non ti piacerebbe farlo. Penso che tu voglia qualcos'altro.

Non è affatto una soluzione algoritmica migliorata, ma spesso puoi migliorare le prestazioni generando più thread di lavoro, potenzialmente qui uno per ogni nodo di primo livello e quindi aggregando i risultati.Questo può spesso migliorare gli algoritmi di forza bruta ingenui in modo relativamente semplice.

Puoi vedere un esempio qui: Alcune funzioni della matrice di Erlang , nella funzione maximise_assignment (commenti a partire dalla riga 191 a partire da oggi).Di nuovo, l'algoritmo sottostante è abbastanza ingenuo e forza bruta, ma la parallelizzazione lo accelera abbastanza bene per molte forme di matrici.

Ho utilizzato un approccio simile in passato per trovare il numero di percorsi hamiltoniani in un grafico.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top