Inteligencia Artificial - Unidad 2
Procedimientos de Búsquedas de Información
Las búsquedas heurísticas se basan en métodos formados por la experiencia, se adquiere conocimiento con base en información. Cuando se aplican a problemas específicos, su eficacia depende en gran medida de la forma en que exploten el conocimiento del dominio particular, ya que por si solas las técnicas heurísticas no son capaces de salvar la explosión combinatoria a la que son tan vulnerables los procesos de búsqueda. Por esta razón estas técnicas también son llamadas métodos débiles.
En las búsquedas heurísticas encontramos también los siguientes tipos de búsqueda:
- Generación, Prueba y Escala
- Búsqueda el primero mejor
- Reducción del problema
- Verificación de restricciones
- Análisis de medios y fines
Generación y Prueba:
Algoritmo: Generar una posible solución. Para algunos problemas esto significa generar un objetivo particular en el espacio problema. Para otros supone generar un camino elegido con el conjunto de estados objetivo aceptable. Verificar si realmente el objetivo elegido es una solución comparándolo con el objetivo final o comparando el camino elegido con el conjunto de estados objetivo aceptable. Si se ha encontrado la solución, terminar, sino volver al paso 1. Si se generan las posibles soluciones de forma sistemática, si la solución existe, este procedimiento es capaz de encontrarla en algún momento. Si el espacio problema es muy grande, en algún momento puede ser demasiado tiempo.
Escalada: La técnica de escalada es la evolución de la técnica de profundidad en la que cada nodo se dispone en una forma de evaluar cómo está de cerca o de lejos la solución. La forma más común de evaluar es la función de evaluación.
La técnica de escalada exagera los problemas de la profundidad en el sentido de que no asegura de que se alcance la solución óptima relacionada con esto existen dos problemas que ocurren a menudo cuando se utiliza escalada:
1. Puede haber máximo o mínimos locales esto ocurre por ejemplo cuando la función de evaluación elegida es maximizante y todos los sucesores de un determinado nodo tienen menor valor que el valor del nodo.
2. Altiplanicies: Es un caso parecido al anterior y sucede cuando los mejores sucesores de un nodo tienen igual valor que el nodo. Las soluciones que se pueden adoptar son:
-Retroceder
-Dar más de un paso
Búsqueda primero el mejor
Este método de búsqueda representa una forma de combinar las ventajas que presentan tanto la búsqueda primero en anchura como la primero en profundidad en un solo método.
Reducción de problemas
La estructura de grafo tipo Y-O es útil para representar la solución de problemas que pueden ser descompuestos en un conjunto de problemas más pequeños. Esta descomposición o reducción genera enlaces de tipo Y. Enlaces de tipo Y apuntan a cualquier número de nodos sucesores que deben ser resueltos para ver si es que el enlace apunta hacia una solución. Los enlaces Y se indican con un arco que conecta los enlaces componentes. Para la descripción del algoritmo de búsqueda en un grafo Y-O se definirá un valor llamado INUTILIDAD. Si el valor estimado para una solución se hace mayor que el valor de INUTILIDAD, se abandona la búsqueda. El valor de INUTILIDAD debe escogerse para que cualquier solución con un costo superior resulte demasiado cara como para ser de utilidad práctica, aún en el caso de que sea posible encontrarla.
Verificación de restricciones:
En estos problemas el objetivo consiste en descubrir algún estado del problema que satisfaga un conjunto dado de restricciones. El diseño de tareas puede contemplarse como problemas de verificación de restricciones en los que el diseño debe realizarse dentro de unos límites de tiempo, coste y materiales.
Análisis de medios y fines:
El proceso de análisis de medios y fines se centra en la detención de diferencias entre el estado actual y el estado objetivo. Una vez se ha aislado una diferencia, debe encontrarse un operador que pueda reducirla. Es posible que tal operador no pueda aplicarse en el estado actual por lo tanto, se crea el sub problema que consiste en alcanzar un estado en el que pueda aplicarse dicho operador. Este tipo de encadenamiento hacia atrás, en donde se seleccionan los operadores y se producen sub objetivos para establecer la precondiciones del operador. Sin embargo, es posible que el operador no introduzca el estado objetivo que se desea. En este caso se tiene un segundo sub problema que consiste en llegar desde ese estado hasta un objetivo. Pero si se ha elegido correctamente la diferencia y el operador es realmente eficaz al reducir la diferencia, estos dos sub problemas serán más fáciles de resolver que el problema original. El proceso de análisis de medios y fines puede entonces aplicarse recursivamente. para centrar la atención del sistema en los problemas grandes, a las diferencias se les asignan niveles de prioridad. Las diferencias de prioridad mayor deben considerarse antes que las de menor prioridad. (Aplicable al Problema de la Secretaria.)