Is there an easy algorithm to
a) count the number of equivalent shortest paths on a manhattan grid
b) enumerate them systematically?
I wrote a dumb random algo and I could run it for a long time to count unique paths but I imagine there's a closed-form solution?
Conversation
Replying to
Subdivide the problem. Path from start to segment start. Path from segment end to end.
2
2
Replying to
i think this decomposes as the product of two full sub-blocks and reduces to the earlier problem.
1
2
Replying to
Before you can get any further, you have to define "making random choices"...
90% of the confusion thinking about stochastic problems boils down to not specifying the EXACT measure of interest.
1
Replying to
By now you know that there are (M+N)! /(M! N!) paths from A to B.
Every path that does not pass the box, will pass exactly one crossed point (see drawing), call it C.
You can count the paths from A to B through C using the formula, take the sum over all such point C, et voilà
1
1
Replying to
The stationary distribution of an unweighted random walk on a graph is proportional to the degree of each node. Specifically the probability of being in node i is the degree of the node divided by twice the number of edges in the graph.
1
1





