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.
- Još 5 drugih odgovora
Novi razgovor -
-
-
I haven't checked details but I think following works: Precompute P(ever reaches desired end given uniform walk) using linear algebra Beginning at start, walk sampling each node with weight proportional to the precomputed probability.
-
This should work. Certainly it gives you a random walk of the right type, and it produces the right answer for sure if all nodes have the same number of out edges (it's a Boltzmann sampler then) but like I say haven't checked details.
- Još 4 druga odgovora
Novi razgovor -
-
-
Assumption: this is an acyclic graph, and you want each path to have equal probability of occurring. Do a topological sort of the graph. Then, using this sorted order, use dynamic programming to label each node with the number of paths from that node to the destination node.
-
Finally, sample a path, choosing each node in the path randomly one-by-one. At each step, look at all the possible next nodes, and make the probability of choosing a certain next node proportional to the number on its label.
Kraj razgovora
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.