torres torre solucion psicologia hanoi discos algorithm haskell f# recursion functional-programming

algorithm - solucion - Torres de Hanoi con K clavijas



torres de hanoi en c (6)

El problema de Towers of Hanoi es un problema clásico para la recursión. Le dan 3 clavijas con discos en una de ellas, y debe mover todos los discos de una clavija a otra, siguiendo las reglas dadas. También debes hacer esto con la cantidad mínima de movimientos.

Aquí hay un algoritmo recursivo que resuelve el problema:

void Hanoi3(int nDisks, char source, char intermed, char dest) { if( nDisks > 0 ) { Hanoi3(nDisks - 1, source, dest, intermed); cout << source << " --> " << dest << endl; Hanoi3(nDisks - 1, intermed, source, dest); } } int main() { Hanoi3(3, ''A'', ''B'', ''C''); return 0; }

Ahora imagine el mismo problema, solo con 4 clavijas, por lo que agregamos otra clavija intermedia. Cuando nos enfrentemos al problema de tener que elegir qué par de intermediarios elegir en cualquier punto, elegiremos el más a la izquierda, en caso de que más de 1 sea gratuito.

Tengo el siguiente algoritmo recursivo para este problema:

void Hanoi4(int nDisks, char source, char intermed1, char intermed2, char dest) { if ( nDisks == 1 ) cout << source << " --> " << dest << endl; else if ( nDisks == 2 ) { cout << source << " --> " << intermed1 << endl; cout << source << " --> " << dest << endl; cout << intermed1 << " --> " << dest << endl; } else { Hanoi4(nDisks - 2, source, intermed2, dest, intermed1); cout << source << " --> " << intermed2 << endl; cout << source << " --> " << dest << endl; cout << intermed2 << " --> " << dest << endl; Hanoi4(nDisks - 2, intermed1, source, intermed2, dest); } } int main() { Hanoi4(3, ''A'', ''B'', ''C'', ''D''); return 0; }

Ahora, mi pregunta es ¿cómo podría generalizar este enfoque recursivo para trabajar con K clavijas? La función recursiva recibiría un char[] que contendría las etiquetas de cada pila, por lo que la función se vería así:

void HanoiK(int nDisks, int kStacks, char labels[]) { ... }

Sé sobre el algoritmo Frame-Stewart, que es muy probable que sea óptimo pero no probado, y que te da la cantidad de movimientos. Sin embargo, estoy interesado en una solución estrictamente recursiva que sigue el patrón de las soluciones recursivas para 3 y 4 clavijas, lo que significa que imprime los movimientos reales.

Para mí al menos, el pseudocódigo del algoritmo Frame-Stewart presentado en Wikipedia es bastante abstracto, y no he tenido éxito traduciéndolo en código que imprime los movimientos. Aceptaría una implementación de referencia de eso (para k aleatorio), o incluso un pseudocódigo más detallado.

Traté de encontrar algún tipo de algoritmo que permute el conjunto de etiquetas en consecuencia, pero no he tenido suerte en hacerlo funcionar. Cualquier sugerencia es apreciada

Actualizar:

Esto parece ser mucho más fácil de resolver en un lenguaje funcional. Aquí hay una implementación F # basada en la solución Haskell de LarsH:

let rec HanoiK n pegs = if n > 0 then match pegs with | p1::p2::rest when rest.IsEmpty -> printfn "%A --> %A" p1 p2 | p1::p2::p3::rest when rest.IsEmpty -> HanoiK (n-1) (p1::p3::p2::rest) printfn "%A --> %A" p1 p2 HanoiK (n-1) (p3::p2::p1::rest) | p1::p2::p3::rest when not rest.IsEmpty -> let k = int(n / 2) HanoiK k (p1::p3::p2::rest) HanoiK (n-k) (p1::p2::rest) HanoiK k (p3::p2::p1::rest) let _ = HanoiK 6 [1; 2; 3; 4; 5; 6]

Y sin tratar 3 clavijas como caso de borde:

let rec HanoiK n pegs = if n > 0 then match pegs with | p1::p2::rest when rest.IsEmpty -> printfn "%A --> %A" p1 p2 | p1::p2::p3::rest -> let k = if rest.IsEmpty then n - 1 else int(n / 2) HanoiK k (p1::p3::p2::rest) HanoiK (n-k) (p1::p2::rest) HanoiK k (p3::p2::p1::rest)

Tenga en cuenta que esto no maneja casos degenerados para los cuales no hay solución, como HanoiK 2 [1; 2] HanoiK 2 [1; 2]

Aquí hay una implementación en Haskell (actualización: se ocupó del caso de 3 pegas haciendo k = n-1 cuando r = 3):

-- hanoi for n disks and r pegs [p1, p2, ..., pr] hanoiR :: Int -> [a] -> [(a, a)] -- zero disks: no moves needed. hanoiR 0 _ = [] -- one disk: one move and two pegs needed. hanoiR 1 (p1 : p2 : rest) = [(p1, p2)] -- only needed for smart-alecks? {- -- n disks and 3 pegs -- unneeded; covered by (null rest) below. hanoiR n [p1, p2, p3] = hanoiR (n - 1) [p1, p3, p2] ++ [(p1, p2)] ++ hanoiR (n - 1) [p3, p2, p1] -} -- n disks and r > 3 pegs: use Frame-Stewart algorithm hanoiR n (p1 : p2 : p3 : rest) = hanoiR k (p1 : p3 : p2 : rest) ++ hanoiR (n - k) (p1 : p2 : rest) ++ hanoiR k (p3 : p2 : p1 : rest) where k | null rest = n - 1 | otherwise = n `quot` 2

Cargue esto en GHCi e ingrese

hanoiR 4 [1, 2, 3, 4]

Es decir, ejecuto las Torres de Hanoi con 4 discos y 4 clavijas. Puede nombrar las 4 clavijas lo que desee, por ejemplo

hanoiR 4 [''a'', ''b'', ''c'', ''d'']

La salida:

[(1,2),(1,3),(2,3),(1,4),(1,2),(4,2),(3,1),(3,2),(1,2)]

Es decir, mueva el disco superior de la clavija 1 a la clavija 2, luego el disco superior de la clavija 1 a la clavija 3, etc.

Soy bastante nuevo para Haskell, así que debo admitir que estoy orgulloso de que esto funcione. Pero puedo cometer errores tontos, así que los comentarios son bienvenidos.

Como puede ver en el código, la heurística para k es simplemente floor (n / 2). No he tratado de optimizar k, aunque n / 2 parecía una buena suposición.

Verifiqué la corrección de la respuesta para 4 discos y 4 clavijas. Es muy tarde en la noche para que pueda verificar más, sin escribir un simulador. (@ _ @) Aquí hay algunos resultados más:

ghci> hanoiR 6 [1, 2, 3, 4, 5] [(1,2),(1,4),(1,3),(4,3),(2,3),(1,4),(1,5),(1,2), (5,2),(4,2),(3,1),(3,4),(3,2),(4,2),(1,2)] ghci> hanoiR 6 [1, 2, 3, 4] [(1,2),(1,4),(1,3),(4,3),(2,3),(1,2),(1,4),(2,4),(1,2), (4,1),(4,2),(1,2),(3,1),(3,4),(3,2),(4,2),(1,2)] ghci> hanoiR 8 [1, 2, 3, 4, 5] [(1,3),(1,2),(3,2),(1,4),(1,3),(4,3),(2,1),(2,3),(1,3),(1,2), (1,4),(2,4),(1,5),(1,2),(5,2),(4,1),(4,2),(1,2), (3,2),(3,1),(2,1),(3,4),(3,2),(4,2),(1,3),(1,2),(3,2)]

¿Esto aclara el algoritmo?

Realmente la pieza esencial es

hanoiR k (p1 : (p3 : (p2 : rest))) ++ -- step 1; corresponds to T(k,r) hanoiR (n-k) (p1 : (p2 : rest)) ++ -- step 2; corresponds to T(n-k, r-1) hanoiR k (p3 : (p2 : (p1 : rest))) -- step 3; corresponds to T(k,r)

donde concatenamos las secuencias de movimientos para los pasos 1, 2 y 3 del algoritmo Frame-Stewart. Para determinar los movimientos, anotamos los pasos de FS de la siguiente manera:

  • Convencionalmente, cuando se llama a hanoi, el objetivo se define (sin pérdida de generalidad) como la transferencia de los discos de la primera vinculación a la segunda vinculación, utilizando todas las trazas restantes para el almacenamiento temporal. Utilizamos esta convención cuando se repiten, para definir la fuente, el destino y el almacenamiento permitido de los subproblemas divididos y conquistados.
  • Por lo tanto, la vinculación de origen es p1, y la vinculación de destino es p2. Todas las clavijas restantes están disponibles como almacenamiento temporal, para el problema de hanoi de nivel superior.
  • Paso 1, "Para algunos k, 1 <= k <n, transfiera los discos superiores k a una sola otra clavija": elegimos p3 como "una sola otra clavija".
  • Por lo tanto, "sin alterar la vinculación que ahora contiene los discos superiores k" (paso 2) significa recurse utilizando todas las clavijas, excepto p3. Es decir, p1, p2 y el resto más allá de p3.
  • "Transferir los mejores discos k a la clavija de destino" (paso 3) significa transferir de la "otra clavija" (p3) a p2.

¿Tiene sentido?

El rompecabezas de las Torres de Hanoi fue publicado en el mundo westren en 1883 por el matemático francés Edouard Lucas, bajo el seudónimo, N. Lucas de Siam. La "leyenda" que acompañó el juego declaró que en Benares, durante el reinado del emperador Fo Hi, había un templo indio con una cúpula que marcaba el centro del mundo (Kashi Vishwanath). Dentro de la cúpula, los sacerdotes (brahmanes) movían discos dorados entre 3 puntos de aguja de diamantes (postes desgastados), un codo de altura y tan gruesos como el cuerpo de una abeja. Dios (Brahma) colocó 64 discos de oro en una aguja en el momento de la creación. (Los discos se movieron de acuerdo con las leyes inmutables de Brahma para transferirlos de una clavija a otra). Se dijo que cuando completaran su tarea, el universo llegaría a su fin. La leyenda varía en varios sitios, pero en general es coherente. Las ''leyes'' establecidas por Brahma son como tales: 1) Solo se puede mover 1 disco a la vez 2) No se puede colocar ningún disco en un disco más pequeño 3) Solo se puede quitar el disco superior y luego colocarlo en la parte superior de otro clavija y sus discos El juego termina cuando toda la pila de discos se ha movido a otra clavija. Rápidamente se descubrió que la solución de 3 clavijas existe, pero no se resolvió para una solución de clavija de 4+. En 1939, el American Mathematical Monthly celebró una competencia para resolver por y m peg y n discos. Dos años más tarde, JS Frame y BM Stewart publicaron dos algoritmos separados (pero posteriormente probados iguales). Ambos aún no se han demostrado como correctos, aunque en general se los asume correctos. No ha habido avances aún en una solución adecuada. ***** Esto solo funciona en 3 problemas de clavija ***** El número mínimo de movimientos para una torre de n discos se demostró rápidamente que es 2n-1, con la solución recursiva simple de la siguiente manera: Etiquetar las tres clavijas de inicio , objetivo y temperatura Para mover n clavijas desde la clavija inicial a la clavija de la meta a través de la clavija temporal: Para n> 1, (i) mueva recursivamente los discos superiores n-1 de inicio a temperatura a través del objetivo. (ii) Mueva el enésimo disco desde el inicio hasta el objetivo. (iii) Mueva recursivamente los discos n-1 de la temperatura a la meta a través del inicio. Esta solución toma 2n-1 movimientos: (1) Si n = 1, f (n) = 1 = 2n-1 (2) Si n> 1, f (n) = 2 * (2n-1-1) +1 = 2n-2 + 1 = 2n-1 La manera fácil de resolverlo ... 1,3,7,15,31 son las soluciones para los primeros n discos. Recursivamente que se asemeja a nk = 2nk-1 + 1. A partir de ahí podemos inducir que n = 2n-1. Demostrando por inducción te dejo a ti. ***** el algoritmo básico de Frame / Stewart ***** Para m peg y n discos, elija un l tal que 0 ≤ l <n (mientras que l es un entero que minimiza los pasos en la siguiente configuración) .. • Mueva los discos superiores l desde la clavija inicial a una clavija intermedia; esto se puede lograr en movimientos Hk (l) (ya que los discos n-l inferiores no interfieren con los movimientos en absoluto). • Mueva los n - l discos inferiores desde la clavija de inicio a la clavija de objetivos usando movimientos Hk - 1 (n - l). (Debido a que una clavija está ocupada por una torre de discos más pequeños, no se puede usar en esta etapa). • Mueva los discos l originales de la clavija intermedia a la clavija de la meta en Hk (l) movimientos. Entonces, esencialmente, es Hk (n) = 2Hk (l) + Hk-1 (n-1) -----> el l minimizado ***** ¡¡Fácil como un pastel !! ¡No! ***** Verificar que funcione en contra de nuestra solución de 3 clavijas debería ser fácil. Usando k = 2; establecemos H2 (0) = 0, H2 (1) = 1 y H2 (n> 1) = ∞. Para k = 3, podemos establecer l = n-1. (Causa que nuestro H2 (n-1) se vuelva finito) Eso nos permitirá escribir H3 (n) = 2H3 (n-1) + H2 (1) que es igual a 2n-1. Es un juego de palabras, pero funciona. ***** Una descripción ligeramente diferente para ayudar a aclarar ***** El algoritmo de Frame-Stewart, que da una solución presumiblemente óptima para cuatro (o incluso más) clavijas, se describe a continuación: Defina H (n, m) para ser el número mínimo de movimientos necesarios para transferir n discos usando m clavijas El algoritmo se puede describir recursivamente: 1. Para algunos l, 1

`Option VBASupport 1 Option Explicit Dim n as double dim m as double dim l as double dim rx as double dim rxtra as double dim r as double dim x as double dim s1 as double dim s2 as double dim i as integer dim a () dim b () dim c () dim d () dim aa as double dim bb as double dim cc as double dim dd as double dim total as double Sub Hanoi on error goto errorhandler m=inputbox ("m# pegs=??") n=inputbox ("n# discs=??") x=-1 l=m-1 rx=1 s1=0 s2=0 aa=0 while n>rx x=x+1 r=(l+x)/(x+1) rx=r*rx wend rx=1 for i=0 to x-1 r=(l+i)/(i+1) rx=r*rx redim a (-1 to x) redim b (-1 to x) redim c (-1 to x) redim d (-1 to x) a(i)=rx b(i)=i bb=b(i) c(i)=rx-aa aa=a(i) cc=c(i) d(i)=cc*2^bb dd=d(i) s1=s1+dd next rxtra=n-aa s2=rxtra*2^(bb+1) total = 2*(s1+s2)-1 msgbox total exit sub errorhandler: msgbox "dang it!!" ''1, 3, 5, 9, 13, 17, 25, 33 first 8 answers for 4 peg ''16=161,25=577,32=1281,64=18433 End Sub`

Divulgación: estas fuentes se usaron para confirmar las respuestas y para algunos antecedentes del problema. Es difícil dar crédito exacto a dónde se debe porque se usaron varios sitios para verificar ... por lo que son todas las fuentes de muchas partes de la historia.

Hinze, Ralf. Perla funcional: La Tour D''Hanoi , http://www.comlab.ox.ac.uk/ralf.hinze/publications/ICFP09.pdf

Esta perla tiene como objetivo demostrar las ideas de la programación integral y proyectiva usando el rompecabezas Towers of Hanoi como ejemplo. El rompecabezas tiene su propia belleza, que esperamos exponer a lo largo del camino.

Para resolver las Torres de Hanoi, todo lo que necesitas hacer es:

El algoritmo Frame Stewart no es realmente tan complejo. Básicamente, debe mover una cierta cantidad de discos (por ejemplo, la mitad de ellos) a una clavija: trate estos discos como si fueran su propia torre separada. Es fácil definir la solución para 1 o 2 discos, y uno mueve la primera mitad a su destino, mueve la segunda mitad al lugar que necesita para terminar.

Puede segmentarlo continuamente si desea que sea más fácil escribir (el único caso especial que se convierte en 1) pero sin un número significativo de clavijas, no funcionará.

Además, si k >= 3 , puedes resolverlo exactamente como una torre de 3 torres de Hanoi simplemente ignorando el resto de las estacas, aunque eso no sería óptimo.