Shortest Paths in the Tower of Hanoi Graph and Finite Automata
Shortest Paths in the Tower of Hanoi Graph and Finite Automata
We present efficient algorithms for constructing a shortest path between two configurations 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 a small number of the largest discs (asymptotically, ā¦