2.1-2.4
Click here to load reader
-
Upload
jesus-espino -
Category
Documents
-
view
6 -
download
1
Transcript of 2.1-2.4
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.