I'll take a top-down approach instead of Roger's bottom-up approach... I'm guessing that the problem has a bunch of constraints that you've not specified in your email (can't double-back, path can't crossover) and--most importantly--you have to start at (0,0) and end at (10,10), so stopping somewhere in the middle or getting trapped Tron-like by your own wall is not a solution. So if the probability of getting to (10,10) is 1 then the sum of the probabilities of all the legitimate routes has to sum to 1 (and if it doesn't, you've missed some).
Regards, Robert On Mon, Aug 18, 2008 at 11:19 AM, Owen Densmore <[EMAIL PROTECTED]> wrote: > Lately I've been puzzling on the intersection between computing/ > algorithms and mathematics. This lead me to look at: > Donald Knuth's Selected Papers on Computer Science > http://tinyurl.com/5zraag > > In it he has several great essays, one of which is: > Mathematics and Computer Science: Coping with Finiteness > In it he has a section > Counting the Paths on a Grid. > Here are some scanned images of figures he uses: > http://backspaces.net/temp/GridPath1.png > http://backspaces.net/temp/GridPath2.png > And better yet, here's a netlogo model: > http://backspaces.net/temp/GridPath/ > > 2 Questions/Puzzles I'd like to share with you: > 1 - The probability for each path is calculated by looking at the > possible choices at each point in the path. If you see a "3" at a > node, for example, the probability assigned to the next move is 1/3. > The total probability for a given path is the product of the > individual ones. > Question: how can I show that this forms a true probability > space? .. i.e. the sum of the probabilities for all possible paths is > 1.0. > 2 - (Mainly for geeks) My solution for the model is to use a > floodfill after each move to find the possible next moves. For such a > small space (11x11), this is not computationally intensive, but seems > a bit heavy handed. > Question: is there an algorithm that uses a simpler approach? > > -- Owen > > > > > ============================================================ > FRIAM Applied Complexity Group listserv > Meets Fridays 9a-11:30 at cafe at St. John's College > lectures, archives, unsubscribe, maps at http://www.friam.org >
============================================================ FRIAM Applied Complexity Group listserv Meets Fridays 9a-11:30 at cafe at St. John's College lectures, archives, unsubscribe, maps at http://www.friam.org
