The weighted Tower of Hanoi
This work generalizes a classic puzzle to a cost-based setting, providing an optimal algorithm and linking it to move-restriction variants, but it is an incremental extension of known dynamic programming approaches.
The authors introduce the weighted Tower of Hanoi, a generalization where moving a disc between pegs has a cost, and present an optimal dynamic programming algorithm to find the minimum-cost solution.
The weighted Tower of Hanoi is a new generalization of the classical Tower of Hanoi problem, where a move of a disc between two pegs $i$ and $j$ is weighted by a positive real $w_{ij}\geq 0$. This new problem generalizes the concept of finding the minimum number of moves to solve the Tower of Hanoi, to find a sequence of moves with the minimum total cost. We present an optimal dynamic algorithm to solve the weighted Tower of Hanoi problem, we also establish some properties of this problem, as well as its relation with the Tower of Hanoi variants that are based on move restriction.