Recientemente, me encontré con este problema , una variación de las torres de Hanoi .
Planteamiento del problema:
Considere la siguiente variación del conocido problema Towers of Hanoi:
Se nos dan torres ym discos de tamaños 1 , 2 , 3 , ... , m apilados en algunas torres. Su objetivo es transferir todos los discos a la k ª torre en el menor número de movimientos que se pueden gestionar, pero teniendo en cuenta las siguientes reglas:
- moviendo solo un disco a la vez,
- nunca mover un disco más grande a uno más pequeño,
- moverse solo entre torres a distancia como máximo .
(Límites en el problema original: y m ≤ 100 Número de casos de prueba. Leq 1,000 Se puede suponer que todos los problemas se pueden resolver en no más de. 20 000 se mueve.)
Es interesante El problema de las torres clásicas de Hanoi tiene una fuente, un destino y una torre temporal que se utiliza para mover los discos de origen a destino. El problema lanzado en ese sitio básicamente tiene una configuración inicial y final.
¿Cómo se aborda este problema?
Respuestas:
El enfoque más exitoso para lidiar con la versión original de las Torres de Hanoi es usar las bases de datos de patrones (PDB). El estado actual de la técnica se describe en " Progreso reciente en la búsqueda heurística: un estudio de caso del problema de las cuatro clavijas de Hanoi "
De hecho, no veo ninguna razón para cambiar el enfoque típico solo en vista de esta restricción particular.
Espero que esto ayude,
fuente