• Author / Uploaded
• david ortiz

Citation preview

GUIA DE LABORATORIO

Página

:

1 de 9

GUIA N° 05 Escuela Profesional: Ingeniería de Sistemas. Sección y Turno: VII, A1,C1 Docentes: Ing. Adin Velasco C. Ing. Maritza Cabana Cáceres

Asignatura: Sistemas Inteligentes Semestre Académico: 2020 - I

UNIDAD 1: PROCESAMIENTO DE IMÁGENES Y RESOLUCIÓN DE PROBLEMA. Sesión 5: Resolución de Problemas. Uso y aplicaciones de Librerías Scipy y MatplotLib de Python. # ----------# Ejercicio 1 # ----------# --------------------------------------------------------------------------# Definir la clase Ocho_Puzzle, que implementa la representación del # problema del 8-puzzle visto en clase. Para ello, completar el código que se # presenta a continuación, en los lugares marcados con interrogantes. # ---------------------------------------------------------------------------class Ocho_Puzzle(Problema): """Problema a del 8-puzzle. Los estados serán tuplas de nueve elementos, permutaciones de los números del 0 al 8 (el 0 es el hueco). Representan la disposición de las fichas en el tablero, leídas por filas de arriba a abajo, y dentro de cada fila, de izquierda a derecha. Por ejemplo, el estado final será la tupla (1, 2, 3, 8, 0, 4, 7, 6, 5). Las cuatroacciones del problema las representaremos mediante las cadenas: "Mover hueco arriba", "Mover hueco abajo", "Mover hueco izquierda" y "Mover hueco derecha", respectivamente.""""" def __init__(self,tablero_inicial): self.estado_inicial = tablero_inicial self.estado_final = (1, 2, 3, 8, 0, 4, 7, 6, 5) def acciones(self,estado): pos_hueco=estado.index(0) accs=list() if pos_hueco not in (0,1,2): accs.append("Mover hueco arriba") if pos_hueco not in (0,3,6): accs.append("Mover hueco izquierda") if pos_hueco not in (6,7,8): accs.append("Mover hueco abajo") if pos_hueco not in (2,5,8): accs.append("Mover hueco derecha") return accs def aplica(self,estado,accion): pos_hueco = estado.index(0) l = list(estado) if accion == "Mover hueco arriba": l[pos_hueco] = l[pos_hueco-3]

GUIA DE LABORATORIO

Página

:

2 de 9

l[pos_hueco-3] = 0 if accion == "Mover hueco abajo": l[pos_hueco] = l[pos_hueco+3] l[pos_hueco+3] = 0 if accion == "Mover hueco derecha": l[pos_hueco] = l[pos_hueco+1] l[pos_hueco+1] = 0 if accion == "Mover hueco izquierda": l[pos_hueco] = l[pos_hueco-1] l[pos_hueco-1] = 0 return tuple(l) # Ejemplos que se pueden ejecutar una vez se ha definido la clase: # >>> p8p_1 = Ocho_Puzzle((2, 8, 3, 1, 6, 4, 7, 0, 5)) # >>> p8p_1.estado_inicial # (2, 8, 3, 1, 6, 4, 7, 0, 5) # >>> p8p_1.estado_final # (1, 2, 3, 8, 0, 4, 7, 6, 5) # >>> p8p_1.acciones(p8p_1.estado_inicial) # ['Mover hueco arriba', 'Mover hueco izquierda', 'Mover hueco derecha'] # >>> p8p_1.aplica(p8p_1.estado_inicial,"Mover hueco arriba") # (2, 8, 3, 1, 0, 4, 7, 6, 5) # >>> p8p_1.coste_de_aplicar_accion(p8p_1.estado_inicial,"Mover hueco arriba") # 1

# ----------# Ejercicio 2 # -----------

GUIA DE LABORATORIO

Página

:

3 de 9

# Definir las dos funciones heurísticas para el 8 puzzle que se han visto en # clase. Es decir: # - h1_ocho_puzzle(estado): cuenta el número de casillas mal colocadas # respecto del estado final. # - h2_ocho_puzzle_estado(estado): suma la distancia Manhattan desde cada #casilla a la posición en la que debería estar en el estado final. # Ejemplos: # # # # # # # #

>>> 4 >>> 5 >>> 4 >>> 11

h1_ocho_puzzle((2, 8, 3, 1, 6, 4, 7, 0, 5)) h2_ocho_puzzle((2, 8, 3, 1, 6, 4, 7, 0, 5)) h1_ocho_puzzle((5,2,3,0,4,8,7,6,1)) h2_ocho_puzzle((5,2,3,0,4,8,7,6,1))

# -------------------------------------------------------------------------def h1_ocho_puzzle(estado): estado_final = (1,2,3,8,0,4,7,6,5) l = sum ([1 for i in range(9) if estado[i] == estado_final[i]]) return l def posiciones(estado): '''Función auxiliar que determina las coordenadas de la tupla estado en una mátrix''' l = list() for i in estado: indice = estado.index(i) if indice in (0,1,2): l.append((i,0,estado.index(i)%3)) if indice in (3,4,5): l.append((i,1,estado.index(i)%3)) if indice in (6,7,8): l.append((i,2,estado.index(i)%3)) return l def h2_ocho_puzzle(estado): estado_final = (1,2,3,8,0,4,7,6,5) final_pos = posiciones(estado_final) estado_pos = posiciones(estado) t = 0 for i in final_pos: for j in range(9): if estado_pos[j][0] == i[0] and i[0]!=0: t+= abs(i[1]-estado_pos[j][1]) t+= abs(i[2]-estado_pos[j][2]) return t

#============ # Ejercicio 4 #============

GUIA DE LABORATORIO

Página

:

4 de 9

# Resolver usando búsqueda_coste:uniforme, búsqueda_primero_el_mejor y # búsqueda_a_estrella (con las dos heurísticas), el problema del 8 puzzle para # el siguiente estado inicial: # # # # # # #

+---+---+---+ | 2 | 8 | 3 | +---+---+---+ | 1 | 6 | 4 | +---+---+---+ | 7 | H | 5 | +---+---+---+

# >>> puzzle = Ocho_Puzzle((2,8,3,1,6,4,7,0,5)) # >>> busqueda_coste_uniforme(puzzle).solucion() # ['Mover hueco arriba', 'Mover hueco arriba', 'Mover hueco izquierda', 'Mover hueco abajo', 'Mover hueco derecha'] class Problema_con_Analizados(Problema): """Es un problema que se comporta exactamente igual que el que recibe al inicializarse, y además incorpora unos atributos nuevos para almacenar el número de nodos analizados durante la búsqueda. De esta manera, no tenemos que modificar el código del algoritmo de búsqueda.""" def __init__(self, problema): self.estado_inicial = problema.estado_inicial self.problema = problema self.analizados = 0 def acciones(self, estado): return self.problema.acciones(estado) def aplica(self, estado, accion): return self.problema.aplica(estado, accion) def es_estado_final(self, estado): self.analizados += 1 return self.problema.es_estado_final(estado) def coste_de_aplicar_accion(self, estado, accion): return self.problema.coste_de_aplicar_accion(estado,accion)

def resuelve_ocho_puzzle(estado_inicial, algoritmo, h=None): """Función para aplicar un algoritmo de búsqueda dado al problema del ocho puzzle, con un estado inicial dado y (cuando el algoritmo lo necesite) una heurística dada. Ejemplo de uso: >>> resuelve_ocho_puzzle((2, 8, 3, 1, 6, 4, 7, 0, 5),búsqueda_a_estrella,h2_ocho_puzzle)

GUIA DE LABORATORIO

Página

:

5 de 9

Solución: ['Mover hueco arriba', 'Mover hueco arriba', 'Mover hueco izquierda', 'Mover hueco abajo', 'Mover hueco derecha'] Algoritmo: búsqueda_a_estrella Heurística: h2_ocho_puzzle Longitud de la solución: 5. Nodos analizados: 7 """ p8p=Problema_con_Analizados(Ocho_Puzzle(estado_inicial)) sol= (algoritmo(p8p,h).solucion() if h else algoritmo(p8p).solucion()) print("Solución: {0}".format(sol)) print("Algoritmo: {0}".format(algoritmo.__name__)) if h: print("Heurística: {0}".format(h.__name__)) else: pass print("Longitud de la solución: {0}. Nodos analizados: {1}".format(len(sol),p8p.analizados))

#============ # Ejercicio 5 #============

GUIA DE LABORATORIO

Página

:

6 de 9

# Intentar resolver usando las distintas búsquedas y en su caso, las distintas # heurísticas, el problema del 8 puzzle para los siguientes estados iniciales: # # # # # # # # # # # # # #

E1

E2

E3

E4

+---+---+---+ | 2 | 8 | 3 | +---+---+---+ | 1 | 6 | 4 | +---+---+---+ | 7 | H | 5 | +---+---+---+

+---+---+---+ | 4 | 8 | 1 | +---+---+---+ | 3 | H | 2 | +---+---+---+ | 7 | 6 | 5 | +---+---+---+

+---+---+---+ | 2 | 1 | 6 | +---+---+---+ | 4 | H | 8 | +---+---+---+ | 7 | 5 | 3 | +---+---+---+

+---+---+---+ | 5 | 2 | 3 | +---+---+---+ | H | 4 | 8 | +---+---+---+ | 7 | 6 | 1 | +---+---+---+

Se pide, en cada caso, hacerlo con la función resuelve_ocho_puzzle, para obtener, además de la solución, la longitud (el coste) de la solución obtenida y el número de nodos analizados. Anotar los resultados en la siguiente tabla (L, longitud de la solución, NA, nodos analizados), y justificarlos con las distintas propiedades teóricas estudiadas.

# ---------------------------------------------------------------------------------------# E1 E2 E3 E4 # Anchura L= # NA=

L=

L=

L=

NA=

NA=

NA=

# Profundidad L= # NA=

L=

L=

L=

NA=

NA=

NA=

# Coste uniforme L= # NA=

L=

L=

L=

NA=

NA=

NA=

# Primero el mejor (h1) L= # NA=

L=

L=

L=

NA=

NA=

NA=

# Primero el mejor (h2) L= # NA=

L=

L=

L=

NA=

NA=

NA=

GUIA DE LABORATORIO

Página

# A* (h1) L= # NA=

L=

L=

L=

NA=

NA=

NA=

# A* (h2) L= # NA=

L=

L=

L=

NA=

NA=

NA=

:

7 de 9

# ---------------------------------------------------------------------------------------#============ # Ejercicio 6 #============ # La siguiente heurística h3_ocho_puzzle se obtiene sumando a la heurística # h2_ocho_puzzle una componente que cuantifica la "secuencialidad" en las # casillas de un tablero, al recorrerlo en el sentido de las aguas del reloj # ¿Es h3 admisble? Comprobar cómo se comporta esta heurística cuando se usa en # A*, con cada uno de los estados anteriores. Comentar los resultados. def h3_ocho_puzzle(estado): suc_ocho_puzzle ={0: 1, 1: 2, 2: 5, 3: 0, 4: 4, 5: 8, 6: 3, 7: 6, 8: 7} def secuencialidad_aux(estado,i): val=estado[i] if val == 0: return 0 elif i == 4: return 1 else: i_sig=suc_ocho_puzzle[i] val_sig = (val+1 if val