2.1 Solución de problemas por búsqueda

La solución de problemas es fundamental para la mayoría de las aplicaciones de IA;

existen principalmente dos clases de problemas que se pueden resolver mediante

procesos computables: aquéllos en los que se utiliza un algoritmo determinista que

garantiza la solución al problema y las tareas complejas que se resuelven con la búsqueda

de una solución; de ésta última clase de problemas se ocupa la IA.

La resolución de problemas es una capacidad que consideramos inteligente

Somos capaces de resolver problemas muy diferentes. Encontrar el camino en un laberinto,

Resolver un crucigrama,Jugar a un juego,Diagnosticar una enfermedad,Decidir si invertir en bolsa,etc.

El objetivo es que un programa también sea capaz de resolverlos. Deseamos definir cualquier tipo de problema de manera que se pueda resolver automáticamente

Necesitamos:

Una representación común para todos los problemas Algoritmos que usen alguna estrategia para resolver problemas definidos en esa

representación común

Si abstraemos los elementos de un problema podemos identificar:

a. Un punto de partidab. Un objetivo a alcanzarc. Acciones a nuestra disposición para resolver el problemad. Restricciones sobre el objetivoe. Elementos que son relevantes en el problema definidos por el tipo de dominio

Existen diferentes formas de representar problemas para resolverlos de manera automática:

Representaciones generales,espacio de estados: un problema se divide en un conjunto de pasos de resolución desde el inicio hasta el objetivo

2.2 Espacios de estados

Un espacio de estados es un grafo cuyos nodos corresponden a estados del problema. De

éste modo, utilizando ésta representación, la solución a los problemas se convierte en la

búsqueda de caminos ó rutas óptimas dentro del grafo.

Los estados y su relación de accesibilidad conforman lo que se denomina espacio de estados

Representan todos los caminos que hay entre todos los estados posibles de un problema

Podría asimilarse con un mapa de carreteras de un problema si la solución de nuestro problema está dentro de ese mapa.

Definir el conjunto de estados del problema (explícita o implícitamente):

1. Especificar el estado inicial2. Especificar el estado final o las condiciones que cumple3. Especificar los operadores de cambio de estado (condiciones de aplicabilidad y función de

transformación)4. Especificar el tipo de solución5. La secuencia de operadores o el estado final6. Una solución cualquiera, la mejor (definición de coste)

2.3 Métodos de búsqueda

los métodos más importantes de propósito general para la búsqueda de soluciones a los problemas son:

-Búsqueda ciega.

-Primero en profundidad.

-Primero a lo ancho.

-Solución por costo mínimo.

-Reducción de Problemas, grafos AND/OR,

árboles de juegos.

-Heurística, funciones de evaluación, búsquedas heurísticas en

grafos AND/OR.

-Técnicas de poda : alfa, beta, alfa-beta, hacia adelante y otras.

Primero en profundidad.-

Explora cada camino posible hasta su conclusión antes de intentar otro camino.

Ejemplo:

Primero a lo ancho.-

Explora cada nodo sobre el mismo nivel antes de intentar analizar un nivel más profundo.

Ejemplo:

2.4Satisfaccion de restricciones

La programación de restricciones puede dividirse en dos ramas claramente diferenciadas: la “satisfacción de restricciones” y la “resolución de restricciones”. Ambas comparten la misma terminología, pero sus orígenes y técnicas de resolución son diferentes. La satisfacción de restricciones trata con problemas que tienen dominios finitos,mientras que la resolución de restricciones está orientada principalmente a problemas sobre dominios infinitos o dominios más complejos.

Los conceptos clave en esta metodología corresponden a los aspectos de:

La modelización del problema, que permite representar un problema mediante un conjunto finito de variables, un dominio de valores finito para cada variable y un conjunto de restricciones que acotan las combinaciones válidas de valores que las variables pueden tomar. En la modelización CSP, es fundamental la capacidad expresiva, a fin de poder captar todos los aspectos significativos del problema a modelar.

Técnicas inferenciales, que permiten deducir nueva información sobre el problema a partir de la explícitamente representada. Estas técnicas también permiten acotar y hacer más eficiente el proceso de búsqueda de soluciones.

Técnicas de búsqueda de la solución, apoyadas generalmente por criterios heurísticos, bien dependientes o independientes del dominio. El objetivo es encontrar un valor para

cada variable del problema de manera que se satisfagan todas las restricciones del problema. En general, la obtención de soluciones en un CSP es NP-completo, mientras que la obtención de soluciones optimizadas es NPduro, no existiendo forma de verificar la optimalidad de la solución en tiempo polinomial. Por ello, se requiere una gran eficiencia en los procesos de búsqueda.