Upload
pablo-burbano
View
138
Download
17
Embed Size (px)
DESCRIPTION
Descripcion de las Torres de Hanoi
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 <- raiz mientras nodos_abiertos != () { actual <- ColaTope(nodos_abiertos) /* Mete el tope de nodos_abiertos en actual */ ColaPop (nodos_abiertos) /* Elimina el tope de nodos_abiertos */ nodos_visitados <- nodos_visitados + actual si estado_final(actual) devolver actual si_no { hijos <- expandir(actual)
hijos <- hijos – nodos_visitados /* Elimina los nodos_visitados que halla en hijos*/
nodos_abiertos <- nodos_abiertos + hijos } } } //recibe un nodo y devuelve el conjunto de hijos que resultan //al aplicar los operadores definidos Funcion expandir(nodo) { hijos <- () Para cada Operador { hijo <- AplicarOperador(nodo, operador) si hijo hijos <- hijos + hijo }
devolver hijos }