×

The complexity of the generalized cyclic Towers of Hanoi problem. (English) Zbl 0576.68036

Summary: This paper analyzes the generalized cyclic Towers of Hanoi problem. A directed state-space graph is used for representing states of discs and disc movements. Such a graph is then transformed to a shortest-path tree for making explicit all shortest paths for moving all discs in all possible states to a goal state. The best-case, the worst-case, and the average-case complexities are then given based on such a shortest-path tree.

MSC:

68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI