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 determiní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 determinístico presente

problemas más grandes para el agente diseñador.

Un sistema es determinístico si, para un estado dado, al menos aplica una regla a

él y de solo una manera. Si más de una regla aplica a cualquier estado particular

del sistema, o si una regla aplica a un estado particular del sistema 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 secuencia de

los nodos visitados en un árbol.

Sin embargo, 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 de la metodología de expansión de un espacio de estado y

consecuentemente el orden de los estados visitados los problemas de búsqueda se

nombran diferentes:

-Búsqueda de Metas en 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.

Si el nodo hoja no representa la meta de estado, la búsqueda se dirige atrás y

arriba al siguiente

La búsqueda de profundidad es usada por computadoras a menudo para los

problemas de búsqueda como ubicar archivos en un disco, o por buscadores para

“spidering” en Internet.

4.3.2.-BUSQUEDA DE METAS EN ANCHURA

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.

Si una meta de estado es alcanzada aquí, el éxito es reportado. De otra forma, la

búsqueda continúa ampliando caminos de todos los nodos del nivel en curso, para

posteriormente bajar al próximo nivel. De este modo, la búsqueda continúa revisar

nodos en un nivel especial, e informará sobre el éxito cuando un nodo meta es

encontrado, y reportar una falla si todos los nodos han sido revisados y ningún

nodo meta ha sido encontrado.

4.3.3.- BUSQUEDA ÓPTIMA

La búsqueda heurística trata de resolver los problemas mediante una nueva

técnica.

Podemos expandir nodos por selección juiciosa, seleccionado el nodo más

prometedor, donde estos nodos estarán identificados por el valor de su fuerza

comparada con sus competidores homólogos con la ayuda de funciones intuitivas

especializadas, llamadas funciones heurísticas.

La búsqueda heurística generalmente trabaja para dos tipos distintos de problemas:

-Backward reasoning (razonamiento hacia atrás).

-Forward reasoning (razonamiento hacia delante).

En un problema de razonamiento hacia delante, nos movemos hacia la meta de

estado desde un estado inicial predefinido, mientras en un problema de

razonamiento hacia atrás, nos movemos hacia un estado inicial a partir de una

meta de estado final.

4.4.- SATISFACCION DE RESTRICCIONES

Los problemas pueden resolverse buscando en un espacio de estados, estos

estados pueden evaluarse por heurísticas específicas para el dominio y probados

para verificar si son estados meta.

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

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.

Una gran ventaja que nos proporciona la utilización de los juegos es que a través

de ellos es muy fácil medir el éxito o el fracaso, por lo que podemos comprobar si

las técnicas y algoritmos empleados son los óptimos. En comparación con otras

aplicaciones de inteligencia artificial, por ejemplo comprensión del lenguaje, los

juegos no necesitan grandes cantidades de algoritmos. Los juegos más utilizados

son las damas y el ajedrez