Shortest paths in the Tower of Hanoi graph and finite automata

2003/10/08 by Dan Romik, Romik, Dan · 1 voice
Computer Science · Mathematics · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #cs.DM #math.CO #math.PR #msc:68W40 #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.math/0310109

15 pages, 6 figures

arxiv created 2003/10/08 · arxiv updated 2009/12/01

Abstract

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.

Discussions

• But be careful! By "distance", I mean the length of the shortest path moving inside the Sierpiński triangle, not the usual distance between points in the plane. Also: we compute the "average" distance [bsky, 11 points, 1 comments]

Related

• The Tower of Hanoi and finite automata
• The Tower of Hanoi problem on Path_h graphs
• Twin Towers of Hanoi
• Relations between automata and the simple k-path problem
• A Survey of Shortest-Path Algorithms