• Author / Uploaded
• Ruben Holguino Borda

Citation preview

CAPITULO 3 BUSQUEDA NO INFORMADA Universidad Nacional de San Antonio Abad del Cusco

Departamento Académico de Informática Ing. Luis Palma

Ing. Luis Palma

Inteligencia Artificial

RESOLUCIÓN DE PROBLEMAS La principal capacidad del hombre es resolver problemas, y para ello: • Analiza los elementos esenciales del problema. • Identifica las acciones necesarias para resolver el problema. • Y determina la estrategia más acertada para atacarlos.

Ing. Luis Palma

Inteligencia Artificial

ELEMENTOS DE UN PROBLEMA • Un punto de partida: Características que definen el problema • Un objetivo que alcanzar: Que queremos obtener • Acciones a nuestra disposición: De qué herramientas disponemos para manipular los elementos del problema • Restricciones sobre el objetivo: Qué características debe tener la solución

Ing. Luis Palma

Inteligencia Artificial

ESPACIO DE ESTADOS 1. Estado: Representación de los elementos que describe el problema en un momento dado. Se distinguen el estado inicial (punto de partida), y el estado final (objetivo del problema)

2. Operador: Un operador es una función de transformación que convierte un estado en otro estado. Los operadores definen una relación de accesibilidad entre estados:

Ing. Luis Palma

Inteligencia Artificial

ESPACIO DE ESTADOS 3. Espacio de Estados: todo el conjunto de estados posibles y su relación de accesibilidad conforman lo que denominados el espacio de estados. Este representa todos los caminos que hay entre los estados posibles de un problema. 4. Solución: la solución podemos definir de 2 maneras: • Secuencia de pasos que llevan del estado inicial al final. • Estado final del problema Existen problemas en el que el objetivo del problema es determinar la secuencia de operadores, y existen otros problemas en el que el objetivo es encontrar el estado solución (sin importar la secuencia de operadores).

Ing. Luis Palma

Inteligencia Artificial

Ejemplo: MICHI

Estado Inicial

Espacio de estados

Estado Final

Operadores: Juegas dos jugadores intercaladamente, Primero juegan las X, luego las O, marcando cada uno X u O respectivamente Solución: el juego termina si una de los jugadores forma una línea de 3 X ó 3 O, También terminan cuando empatan (no existe casilleros donde marcar y ninguno formo una línea de 3 X ó 3 O) Ing. Luis Palma

Inteligencia Artificial

LLAVE PERDIDA Imagine que se ha perdido la llave del carro en alguna habitación del departamento.

Ing. Luis Palma

Inteligencia Artificial

LLAVE PERDIDA • Estado inicial: La persona que busca se encuentra en la puerta de entrada, recién dará inicio a la búsqueda. • Estado final: La persona ha encontrado la llave en alguna habitación. • Operadores: Buscar en un habitación si no encuentra pasar a otra habitación. • Espacio de estados: Persona ubicada en algún ambiente del departamento buscando la llave. • Solución: En que habitación se encuentra la llave, no interesa conocer por que habitaciones realizó la búsqueda.

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – 8 PUZZLE • El 8 puzzle es un problema que consiste en un tablero de 9 posiciones dispuestos como una matriz de 3x3 en el que hay 8 posiciones ocupadas por fichas numeradas del 1 al 8 y una posición vacía. Las fichas se pueden mover ocupando la posición vacía, si la tiene adyacente. El objetivo es partir de una posición cualquiera de las fichas, para obtener una disposición de éstas en el orden específico. Tal como muestra la figura:

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – 8 PUZZLE • Estado inicial: cualquier configuración de 8 fichas en el tablero. • Estado final: configuración específica de 8 fichas en el tablero. • Operadores: mover hueco vertical u horizontalmente. • Espacio de estados: configuraciones de 8 fichas en el tablero, enumeradas del 1 al 8. • Solución: secuencia de movimientos que debe realizarse para llegar del estado inicial al estado final (posiblemente nos interesa la solución con el menor número de pasos).

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO - N REINAS • El problema de la N reinas consiste en colocar N reinas en un tablero de ajedrez de N x N de manera que NO se ataquen entre si. En la figura tenemos la solución para un problema de 8 reinas

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – N REINAS • Estado inicial: configuración sin reinas en el tablero. • Estado final: configuración con N reinas en el tablero, en la que ningún par de reinas se ataca entre si. • Operadores: colocar las reinas en una fila y columna. • Espacio de estados: configuraciones de 0 a N reinas en el tablero de N x N de tamaño con sólo una reina por fila y columna. • Solución: disposición de N reinas que no se atacan entre; solo interesa una solución no interesa los pasos.

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO - BLOQUES • Se tiene N bloques, el juego consiste en colocar los N bloques en cierto orden uno sobre otro (apilados), para ello el jugador solo debe coger un bloque por vez y puede colocar en la mesa o sobre otro bloque libre.

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – BLOQUES • Estado inicial: configuración de N bloques en uno o mas apilados en cualquier secuencia de bloques. • Estado final: configuración de N bloques en una secuencia específica. • Operadores: Situar solo un bloque sobre otro bloque o sobre la mesa • Espacio de estados: configuraciones de los N bloques en uno o varios apilamientos y en orden cualquiera. • Solución: Interesa conocer la secuencia de movidas para llegar del estado inicial al final.

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – ROBOT CAMINANTE El problema consiste en que un robot se desplace de una coordenada origen a otra coordenada objetivo en un paisaje, bidimensional con obstáculos (ejemplo el juego de age of emperies).

Ing. Luis Palma

Inteligencia Artificial

EJEMPLO – NAVEGACION • Espacio de estados: conjunto de coordenadas en las que puede estar el robot en cualquier en el paisaje bidimensional con obstáculos. • Estado inicial: robot en cualquier coordenada del paisaje con obstáculos. • Estado final: robot en la coordenada objetivo del paisaje. • Operadores: El robot puede moverse en 4 direcciones, pero no puede moverse por encima de obstáculos. • Solución: Interesa conocer la ruta por la que se desplaza desde la coordenada origen a la coordenada destino.

Ing. Luis Palma

Inteligencia Artificial

EJERCICIO PRÁCTICO: Identificar y completar los elementos de los problemas Estado Inicial, Estado Final, Operador, Estados, Solución

Ing. Luis Palma

Inteligencia Artificial

JARRAS DE AGUA • Disponemos de dos jarras de agua, una de 4 litros de capacidad y otra de 3 litros de capacidad. Inicialmente están ambas vacías. El estado objetivo es que la jarra de 4 litros de capacidad contenga dos litros de agua, independientemente el contenido de la otra, sabiendo que en ninguna de las jarras hay una señal de volumen distinta de su capacidad.

Ing. Luis Palma

Inteligencia Artificial

AGENTE DE VIAJE Un agente de viaje se encuentra en Perú y de viajar por Brasil, Argentina, Venezuela, Chile, Colombia, Bolivia y regresar a Perú, considerar que existen todas la rutas posibles, ¿cual es la secuencia de países a visitar para que el costo sea el más bajo?

Ing. Luis Palma

Inteligencia Artificial

PACMAN

Ing. Luis Palma

Inteligencia Artificial

LABERINTO

Ing. Luis Palma

Inteligencia Artificial

AJEDREZ

Ing. Luis Palma

Inteligencia Artificial

TRES EN RAYA

Ing. Luis Palma

Inteligencia Artificial

DAMAS

Ing. Luis Palma

Inteligencia Artificial

CUADRADO MÁGICO

Ing. Luis Palma

Inteligencia Artificial

SUDOKU

Ing. Luis Palma

Inteligencia Artificial

ALGORITMOS DE BUSQUEDA

Ing. Luis Palma

Inteligencia Artificial

ALGORITMOS DE ESPACIO DE ESTADOS • Algoritmos de búsqueda no informada • Anchura prioritaria • Profundidad prioritaria • Profundidad iterativa

• Algoritmos de búsqueda heurística • A* • IDA* • Hill-Climbing.

Ing. Luis Palma

Inteligencia Artificial

ALGORITMO DE BÚSQUEDA GENERAL

Las estructuras más adecuadas para representar es espacio de estados son los grafos o árboles en la cada nodo se representa un estado del problema y los operadores de cambio se representa por los arcos, la elección de árbol o grafo obedece al echo de llegar a través de un camino o que haya diferentes caminos.

Ing. Luis Palma

Inteligencia Artificial

ALGORITMO DE BÚSQUEDA GENERAL Algoritmo Búsqueda General Insertar(Est_Inicial, Lista_Est_Abiertos) Est_Actual  Primero(Lista_Est_Abiertos) Mientras Est_Actual ≠ Est_Final y No(Es_Vacia(Lista_Est_Abiertos)) hacer Borra_Primero(Lista_Est_Abiertos) Insertar(Est_Actual,Lista_Est_Cerrados) Hijos  Generar_Sucesores(Est_Actual) Hijos  Tratar_Repetidos(Hijos,Lista_Est_Cerrados, Lista_Est_Abiertos) Insertar(Hijos,Lista_Est_Abiertos) Est_Actual  Primero(Lista_Est_Abiertos) Fin_Mientras Ing. Luis Palma

Inteligencia Artificial

CONSIDERACIONES DEL ALGORITMO DE BÚSQUEDA GENERAL Consideraciones a tomar en cuenta en el algoritmo: • Listad de nodos abiertos: almacena los nodos generados (sucesores). • Listad de nodos cerrados: almacenan nodos procesados. • Política de decisiones: definen el orden en el que se generan los sucesores y el orden de procesamiento (exploración) de sucesores. El orden define el comportamiento del algoritmo. • Orden de Expansión: orden en el que generamos los sucesores. • Orden de Selección: orden de exploración de los nodos

Ing. Luis Palma

Inteligencia Artificial

PROPIEDADES PARA EVALUAR A LOS ALGORITMOS • Completitud: Si un algoritmo es completo tenemos la garantía que encontrara una solución. ¿Encuentra la solución?

• Complejidad temporal: nos indica el costo temporal de la búsqueda en función al tamaño del problema. ¿Cuánto tiempo requiere? • Complejidad espacial: espacio requerido para almacenar los nodos pendientes de explorar. ¿Cuánta memoria requiere? • Optimalidad: si es capaz de encontrar la mejor solución. ¿Encuentra la mejor solución? Ing. Luis Palma

Inteligencia Artificial

BUSQUEDA NO INFORMADA

Ing. Luis Palma

Inteligencia Artificial

BUSQUEDA NO INFORMADA Características de los algoritmos de búsqueda no informada: • Estos algoritmos no dependen de la información propia del problema, por tanto pueden aplicarse a cualquier circunstancia. • Sigue una estrategia fija al momento de resolver un problema. • Existen políticas de recorrido (anchura, profundidad, etc.) • Son algoritmos exhaustivos y sistemáticos, su coste puede ser prohibitivo para la mayoría de problemas reales.

Ing. Luis Palma

Inteligencia Artificial

ANCHURA PRIORITARIA • La búsqueda en anchura prioritaria explora el espacio de búsqueda haciendo un recorrido por niveles, de modo que un nodo solo se visita cuando todos sus predecesores y sus hermanos anteriores en orden de generación ya fueron visitados. • Las propiedades que toman: • Completitud: el algoritmo siempre encuentra la solución. • Complejidad temporal: O(rp), donde: r: ramificación, p: profundidad. • Complejidad espacial: O(rp), donde: r: ramificación, p: profundidad. • Optimalidad: la solución obtenida es optima.

Ing. Luis Palma

Inteligencia Artificial

ANCHURA PRIORITARIA En el grafo de la figura haga un recorrido en anchura prioritaria, asumiendo que el nodo A es el nodo inicio, y los nodos K y E son los nodos solución.

A, D, F, G, H, C, E Ing. Luis Palma

Inteligencia Artificial

PROFUNDIDAD PRIORITARIA • La búsqueda en profundidad prioritaria explora un camino hasta la mayor profundidad posible, retrocediendo cuando acaba el camino y retomando la última posibilidad de elección disponible. • Las propiedades que toman: • Completitud: el algoritmo encuentra la solución si existe una solución dentro de un límite de profundidad. • Complejidad temporal: O(rp), donde: r: ramificación, p: profundidad. • Complejidad espacial: en un versión iterativa O(rp), donde: r: ramificación, p: profundidad, si la versión es recursiva O(p). • Optimalidad: No se garantiza que la solución sea optima.

Ing. Luis Palma

Inteligencia Artificial

PROFUNDIDAD PRIORITARIA En el grafo de la figura haga un recorrido en profundidad prioritaria, asumiendo que el nodo A es el nodo inicio, y los nodos K y E son los nodos solución.

A, D, H, B, C, K Ing. Luis Palma

Inteligencia Artificial

ALGORITMO DE PROFUNDIDAD ITERATIVA Algoritmo Profundiad Iterativa(limite:entero) Prof  1 Inicializar(Lista_Est_Abiertos) Mientras Est_Actual ≠ Est_Final y Prof < Límite hacer Insertar(Est_Inicial, Lista_Est_Abiertos) Est_Actual  Primero(Lista_est_abiertos) Mientras Est_Actual ≠ Est_Final y No_vacia(Lista_est_Abiestos) hacer Borra_Primero(Lista_Est_Abiertos) Insertar(Est_Actual,Lista_Est_Cerrados) Si Profundidad(Est_Actual)