Unidad 4 - Búsqueda y satisfacción de restricciones.

photo credit Nasa / Goddard Space Flight Center / Reto Stöckli Búsqueda y satisfacción de

restricciones. 4.1.-PROBLEMAS Y ESPACIOS DE ESTADOS Definición de Problema y Espacio de Estados
Un problema se define por:

-Estado inicial, conjunto de operadores, predicado meta, función de coste del camino.

-Solución

-Camino del estado inicial a un estado que satisface el predicado meta

-Espacio de Estados

-Conjunto de todos los estados alcanzables desde el estado inicial por cualquier secuencia de operadores 4.2 Espacios de estados deterministicos y no deterministicos Un ambiente detrerminístico es aquel en el cual cualquier acción tiene un solo efecto garantizado, no hay incertidumbre acerca del estado que resultará de la realización de la acción. El mundo físico puede ante todos los intentos y propósitos, ser considerado como no determinístico. Un ambiente no detrminístico presente en más de una manera, entonces el sistema es no determinístico. 4.3 Busqueda sistematica Los problemas de búsquedas, que generalmente encontramos en Ciencias Computacionales, son de un estado determinístico. Por ejemplo, en los algoritmos de búsqueda de anchura y de búsqueda de profundidad, uno sabe la scuencia de los nodos visitados en un árbol.

Los problemas de búsqueda, los cuales siempre tendremos que tratar en inteligencia artificial, son no determinísticos y el orden de elementos visitados en el espacio de búsqueda depende completamente en el conjunto de datos.

Dependiendo la metodología de expansión de un espacio de estado, el orden de los estados visitados los problemas de búsqueda de nombran diferentes:
*Búsqueda de metas por anchura
*Búsqueda de metas a profundidad
*Búsqueda óptima 4.3.1.-BUSQUEDA DE METAS A PROFUNDIDAD El algoritmo de más utilizado es el de búsqueda de metas por profundidad. Es llamado así porque sigue cada camino hasta su mayor profundidad antes de moverse al siguiente camino.

Asumiendo que iniciamos desde el izquierdo y trabajamos hacia la derecha, la búsqueda de metas por profundidad involucra trabajar todos los caminos debajo del camino de árbol más a la izquierda hasta que un nodo hoja es alcanzado. Si esta es una meta de estado, la búsqueda es completada y reportada de exitosa. 4.3.2.-BUSQUEDA DE METAS EN ANCHURA 4.4.- SATISFACCION DE RESTRICCIONES Los componentes del estado, son equivalentes a un grafo de restricciones, los cuales están compuestos de:
Variables. Dominios (valores posibles para las variables).
Restricciones (binarias) entre las variables.

Objetivo: encontrar un estado (una asignación completa de valores a las variables) Que satisface las restricciones.

En los Problemas de Satisfacción de Restricciones (PSR), los estados y la prueba de meta siguen a una representación estándar, estructurada y muy simple.

Ejemplos: --Crucigramas --Colorear mapas Una alternativa para la búsqueda de profundidad es la búsqueda de metas de anchura (o amplitud). Como su nombre indica, este enfoque supone atravesar un árbol por anchura más que por profundidad.

Como puede ser visto en la figura más adelante, el algoritmo de anchura empieza examinando todos los nodos de un nivel (a veces llamado hebra uno) abajo del nodo raíz. 4.3.3 Búsqueda óptima La búsqueda heurística generalmente trabaja para dos tipos distintos de problemas:

*Backward reasoning (razonamiento hacia atrás).

*Forward reasoning (razonamiento hacia delante). 4.5.-RESOLUCION DE PROBLEMAS DE JUEGOS Siendo una de las principales capacidades de la inteligencia humana su capacidad para resolver problemas, así como la habilidad para analizar los elementos esenciales de cada problema, abstrayéndolos, el identificar las acciones que son necesarias para resolverlos y el determinar cuál es la estrategia más acertada para atacarlos, son rasgos fundamentales.
Podemos definir la resolución de problemas como el proceso que partiendo de unos datos iníciales y utilizando un conjunto de procedimientos escogidos, es capaz de determinar el conjunto de pasos o elementos que nos llevan a lo que denominaremos una solución óptima o semi-óptima de un problema de planificación, descubrir una estrategia ganadora de un juego, demostrar un teorema, reconocer una imagen, comprender una oración o un texto son algunas de las tareas que pueden concebirse como de resolución.