• Author / Uploaded
• Gerardo Gómez García

• Categories
• Inteligencia artificial
• Tecnología
• Teoría de grafos
• Heurístico
• Ajedrez

Citation preview

INSTITUTO TECNOLOGICO DE OAXACA

1

INTELIGENCIA ARTIFICIAL SEGUNDA UNIDAD: TECNICAS DE BÚSQUEDA M.C. IDARH CLAUDIO MATADAMAS ORTIZ

INTRODUCCIÓN

2

La resolución de problemas se describe a menudo como una búsqueda en un enorme laberinto de posibilidades, un laberinto que describe el entorno. Para resolver exitosamente un problema se requiere explorar el laberinto de forma selectiva y con ello reducirlo a proporciones manejables. Las máquinas aún no pueden reducir automáticamente los problemas a proporciones manejables, es por ello que los seres humanos tienen que formular los problemas y proponer estrategias para encontrar su solución.

CLASES DE PROBLEMAS.

3



Una primera clase puede ser resuelta usando algún tipo de procedimiento determinista cuyo éxito esté garantizado. A este procedimiento se le llama de computación. La resolución por computación normalmente sólo se aplica a aquellos tipos de problemas para los que existan tales procedimientos, como en matemáticas.



La segunda categoría, consiste en problemas que se resuelven con la búsqueda de una solución. Este es el método de resolución de problemas del que se preocupa la IA.

Problema: llaves perdidas.

4

DEFINICIONES NECESARIAS.

5



Estado: es la representación de un problema en un instante dado. Para definir el espacio de estados o espacio de búsqueda(El conjunto de todos los nodos) no es necesario hacer una exhaustiva enumeración de todos los estado válidos, sino que es posible definirlo de manera más general.



Estado inicial: consiste en uno o varios estados en los que puede comenzar el problema.



Estado objetivo o estado meta: consiste en uno o varios estados finales que se consideran solución aceptable.



Reglas: describen las acciones u operadores que posibilitan un pasaje de estados. Podríamos decir que una regla tiene una parte izquierda y una derecha. La parte izquierda determina la aplicabilidad de la regla, es decir, describe los estados a los que puede aplicarse la regla. La parte derecha describe la operación que se lleva a cabo si se aplica la regla(acción).



Heurística es la información acerca de la posibilidad de que un nodo específico sea mejor para intentar la próxima elección que cualquier otro nodo. El camino solución es el grafo dirigido de los nodos visitados que nos llevan a la solución.

6

Ejemplo: jugar al ajedrez:

7



Espacio de estados: La totalidad de tableros que se pueden generar en un juego de ajedrez.



Estado Inicial: Puede ser el tablero de 8 x 8 donde cada cuadro contiene un símbolo de acuerdo a las piezas situadas.



Objetivo o estado final: Cualquier posición de tablero en la que el contrario no puede realizar ningún movimiento legal y su rey esté amenazado.



Reglas: Son los movimientos legales, que pueden describirse mediante una parte patrón para ser contrastado con la posición actual del tablero y otra parte que describe el cambio que debe producirse en el tablero. Dado que escribir todas las posiciones del tablero, las reglas deben escribirse de manera más general posible.



Heurística: Podemos elegir tableros en donde el contrincante tenga el menor número de piezas desplegadas.



Camino solución: El conjunto de movimientos para llegar al estado final.

8



En la mayoría de los problemas en los que quiera usar una computadora para hallar la solución, la situación es diferente.



Generalmente, usará una computadora para resolver problemas en los que le número de nodos en el espacio de búsqueda sea muy grande.



El espacio de búsqueda va creciendo, de igual modo se incrementarán el número de diferentes caminos posibles hasta la meta.



Cada nodo añadido al espacio de búsqueda añade más de un camino; por lo que el número de caminos hasta la meta se incrementará rápidamente con cada nuevo nodo.

FORMULACIÓN Y RESOLUCIÓN DE PROBLEMAS. Para construir un sistema de computación que resuelva un problema específico, es necesario: 

Definir el problema formalmente con precisión.



Analizar el problema.



Representar el conocimiento necesario para resolver el problema.



Elegir una técnica de resolución del problema y aplicarla.

9

DEFINICIÓN FORMAL DEL PROBLEMA. Objetivo: Descripción formal y manejable del propio problema operacionalización. Para producir una especificación formal de un problema se deben definir: 

Espacio de estados válidos.



Estado inicial del problema.



Estado objetivo o final.



Reglas que se pueden aplicar para pasar de un estado a otro.

10

11 La representación como espacio de estados: 

Permite definir formalmente el problema, mediante la necesidad de convertir una situación dada en una situación deseada mediante un conjunto de operaciones permitidas.



Permite definir el proceso de resolución de un problema como una combinación de técnicas conocidas y búsqueda (la técnica general de exploración del espacio intenta encontrar alguna ruta desde el estado actual hasta un estado objetivo).

ANÁLISIS DEL PROBLEMA.

12

¿Puede descomponerse el problema en subproblemas más pequeños? 

Algunos problemas pueden descomponerse en subproblemas independientes, de manera que encontrar una solución global es la composición de soluciones particulares. Por ej. en la resolución de integrales, una integral puede descomponerse por partes, y resolver las partes simples directamente o descomponerlas recursivamente.



Por otra parte, existen otros problemas que no pueden descomponerse y componer la solución a partir de las soluciones parciales de sus partes p. ej. problemas de planificación de rutas con restricciones. Por el contrario, una solución necesita considerar globalmente el problema.

¿Pueden deshacerse pasos inadecuados hacia la solución? 

Recuperables: en un punto dado es posible deshacer todos los pasos inadecuados.



No recuperables: en un punto dado no es posible deshacer ningún paso realizado. En estos problemas el sistema debe esforzarse en la toma de decisiones pues éstas son irrevocables.



Ignorables: en un punto dado es posible ignorar los pasos realizados hasta el momento y comenzar de nuevo con una nueva solución. Por ej. un demostrador de teoremas.

13

14 ¿Es predecible el universo del problema? 

Consecuencia cierta: es posible planificar una secuencia de movimientos estando seguros del resultado a obtener. Se puede realizar una planificación para generar operadores que garanticen llegar a la solución.



Consecuencia incierta: no es posible planificar con certeza pues no se sabe que ocurrirá luego del siguiente movimiento. Sin embargo, se puede realizar una planificación para generar operadores que tengan una buena probabilidad de llegar a la solución.

15 ¿Una solución es buena de manera absoluta o relativa? La solución de un problema puede consistir en encontrar: 

Algún camino: sólo importa encontrar una solución sin importar si existen otros caminos que conducen a la solución. Generalmente se resuelven con heurísticas. Por ej. programa de respuestas a preguntas.



El mejor camino: importa encontrar la ruta más corta hacia la solución. Son problemas más complicados de computar. Algunos requieren una búsqueda más exhaustiva que usando heurísticas. Por ej. en el problema del viajero importa encontrar la ruta más corta entre las ciudades a visitar.

16 ¿La solución deseada es un estado o la ruta hacia un estado? La solución de un problema puede 

consistir en encontrar: Un estado final: no es necesario el registro del proceso seguido, sólo importa arribar a la solución final. Por ej. interpretar texto.



Una ruta hacia un estado final: se necesita dar el camino seguido desde el estado inicial al estado final. Por ej. problema de las jarras de agua.

17 ¿El conocimiento se necesita para resolver el problema o para restringir la búsqueda de la solución? El conocimiento puede emplearse para:



Reconocer la solución: se necesita gran cantidad de conocimiento acerca del problema para poder encontrar una solución. Por ej. comprensión de texto.



Acotar la búsqueda: la solución básica puede encontrarse con poco conocimiento, pero para restringir el árbol de búsqueda y encontrar la solución de manera más eficiente es necesario contar más conocimiento. Por ej. en el ajedrez se necesita básicamente poco conocimiento para conocer los movimientos legales y un mecanismo sencillo de búsqueda. Pero dado que para aumentar la eficiencia de la búsqueda ésta debe restringirse, se necesita conocimiento de heurísticas de buenas estrategias y tácticas para jugar.

18 El programa que soluciona el problema ¿busca la solución solo o necesita interactuar con una persona?

Con respecto a la relación programa-usuario, existen dos tipos de programas que solucionan el problema: 

Solitarios: reciben como entrada el problema y dan como salida la solución. No importa el razonamiento que haya seguido la máquina para encontrar la solución. Por ej. problema de las jarras de agua.



Conversacionales: existe una comunicación hombre-máquina de manera que el usuario puede ayudar a la máquina o la máquina puede informar al usuario durante la búsqueda de la solución. Para que esta comunicación sea posible debe existir una correspondencia entre el razonamiento seguido por la máquina y la forma de razonamiento humano. Por ej. en un sistema experto de diagnóstico médico, el usuario no aceptaría el veredicto de una máquina si no puede comprender el razonamiento que la llevó a él .

Problemas NP-difíciles

19

Definición informal: 

Problemas que, para resolverlos de forma exacta, requieren la realización de una búsqueda en un espacio que es de tamaño exponencial.



Nadie sabe como evitar esa búsqueda.



No se espera que nadie lo consiga nunca…

Problemas NP-difíciles

20



Todos los problemas de los que se ocupa la I.A. son NP-difíciles (si existe un algoritmo rápido para un problema, difícilmente consideraremos que el problema requiere inteligencia).



Si un problema es NP-difícil y tenemos un algoritmo que encuentra la solución de forma rápida y casi siempre correcta, podemos considerar que el algoritmo es “inteligente”.



La I.A. implica que la búsqueda está sujeta a errores.

Métodos de búsqueda…

21

Tipos de problemas …

Existen dos tipos de problemas que se han estado investigando en el área de Inteligencia Artificial: Los denominados problemas de juguete y problemas del mundo real. 

Problemas de juguete. Un problema de juguete se utiliza para ilustrar o ejercitar los métodos de resolución de problemas. Éstos se pueden describir de forma exacta y concisa. Esto significa que diferentes investigadores pueden utilizarlos fácilmente para comparar el funcionamiento de los algoritmos.



Un problema del mundo real es aquel en el que la gente se preocupa por sus soluciones. Ellos tienden a no tener una sola descripción, sin embargo se podría dar la forma general de sus formulaciones.

22



El mundo de la aspiradora es un problema de juguete, este problema puede formularse como sigue:



Espacio de estados: La aspiradora está en una de dos habitaciones, cada una de las cuales puede o no contener suciedad(8 posibles estados del mundo); Estado Inicial: Cualquier estado puede designarse como un estado inicial.



Objetivo o estado final: Cuando todos las habitaciones están limpias;



Reglas: La aspiradora puede: moverse a la habitación izquierda, moverse a la habitación derecha o aspirar la habitación.

23 

El problema del viajante de comercio es un problema de ruta en la que cada ciudad es visitada exactamente una vez. La tarea principal es encontrar el viaje más corto.



Un problema de distribución VLSI requiere la colocación de millones de componentes y de conexiones en un chip verificando que el área es mínima, que se reduce al mínimo el circuito, que se reduce al mínimo las capacitaciones, y se maximiza la producción de fabricación. El problema de la distribución viene después de la fase de diseño lógico, y está dividido generalmente en dos partes: distribución de celdas y dirección del canal. En la distribución de celdas, los componentes primitivos del circuito se agrupan en las celdas, cada una de las cuales realiza una cierta función.

Grafos de estados (implícito)

24



Representación matemática de un problema de búsqueda (nodos; estados; arcos: operadores).



Grafo teórico que representa todas las posibles transformaciones del sistema aplicando todos los operadores posibles recursivamente.



Debido a su complejidad exponencial, que requeriría una cantidad inviable de memoria y tiempo, el grafo del espacio de estados no puede generarse por completo.

Grafos de estados (explícito)

25



Debido a la complejidad exponencial del grafo implícito, se irá generando, paso a paso, una porción del grafo conforme avance el proceso de búsqueda.



El grafo explícito es el subgrafo del grafo implícito que se va generando durante el proceso de búsqueda de una secuencia de operadores que resuelva nuestro problema (camino solución) .



Usualmente, en forma de árbol.

Árbol de búsqueda / Grafo explícito

26



Nodo raíz: Estado inicial.



Hijos de un nodo: Posibles sucesores (nodos correspondientes a estados resultantes de la aplicación de un operador al nodo padre).



Los nodos del árbol representan estados, pero corresponden a PLANES mediante los cuales se alcanzan dichos estados.

Tipos de técnicas de búsqueda

27

No informadas o a ciegas. 

Busca la primera solución sin importar que tan optima sea.



No detecta si se está aproximado o alejando a la solución.



No es capas de encontrar una solución aceptable en caso de que no exista o sea demasiado costoso encontrar la solución optima.

Informadas o heurísticas. 

Busca soluciones aceptables.



Reduce el espacio de búsqueda y es capas de determinar su proximidad a una solución y la calidad de la misma utilizando conocimiento a priori.

Técnica de búsqueda primero en profundidad.

28



Una búsqueda primero en profundidad explora cada camino posible hasta su conclusión(meta) antes de intentar otro camino. Esta técnica de búsqueda pertenece a las estrategias de búsqueda no informada, es decir la búsqueda no utiliza más que la información proporcionada por la definición del problema.



Esta estrategia de búsqueda en profundidad puede implementarse a través de una estructura de tipo pila(último en entrar primero en salir) o alternativamente puede aplicarse como una función recursiva que se llama en cada uno de sus hijos.



La búsqueda primero en profundidad tiene unos requisitos muy modestos de memoria. Necesita almacenar sólo un camino desde la raíz a un nodo hoja, junto con los nodos hermanos restantes no expandidos para cada nodo del camino. Una vez que un nodo se ha expandido, se puede quitar de la memoria tan pronto como todos sus descendientes han sido explorados.

Cuándo terminar de buscar? 

Se ha encontrado la solución.



Se ha acabado el tiempo disponible.



Se ha llegado a un nivel de profundidad determinado

29

Búsqueda en profundidad.

30

Pasos

31



Siempre se expande uno de los nodos que se encuentren en los mas profundo del árbol. Solo si la búsqueda conduce a un callejón sin salida, se revierte la búsqueda y se expanden los nodos de niveles menos profundos.



Esta búsqueda, o se queda atorada en un bucle infinito, y nunca es posible regresar al encuentro de una solución, o encuentra una ruta de solución más larga que la solución óptima. El tiempo necesario crece exponencialmente con respecto a la profundidad, mientras que el espacio requerido en memoria lo hace en forma lineal

Técnica de búsqueda primero en amplitud.

32



La búsqueda primero en amplitud o en anchura es una estrategia sencilla en la que se expande primero el nodo raíz, a continuación se expanden todos los sucesores del nodo raíz, después sus sucesores, etc.



En general, se expanden todos los nodos a una profundidad en el árbol de búsqueda antes de expandir cualquier nodo del próximo nivel.



La búsqueda primero en anchura se puede implementar utilizando una estructura de tipo cola primero en entrar primero en salir, asegurándose que los nodos primeros visitados serán los primeros expandidos.



La principal desventaja de la búsqueda en anchura es los requisitos de memoria para almacenar todos los nodos que no han sido expandidos durante la búsqueda.

Pasos…

33

Todos los nodos que están en la profundidad d del árbol de búsqueda se expanden antes de los nodos que estén en la profundidad d+1. •Si son varias las soluciones, este tipo de búsqueda permitirá siempre encontrar primero el estado meta más próximo a la raíz. •El tiempo y la cantidad de memoria necesaria crece exponencialmente con respecto a la profundidad.

• Se tiene un árbol en un estado inicial y se cuenta con cuatro metas: M1, M2, M3 y M4.

• Se introduce A como primer elemento de la lista.

• Se comprueba que A no es una meta y se elimina de la lista. • Se introducen los hijos de A en la lista recorriendo el árbol de izquierda a derecha y manteniendo la información del recorrido. Es decir AB y AC.

• AB no muestra ninguna meta así que se saca de la lista. • Se analizan los hijos de B y se introducen al final de la lista como ABD y ABE.

• AC tampoco es una meta y es eliminado de la lista. • Se introducen los hijos de C al final de la lista.

• Se siguen sacando de la lista aquellos nodos que no dan como resultado una meta. • En este caso se introducen al final de la lista los hijos de D. • Los nuevos nodos introducidos a la lista son H e I.

• ABE no muestra ninguna meta y se elimina de la lista. • Al introducir los hijos de E al final de la lista se puede ver que ha aparecido uno de los nodos meta. En este caso el nodo es M1

• Se siguen eliminando los nodos que no son estados meta y agregando a los hijos al final de la lista.

• En este punto se elimina ABEJ y se introducen los hijos de J al final de la lista y al frente queda ABEM1 lo que da como resultado el éxito.

• Se encuentra la meta M1 y se detiene el algoritmo al haber alcanzado el éxito.

• Se traza el camino desde el origen hacia la meta: • A  B  E  M1 • El algoritmo de búsqueda en anchura se detiene al encontrar un nodo meta sin importar cual sea este. • En el caso hipotético de que M1 no hubiese sido un nodo meta el algoritmo habría continuado sacando nodos del frente de la lista e introduciendo hijos al final de la misma hasta hallar una meta. En este caso M2.

Problema del viajero

48

Imagine que usted es agente de viajes y un cliente bastante molesto quiere que le reserve un boleto de Salina Cruz a Ciudad Reynosa con la línea de autobuses ADOGL . A pesar de que usted le dice al cliente que la línea de autobuses ADO GL tiene rutas directas, éste insiste en viajar exclusivamente con ADO-GL R. Mirando la lista(supuesta) de rutas de ADO-GL, encuentra que es posible. Entonces puede verse que hay una forma de llegar de Salina Cruz a Ciudad Reynosa con la línea de autobuses ADO-GL Rusando trasbordos. Así pues reserva un boleto para el cliente. La información extraída del libro de rutas del ADO-GL puede ser trasladada al grafo no dirigido mostrado en la figura siguiente.

49

50

Consideraciones 

Espacio de estados: Todas las terminales de ADO-GL



Estado Inicial: La terminal de Salina Cruz



Objetivo o estado final: La terminal de Ciudad Reynosa;



Reglas: Moverse a alguna ciudad adyacente desde la terminal en la que se encuentre el cliente en ese momento



Con la información anterior determine una ruta que resuelva el problema utilizando ambas técnicas vistas en clase.

51