• Author / Uploaded
• Pablo Burbano Bravo

• Categories
• Matemáticas Aplicadas
• Áreas de informática
• Algoritmos
• Algoritmos y Estructuras de Datos
• Programación de computadoras

Citation preview

Torres de Hanoi Gonzalo Saavedra Postigo Francisco José Rubio Sánchez Sergio Ruiz Bens

1. Realiza una formulación adecuada del problema asignado - Espacio de Estados = (x1,y1),(x2,y2),(x3,y3) tal que xi € {A,B,C} yi € {1,2,3} donde cada par (xi,yi) hace referencia al palo y a la posición, para cada disco - Estado Inicial = (A,3), (A,2), (A,1) - Estado Final = (B,3), (B,2), (B,1) - Conjunto de Reglas 1.- Mover disco 1 al palo A, x1 != A =>(A, max(para todo yi / xi = A)+1),(x2,y2),(x3,y3) 2.- Mover disco 1 al palo B, x1 != B =>(B, max(para todo yi / xi = B)+1),(x2,y2),(x3,y3) 3.- Mover disco 1 al palo C, x1 != C =>(C, max(para todo yi / xi = C)+1),(x2,y2),(x3,y3) 4.- Mover disco 2 al palo A, x1 != A, x2 != A, x1 != x2 => (x1,y1),(A, max(para todo yi / xi = A)+1),(x3,y3) 5.- Mover disco 2 al palo B, x1 != B, x2 != B, x1 != x2 => (x1,y1),(B, max(para todo yi / xi = B)+1),(x3,y3) 6.- Mover disco 2 al palo C, x1 != C, x2 != C, x1 != x2 => (x1,y1),(C, max(para todo yi / xi = C)+1),(x3,y3) 7.- Mover disco 3 al palo A, x1 != A,x2 != A,x3 != A,x1 != x2,x2 != x3 => (x1,y1),(x2,y2)(A,max(para todo yi /xi = A)+1) 8.- Mover disco 3 al palo B,

x1 != B,x2 != B,x3 != B,x1 != x2,x2 != x3 => (x1,y1),(x2,y2)(B,max(para todo yi / xi = B)+1) 9.- Mover disco 3 al palo C, x1 != C,x2 != C,x3 != C,x1 != x2,x2 != x3 => (x1,y1),(x2,y2)(C,max(para todo yi / xi = C)+1) 2. Elige la resolución del problema mediante la aplicación de una de las 2 estrategias básicas de Búsqueda No Informada: Búsqueda Primero en Anchura Búsqueda Primero en Profundidad Describe detalladamente las posibles modificaciones que se realicen respecto a la estrategia básica: evitar caminos repetidos, cíclicos, etc. - Árbol de búsqueda en anchura

Los nodos que no se han expandido están repetidos.

La solución encontrada es: (A,3)(A,2),(A,1) -> (B,1)(A,2),(A,1) -> (B,1)(C,1),(A,1) -> (C,2)(C,1),(A,1) -> (C,2)(C,1),(B,1) -> -> (A,1)(C,1),(B,1) -> (A,1)(B,2),(B,1) -> (B,3)(B,2),(B,1) 3. Determina los parámetros b: factor de ramificación medido como el nº medio de sucesores de un nodo, d: profundidad de la mejor solución (entendida como la que menor nº de acciones genera), y si es posible, m: profundidad máxima de cualquier camino. Compara esta versión con la versión básica de la estrategia. b=3 d=7 m=7 Por lo que el orden de complejidad espacial-temporal será: O(3^8), ya que la complejidad temporal de 1º en anchura es O(b^(d+1)) y la complejidad en espacio es también O(b^(d+1)). 4. Diseña el algoritmo de la versión de la estrategia elegida con las mejoras aportadas y descritas en 2. Procedimiento busqueda_en_anchura() { nodos_abiertos