Please enable JavaScript.
Coggle requires JavaScript to display documents.
T5.RPA.BúsquedaInformada - Coggle Diagram
T5.RPA.BúsquedaInformada
Heurística
Definición: representa el conocimiento extraído de la experiencia dentro del dominio del problema por medio de reglas expresadas en proposiciones. Se usa únicamente cuando no hay una solución óptima con una serie de restricciones de partida.
Tipos
Débil: aplicar un método riguroso para guiar el proceso de búsqueda para mejorar el rendimiento al resolver el problema
Fuerte: facilitar la resolución del problema, pero no nos garantiza la resolución de este, ni su completitud ni su optimalidad.
Función heurística
Tipos
admisible: el valor de una función es menor o igual que el valor del padre más la distancia del padre al hijo
consistente: el valor de una función cumple con la propiedad de que el valor de la función de evaluación de un hijo nunca sea menor que el del padre
-
Calidad: será preferible elegir aquellas funciones que presenten valores de H grandes, siempre que se mantengan admisibles
Definición: evaluar cómo de prometedor es un nodo en el proceso de búsqueda de la meta. El mejor primero," es decir, el nodo más prometedor se expande primero
Búsqueda A*
Coste: coste estimado del nodo actual al nodo meta (h(n)=0 si n es un nodo meta) + coste real de llegar a n desde el estado inicial. Computacional: exponencial en tiempo y espacio
Características: Se basa en un algoritmo genérico. Para que A sea óptimo debe ser admisible. Los nuevos sucesores usan f(x) = g(n) + h*(n). Usa una lista abierta (donde se inserta los nodos si y solo si el nuevo nodo tiene menor f que todos los competidores) y una lista cerrada (nodos visitados). Evita ciclos generales, pues no escribe nodos que se han generado preciamente en el camino al nodo que expande
Concepto: función que se usa para guiar la búsqueda de una solución en el árbol de búsqueda. Su objetivo es minimizar el coste estimado de un camino combinando el coste de llegar al nodo n (g(n)) y el coste aproximado de llegar de este nodo n hasta la meta por medio de la función heurística h**(n).
Propiedades: Completitud si existe solución la encuentra. Admisible si el número de sucesores es finito para cada nodo y H(n) es menor o igual que h(opt(n))
Búsqueda por subobjetivos: Reduce la complejidad en problemas con planes extensos. Con búsquedas heurísticas reduce aún más la complejidad y requiere funciones heurísticas específicas para cada subobjetivo
-