Tours de Hanoi mais avec configuration initiale et finale arbitraire

Récemment, je suis tombé sur ce problème , une variante des tours de hanoi .

Énoncé du problème:

Considérez la variation suivante du problème bien connu des tours de Hanoi:

On nous donne tours et m disques de tailles 1 , 2 , 3 , … , m empilés sur certaines tours. Votre objectif est de transférer tous les disques vers la k ème tour en aussi peu de mouvements que vous pouvez gérer, mais en tenant compte des règles suivantes:$n$$1,2,3,\dots,m$$k^{\text{th}}$

• déplacer un seul disque à la fois,
• ne jamais déplacer un disque plus gros sur un plus petit,
• se déplaçant uniquement entre les tours à distance au plus .$d$

(Limites dans le problème d'origine: et m ≤ 100. Nombre de cas de test ≤ 1000. Vous pouvez supposer que tous les problèmes peuvent être résolus en pas plus de 20000 mouvements.)$3 \le n \le 1000$$m \le 100$$\le 1000$$20000$

C'est intéressant. Le problème des tours classiques de hanoi a une source, une destination et une tour temporaire qui sont utilisées pour déplacer les disques de la source à la destination. Le problème posé sur ce site a essentiellement une configuration initiale et finale.

Comment aborder ce problème?

L'approche la plus efficace pour gérer la version originale des tours de Hanoi consiste à utiliser des bases de données de modèles (PDB). L'état actuel de la technique est décrit dans " Progrès récents dans la recherche heuristique: une étude de cas du problème des tours à quatre chevilles de Hanoi "

$t$

$d$

Je ne vois, en effet, aucune raison de changer l'approche typique juste au vu de cette contrainte particulière.

J'espère que cela t'aides,