Algoritmo Torres de Hanoi generalizado

LOc0

Buenas noches. Voy al grano. ¿Tiene alguien por ahí un algoritmo (el lenguaje es igual) para resolver las Torres de Hanoi (mínimo de movimientos) con las siguientes condiciones?:

a) de 1 a 8 discos

b) de 3 a 5 ejes

c) posición inicial y final de los discos arbitraria ( esta es la parte "jodida" ).

Gracias.

Salu2 ;)

Ninja-Killer

http://html.rincondelvago.com/las-torres-de-hanoi.html

http://www.lawebdelprogramador.com/codigo/C_Visual_C/341-Torres_de_Hanoi_en_C++_(Algoritmo_recursivo).html

1 respuesta
LOc0

Gracias por el intento #2, pero esos enlaces son del juego "clásico" de 3 ejes.

Salu2 ;)

Khanser

Creo que necesitas el algoritmo min-max con poda alfa-beta ajustando una funcion heurística que mejora cuando los discos estan en su posicion 'buena'.

Teniendo en cuenta que los nodos de juego a los que se le puede aplicar la función heurística representan el estado de los discos en los palos.

La función heurística devolverá un valor inicial que se irá incrementando por cada disco si éste tiene encima uno más pequeño si el primer disco de palo es el más grande que se puede emplazar.

Yo empezaria probando por ahí, e iría modificando la función heurística. Intenta optimizar ésta función al máximo :)

1 respuesta
LOc0

#4 Gracias por la respuesta. No sé yo si con heurística sacaría la solución con número de movimientos mínimo... Había pensando en calcular el recorrido mínimo en el grafo de estados, pero para más de 3 ejes el grafo se vuelve muy tocho...

Seguiré pensando...

Salu2 ;)

1 respuesta
Khanser

#5 Claro que se vuelve tocho, de ahí que se pode XD Con una buena heurística lo tienes todo hecho :)
Si usas la heuristica como bueno/malo es normal que se vuelva muy tocho, en vez de blanco/negro tienes que hacer que la funcion heuristica te de una escala de grises, ahí es cuando empezará a podar el jardinero y se quedará a gusto xD

1 respuesta
ItNaS

De la wikipedia:

Four pegs and beyond

Although the three-peg version has a simple recursive solution as outlined above, the optimal solution for the Tower of Hanoi problem with four pegs (called Reve's puzzle), let alone more pegs, is still an open problem. This is a good example of how a simple, solvable problem can be made dramatically more difficult by slightly loosening one of the problem constraints.

LOc0

#5 No sé yo si hablamos de lo mismo jeje...

#6 Existe un algoritmo http://en.wikipedia.org/wiki/Tower_of_Hanoi#Frame.E2.80.93Stewart_algorithm que se conjetura es eficiente aunque no ha sido demostrado matemáticamente (se ha probado hasta 30 discos que lo es, pero a partir de ahí no se puede asegurar). La cosa sería adaptar ese algoritmo para una posición inicial y final arbitrarias. Será cuestión de pensar porque el problema me consta que es solucionable.

Gracias por las respuestas.

Salu2 ;)

Usuarios habituales

  • LOc0
  • ItNaS
  • Khanser
  • Ninja-Killer