Búsquedas Heurísticas IA

Views:
 
Category: Entertainment
     
 

Presentation Description

Inteligencia Artificial

Comments

Presentation Transcript

slide 1:

Búsquedas Heurísticas Función que asigna a cada estado una estimación del coste óptimo a la solución. • Procedimiento: criterio que puede resolver un problema pero que no hay garantía de que siempre lo resuelva. • Función: estimación del coste necesario para alcanzar una solución desde el estado actual. 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 sí 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 y prueba Algoritmo o 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 objetivos aceptables. o 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 objetivos aceptables. o 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.

slide 2:

Ejemplo: Búsqueda el primero 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 Se utilizan los grafos Y-O que son útiles para la representación de la solución en problemas que pueden resolverse descomponiéndolos en un conjunto de problemas más pequeños cada uno de los cuales debe resolverse. Esta descomposición genera arcos denominados arcos Y. Un arco Y puede apuntar a cualquier número de nodos sucesores de forma que todos ellos deben resolverse para que el arco apunte a sola solución. 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 subproblema que consiste en alcanzar un estado en el que pueda aplicase dicho operador. Este tipo de encadenamiento hacia atrás en donde se seleccionan los operadores y se producen subobjetivos 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.

authorStream Live Help