What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
If acyclic, go depth first from source and remove all edges that don't eventually lead to sink then walk randomly uniform over the edges sounds optimal? O(V + E) or something
-
-
I actually need it to work for acyclic graphs. Also, this won't produce the correct distribution because it doesn't penalize entering nodes that had a lot of dead end out-edges.
-
what distribution are you after? this is uniform over all complete paths (almost by def: you're removing all edges that aren't on a path, then splitting p mass at each branch)
- Još 4 druga odgovora
Novi razgovor -
Čini se da učitavanje traje već neko vrijeme.
Twitter je možda preopterećen ili ima kratkotrajnih poteškoća u radu. Pokušajte ponovno ili potražite dodatne informacije u odjeljku Status Twittera.