Cos'è un algoritmo veloce e stabile per un percorso casuale in un grafo di nodi?

Question

Ho un grafico costituito da nodi e ho bisogno di un algoritmo veloce che generi un percorso casuale tra due nodi. Ho progettato diversi algoritmi da zero per questo, ma non riesco a farlo bene.

O l'algoritmo si blocca nei loop, o quando tengo la registrazione dei nodi visitati a volte si blocca tra i nodi visitati. Un altro problema che ho riscontrato è che il mio algoritmo era troppo instabile nelle prestazioni.

Quindi la mia domanda è; qualcuno conosce un algoritmo veloce e stabile per un percorso casuale tra due nodi raggiungibili in un grafo non orientato?

Answer 1

Lascia che il grafico sia G=(V,E). Creare un sottoinsieme U di V tale che U = { u | there is a path from u to the target }.

• Nota che trovare questo sottoinsieme U è facile - e può essere fatto in tempo lineare utilizzando DFS o BFS sui bordi stornate dal bersaglio.

Utilizzando questo sottoinsieme, creare un grafico G'=(U,E') dove U è definito sopra e E' = E [intersection] UxU [I bordi stessi, ma applicati soltanto sui vertici in U].

Esegui in modo casuale (scegliendo il vertice da esplorare in ordine casuale) DFS su G' fino a raggiungere il target.

• Nota - l'idea è quella di trovare una via - non necesseraly semplice, e quindi non si dovrebbe mantenere una serie visited.
• Si potrebbe aggiungere una "regola di interruzione" che se raggiungi una certa profondità, cercherai il bersaglio - non randomizzato, per evitare loop infiniti nelle cerchie.
• perofrmance dovrebbe essere diversa, dal momento che è lineare nella lunghezza del percorso trovato, che potrebbe essere molto lungo o molto breve ...

Answer 2

Dipende da cosa si intende per casuale. Se non ti interessa cosa significa, hai provato un monte-carlo method?

Il mio pugnale selvaggio nel buio, pseudo-codice, assumendo che il bersaglio sia raggiungibile a tutti e che tu abbia un grafo non orientato.

1. s <- start node 
2. Choose a random neighbor of s, call that neighbor n. 
3. Add the edge from s to n to the path. 
4. Set s <- n. 
5. Go to 2, unless you've reached the target. 

Gli avvertimenti di amit tengono anche qui:

• Si potrebbe aggiungere una "regola di rottura" che se si raggiunge una certa profondità, si cercherà il target - unrandomised, per evitare cicli infiniti in cerchi.
• perofrmance dovrebbe essere diversa, dal momento che è lineare nella lunghezza del percorso trovato, che potrebbe essere molto lungo o molto breve ...

Answer 3

Se ho capito bene la tua domanda, si sta cercando di generare un uniform spanning tree.