Shortest paths in the Tower of Hanoi graph and finite automata

Details Shortest paths in the Tower of Hanoi graph and finite automata Shortest paths in the Tower of Hanoi graph and finite automata

2003-10-08

arxiv.org/abs/math/0310109v1

Mathematics

Combinatorics

15 pages, 6 figures

Scientific paper

We present efficient algorithms for constructing a shortest path between two states in the Tower of Hanoi graph, and for computing the length of the shortest path. The key element is a finite-state machine which decides, after examining on the average only 63/38 of the largest discs, whether the largest disc will be moved once or twice. This solves a problem raised by Andreas Hinz, and results in a better understanding of how the shortest path is determined. Our algorithm for computing the length of the shortest path is typically about twice as fast as the existing algorithm. We also use our results to give a new derivation of the average distance 466/885 between two random points on the Sierpinski gasket of unit side.

Affiliated with

Also associated with

No associations

Rating

Shortest paths in the Tower of Hanoi graph and finite automata does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Shortest paths in the Tower of Hanoi graph and finite automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Shortest paths in the Tower of Hanoi graph and finite automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-640929