Torres de Hanoi pero con configuración arbitraria inicial y final

11

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:n1,2,3,,mkth

  • 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 .d

(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.)3n1000m100100020000

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?

Nulo
fuente
44
¿Sería capaz de escribir el problema en la pregunta, para que la pregunta quede sola desde el enlace?
Luke Mathieson el
2
Además, ¿qué has probado? ¿Está familiarizado con las soluciones a los problemas originales y ha tratado de adaptarlos?
Raphael
3
>5001000
Si olvida la restricción de la distancia a lo sumo d, entonces esto me parece lo mismo que el rompecabezas de Reve, que tiene la solución no probada del algoritmo Frame-Stewart descrita en esta página wiki . Intuitivamente, agregar esta restricción hace que las cosas sean aún más complicadas.
Ciro Santilli 冠状 病毒 审查 六四 事件 法轮功

Respuestas: