What's the fastest way to sample a random walk on a directed graph conditional on the start and end points?
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.
Hvala. Twitter će to iskoristiti za poboljšanje vaše vremenske crte. PoništiPoništi
-
Č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.