Laboratorio 3 Busqueda PDF

Preview

Summary

metodos de busqueda en la inteligencia artificial...

Description

Laboratorio Nº 3 – Algoritmos de Búsqueda Asignatura

Inteligencia Artificial

Profesor

José Carlos Rangel Ortiz

Tema

Algoritmos de Búsqueda con Python

Código

8452

Recursos  

Computadora con Python instalado Guía de Laboratorio

Entregables   

Informe de laboratorio con las respuestas a las preguntas planteadas en cada parte del laboratorio Subir el informe a la plataforma Moodle en formato PDF Nombrar el archivo siguiendo el formato de nombres especificado por el Docente

La Inteligencia Artificial y las Técnicas de Búsqueda Informadas y No Informadas. La Inteligencia Artificial es al día de hoy una herramienta que está ayudando a afrontar la solución de problemas usando un enfoque muy distinto al de la computación clásica. Está basada en un conjunto de técnicas que por sí solas o en combinación con otras nos ayudarán a encontrar una solución (no necesariamente la mejor) a un problema cuya resolución es compleja e incluso inabordable por una persona humana. La resolución de problemas mediante la búsqueda de una solución en el espacio de posibles estados en los que puede encontrarse el problema es una de las primeras áreas en las que la Inteligencia Artificial comenzó a trabajar, puesto que su ligación con las matemáticas y su naturaleza más relacionada con el problema en sí mismo que con los mecanismos de la mente, la hacían más abordable. Para construir un sistema que resuelva un problema específico, es necesario realizar estas cuatro acciones:    

Definir el problema con precisión. La definición debe incluir especificaciones precisas tanto sobre las situaciones iniciales como sobre las situaciones finales que se aceptarían como soluciones al problema. Analizar el problema. Algunas características de gran importancia pueden tener un gran efecto sobre la conveniencia o no de utilizar diversas técnicas que resuelvan el problema. Aislar y representar el conocimiento necesario para resolver el problema. Elegir la mejor técnica que resuelva el problema y aplicarla al problema particular.

Inteligencia Artificial | Laboratorio 3

I.

Técnicas de Búsqueda No informadas

Son aquellas técnicas donde el problema a resolver no ofrece ninguna información adicional que nos ayude a encontrar una solución de formas rápida, más allá de la que proporciona el propio enunciado. Son técnicas de búsqueda a ciegas o a fuerza bruta. A continuación se presente la clase arbol.py que se utilizará en los siguientes problemas

2

Inteligencia Artificial | Laboratorio 3

Algoritmo de Búsqueda en Anchura Este tipo de búsqueda consiste en ir explorando el árbol por ramas del mismo nivel, es decir, no se podrá explorar una rama superior si la rama inferior no se ha explorado por completo. A continuación se plantea unos problemas propuestos en Python para demostrar el algoritmo de búsqueda en anchura. Copie el código de Python y analice los resultados de acuerdo al algoritmo basado en búsqueda en anchura. Se plantea que el algoritmo resuelva el siguiente problema propuesto.  

Problema a Resolver [4,2,3,1] Solución al Problema [1,2,3,4]

A continuación se presenta la el código en Python de puzzlelineal_bfs.py (Búsqueda en Anchura) para resolver el problema propuesto. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. #Puzzle Lineal con búsqueda en amplitud def buscar_solucion_BFS(estado_inicial, solucion): solucionado=False nodos_visitados=[] nodos_frontera=[] nodoInicial = Nodo(estado_inicial) while (not solucionado) and len(nodos_frontera)!=0: nodo=nodos_frontera.pop(0) #extraer nodo y añadirlo a visitados nodos_visitados.append(nodo) if nodo.get_datos() == solucion: #solucion encontrada solucionado=True return nodo else: #expandir nodo hijo dato_nodo = nodo.get_datos() #operador izquierdo hijo=[dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]] if not hijo_izquierdo.en_lista(nodos_visitados) and not hijo_izquierdo.en_lista(nodos_frontera): nodos_frontera.append(hijo_izquierdo) #operador central hijo=[dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]] hijo_central = Nodo(hijo) if not hijo_central.en_lista(nodos_visitados) and not hijo_central.en_lista(nodos_frontera): nodos_frontera.append(hijo_central) #operador derecho hijo=[dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]] hijo_derecho = Nodo(hijo) if not hijo_derecho.en_lista(nodos_visitados) and not hijo_derecho.en_lista(nodos_frontera): nodos_frontera.append(hijo_derecho)

if __name__ == "__main__": estado_inicial=[4,2,3,1] nodo_solucion = buscar_solucion_BFS(estado_inicial, solucion) #mostrar resultado

3

Inteligencia Artificial | Laboratorio 3

resultado=[] nodo=nodo_solucion while nodo.get_padre() !=None: resultado.append(nodo.get_datos()) nodo = nodo.get_padre() resultado.append(estado_inicial) resultado.reverse()

Preguntas Propuestas al Problema Propuesto: 1. ¿Cuántas líneas de código fueron necesarias completar en el código? 2. Verifique si la salida del algoritmo corresponde a los siguientes movimientos de estados. Movimiento de Estados=[[4, 2, 3, 1], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [2, 1, 3, 4], [1, 2, 3, 4]] 3. ¿Cuál son los movimientos estados para resolver el siguiente estado inicial? Estado inicial=[3,1,4,2] 4. ¿Cuál sería el estado inicial pasado al algoritmo para generar el siguiente movimiento de estado=[[2, 1, 4, 3], [1, 2, 4, 3], [1, 2, 3, 4]] y llegar a la salida deseada?

5. Analice el funcionamiento del algoritmo para la estrategia de búsqueda en profundidad.

4

Inteligencia Artificial | Laboratorio 3

Algoritmo de Búsqueda en Profundidad A continuación se presenta la el código en Python de puzzlelineal_dfs.py (Búsqueda en Profundidad) para resolver el problema propuesto. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. #Puzzle Lineal con búsqueda en Profundidad from arbol import Nodo def buscar_solucion_DFS(estado_inicial, solucion): while (not solucionado) and len(nodos_frontera)!=0: nodo=nodos_frontera.pop() #extraer nodo y añadirlo a visitados nodos_visitados.append(nodo) if nodo.get_datos() == solucion: #solucion encontrada solucionado=True return nodo else: #expandir nodo hijo dato_nodo = nodo.get_datos() #operador izquierdo if not hijo_izquierdo.en_lista(nodos_visitados) and not hijo_izquierdo.en_lista(nodos_frontera): nodos_frontera.append(hijo_izquierdo) #operador central hijo=[dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]] hijo_central = Nodo(hijo) if not hijo_central.en_lista(nodos_visitados) and not hijo_central.en_lista(nodos_frontera): nodos_frontera.append(hijo_central) #operador derecho hijo=[dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]] hijo_derecho = Nodo(hijo) if not hijo_derecho.en_lista(nodos_visitados) and not hijo_derecho.en_lista(nodos_frontera): nodos_frontera.append(hijo_derecho) nodo.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho]) if __name__ == "__main__": estado_inicial=[2,4,1,3] solucion=[1,2,3,4] #mostrar resultado resultado=[] nodo=nodo_solucion while nodo.get_padre() !=None: resultado.append(nodo.get_datos()) nodo = nodo.get_padre() resultado.append(estado_inicial) resultado.reverse() print (resultado)

5

Inteligencia Artificial | Laboratorio 3

Preguntas Propuestas al Problema Propuesto: 6. ¿Cuántas líneas de código fueron necesarias completar en el código? 7. ¿Cuál es la diferencia en el código del algoritmo de búsqueda en profundidad vs el algoritmo de búsqueda en anchura? 8. Verifique si la salida del algoritmo corresponde a los siguientes movimientos de estados. Movimiento de Estados =[[4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [4, 3, 1, 2], [4, 1, 3, 2], [1, 4, 3, 2], [1, 4, 2, 3], [1, 2, 4, 3], [1, 2, 3, 4]] 9. ¿Cuál son los movimientos estados para resolver el siguiente estado inicial? Estado inicial=[1,4,2,3] 10. Cuál es el Estado Inicial, pasado al algoritmo, para el siguiente movimiento de estados: [[4, 1, 3, 2], [4, 1, 2, 3], [4, 2, 1, 3], [4, 2, 3, 1], [4, 3, 2, 1], [3, 4, 2, 1], [3, 4, 1, 2], [3, 1, 4, 2], [3, 1, 2, 4], [3, 2, 1, 4], [2, 3, 1, 4], [2, 1, 3, 4], [1, 2, 3, 4]]? 11. Analice el funcionamiento del algoritmo para la estrategia de búsqueda en Anchura.

6

Inteligencia Artificial | Laboratorio 3

Problema Propuesto: Conexiones de Vuelos para España

7

Inteligencia Artificial | Laboratorio 3

Algoritmos de Búsqueda en Anchura A continuación se presenta la el código en Python de vuelos_bfs.py (Búsqueda en Anchura) para resolver el problema propuesto. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. # Vuelos con busqueda en amplitud from arbol import Nodo def buscar_solucion_BFS(conexiones, estado_inicial, solucion): solucionado=False nodos_visitados=[] nodos_frontera=[] nodoInicial = Nodo(estado_inicial) nodos_frontera.append(nodoInicial) while (not solucionado) and len(nodos_frontera)!=0: else: # expandir nodos hijo (ciudades con conexión) dato_nodo = nodo.get_datos() lista_hijos=[] for un_hijo in conexiones[dato_nodo]: hijo=Nodo(un_hijo) lista_hijos.append(hijo) if not hijo.en_lista(nodos_visitados) \ and not hijo.en_lista(nodos_frontera): nodos_frontera.append(hijo) nodo.set_hijos(lista_hijos) if __name__ == "__main__": conexiones = { 'Malaga':{'Salamanca', 'Madrid', 'Barcelona'}, 'Sevilla':{'Santiago', 'Madrid'}, 'Granada':{'Valencia'}, 'Valencia':{'Barcelona'}, 'Madrid':{'Salamanca', 'Sevilla', 'Malaga', 'Barcelona', 'Santander'}, 'Salamanca':{'Malaga', 'Madrid'}, 'Santiago':{'Sevilla', 'Santander', 'Barcelona'}, 'Santander':{'Santiago', 'Madrid'}, 'Zaragoza':{'Barcelona'}, 'Barcelona':{'Zaragoza', 'Santiago', 'Madrid', 'Malaga', 'Valencia'} } estado_inicial='Malaga' solucion='Santiago' nodo_solucion = buscar_solucion_BFS(conexiones, estado_inicial, solucion) # mostrar resultado resultado=[] nodo=nodo_solucion resultado.append(estado_inicial) resultado.reverse() print (resultado)

8

Inteligencia Artificial | Laboratorio 3

Preguntas Propuestas al Problema Propuesto: 12. ¿Cuántas líneas de código fueron necesarias completar en el código? 13. Verifique si la salida del algoritmo corresponde a los siguientes movimientos de estados (transbordo). Movimiento de Estados = ['Malaga', 'Barcelona', 'Santiago'] 14. ¿Cuáles son los movimientos estados (trasbordo) para llegar a la ciudad destino, desde el aeropuerto de origen? Origen=[Valencia] Destino = ['Santiago'] 15. Dado el estado inicial (aeropuerto de origen) y el objetivo (aeropuerto destino), pruebe en el algoritmo cuántos transbordos son necesarios Origen=[Granada] Destino = [Salamanca] Habían otros caminos para llegar al destino? Si su respuesta es “Sí”, Indique los otros caminos y cuántos transbordos eran necesarios? 16. Elabore la matriz de adyacencia del problema propuesto utilizando el gráfico de conexiones de vuelvo. Esta Matriz indica con un 1 cuando los nodos tienen una relación y un 0 en el caso contrario. 17. Analice el funcionamiento del algoritmo para la estrategia de búsqueda en Profundidad

9

Inteligencia Artificial | Laboratorio 3

Algoritmos de Búsqueda en Profundidad Iterativa A continuación se presenta la el código en Python de vuelos_bpi.py (Búsqueda en Profundidad Iterativa) para resolver el problema propuesto. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. #Vuelos con búsqueda con Profundidad Iterativa from arbol import Nodo def DFS_prof_iter(nodo, solucion): for limite in range(0,100): visitados=[] if sol!=None: return sol def buscar_solucion_DFS_Rec(nodo, solucion, visitados, limite): if limite >0: visitados.append(nodo) if nodo.get_datos() == solucion: return nodo else: #expandir nodos hijo (ciudades con conexión) for un_hijo in conexiones[dato_nodo]: hijo=Nodo(un_hijo) if not hijo.en_lista(visitados): lista_hijos.append(hijo) nodo.set_hijos(lista_hijos) for nodo_hijo in nodo.get_hijos(): if not nodo_hijo.get_datos() in visitados: #llamada recursiva sol = buscar_solucion_DFS_Rec(nodo_hijo, solucion, visitados, limite-1) if sol != None: return sol return None if __name__ == "__main__": conexiones = { 'Malaga':{'Salamanca', 'Madrid', 'Barcelona'}, 'Sevilla':{'Santiago', 'Madrid'}, 'Granada':{'Valencia'}, 'Valencia':{'Barcelona'}, 'Madrid':{'Salamanca', 'Sevilla', 'Malaga', 'Barcelona', 'Santander'}, 'Salamanca':{'Malaga', 'Madrid'}, 'Santiago':{'Sevilla', 'Santander', 'Barcelona'}, 'Santander':{'Santiago', 'Madrid'}, 'Zaragoza':{'Barcelona'}, 'Barcelona':{'Zaragoza', 'Santiago', 'Madrid', 'Malaga', 'Valencia'} }

10

Inteligencia Artificial | Laboratorio 3

#mostrar resultado if nodo != None: resultado=[] while nodo.get_padre() !=None: resultado.append(nodo.get_datos()) nodo = nodo.get_padre() resultado.append(estado_inicial) resultado.reverse() print (resultado) else: print("Solución no encontrada")

Preguntas Propuestas al Problema Propuesto: 18. ¿Cuántas líneas de código fueron necesarias completar en el código? 19. Verifique si la salida del algoritmo corresponde a los siguientes movimientos de estados (transbordo). Movimiento de Estados = ['Malaga', 'Barcelona', 'Santiago'] 20. ¿Cuáles son los movimientos estados (trasbordo) para llegar a la ciudad destino, desde el aeropuerto de origen? Origen=[Salamanca] Destino = [Santiago] 21. Dado el estado inicial (aeropuerto de origen) y el objetivo (aeropuerto destino), pruebe en el algoritmo cuántos transbordos son necesarios Origen=[Sevilla] Destino = [Granada] Habían otros caminos para llegar al destino? Si su respuesta es “Sí”, Indique los otros caminos y cuántos transbordos eran necesarios? 22. Elabore la matriz de adyacencia del problema propuesto utilizando el gráfico de conexiones de vuelvo. Esta Matriz indica con un 1 cuando los nodos tienen una relación y un 0 en el caso contrario. 23. Analice el funcionamiento del algoritmo para la estrategia de búsqueda en Profundidad

11

Inteligencia Artificial | Laboratorio 3

II.

Técnicas de Búsqueda informadas

Son aquellas técnicas que disponen de cierta información para facilitar la búsqueda de la solución al problema. Proveen de heurísticas que son criterios, métodos o principios para decidir cuál de entre varias acciones promete ser la mejor para alcanzar una determinada meta. En la generación del árbol de búsqueda, nos podemos guiar con heurísticas que nos den una indicación acerca de cómo de bueno o prometedor es un determinado estado u operador.

Algoritmo de Búsqueda Heurística A continuación se presenta la el código en Python de puzlelineal_heuristica.py (Búsqueda con Heurística) para resolver el problema propuesto. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. #Puzzle Lineal con Heurística from arbol import Nodo def buscar_solucion_heuristica(nodo_inicial, solucion, visitados): if nodo_inicial.get_datos() == solucion: return nodo_inicial else: #expandir nodos sucesores (hijos) dato_nodo = nodo_inicial.get_datos() hijo=[dato_nodo[1], dato_nodo[0], dato_nodo[2], dato_nodo[3]] hijo_izquierdo = Nodo(hijo) hijo=[dato_nodo[0], dato_nodo[2], dato_nodo[1], dato_nodo[3]] hijo_central = Nodo(hijo) hijo=[dato_nodo[0], dato_nodo[1], dato_nodo[3], dato_nodo[2]] hijo_derecho = Nodo(hijo) nodo_inicial.set_hijos([hijo_izquierdo, hijo_central, hijo_derecho]) for nodo_hijo in nodo_inicial.get_hijos(): if not nodo_hijo.get_datos() in visitados and mejora(nodo_inicial, nodo_hijo): #llamada recursiva if sol != None: return sol return None

def mejora(nodo_padre, nodo_hijo): calidad_padre=0 calidad_hijo=0 dato_padre = nodo_padre.get_datos() dato_hijo = nodo_hijo.get_datos() for n in range(1, len(dato_padre)): if(dato_padre[n]>dato_padre[n-1]): calidad_padre = calidad_padre + 1 if (dato_hijo[n]>dato_hijo[n-1]): calidad_hijo = calidad_hijo + 1 if calidad_hijo>=calidad_padre: return True else:

12

Inteligencia Artificial | Laboratorio 3

return False

if __name__ == "__main__": estado_inicial = [4,2,3,1] solucion = [1,2,3,4] nodo_solucion = None visitados = [] nodo_inicial = Nodo(estado_inicial) #mostrar resultado resultado=[] while nodo.get_padre() != None: resultado.append(nodo.get_datos()) nodo = nodo.get_padre() resultado.append(estado_inicial) resultado.reverse()

Preguntas Propuestas al Problema Propuesto: 24. ¿Cuántas líneas de código fueron necesarias completar en el código? 25. Verifique si la salida del algoritmo corresponde a los siguientes movimientos de estados. Movimiento de Estados =[[4, 2, 3, 1], [2, 4, 3, 1], [2, 3, 4, 1], [2, 3, 1, 4], [2, 1, 3, 4], [1, 2, 3, 4]] 26. ¿Cuál son los movimientos estados para resolver el siguiente estado inicial? Estado inicial=[3,1,4,2] 27. Cuál es el Estado Inicial, pasado al algoritmo, para el siguiente movimiento de estados: [4, 1, 3, 2], [1, 4, 3, 2], [1, 3, 4, 2], [1, 3, 2, 4], [1, 2, 3, 4]] 28. Analice el funcionamiento del algoritmo para la estrategia de búsqueda en Profundidad.

13

Inteligencia Artificial | Laboratorio 3

Algoritmo de Búsqueda Voraz A continuación se presenta la el código en Python de vrpvoraz.py (Búsqueda con Algoritmo Voraz) para resolver el problema propuesto. Este algoritmo es una variación del algoritmo de Búsqueda Primero el Mejor. El siguiente código no está completo. Con ayuda del material en la plataforma, complete el código y verifique que la salida corresponde con la solución propuesta. # Heurística voraz para resolver TSP import math def distancia(coord1, coord2): lat1=coord1[0] lon1=coord1[1] lat2=coord2[0] lon2=coord2[1] return math.sqrt((lat1-lat2)**2+(lon1-lon2)**2) def en_ruta(rutas, c): ruta = None for r in rutas: if c in r: ruta = r return ruta def peso_ruta(ruta): total=0 for c in ruta: total = total + pedidos[c] return total

def vrp_voraz(): # calcular lo ahorros s={} for c1 in coord: for c2 in coord: if c1 != c2: if not (c2,c1) in s: d_c1_c2 = distancia(coord[c1],coord[c2]) d_c1_almacen = distancia(coord[c1], almacen) d_c2_almacen = distancia(coord[c2], almacen) s[c1,c2]= d_c1_almacen + d_c2_almacen - d_c1_c2 # ordenar ahorros

# construir rutas rutas=[] for k,v in s: rc1 = en_ruta(rutas, k[0]) rc2 = en_ruta(rutas, k[1]) if rc1==None and rc2==None: # no están en ninguna rura. La creamos. if peso_ruta([k[0],k[1]])...