Búsqueda No Informada
Espacio de estados: Grafo dirigido con todos los estados diferentes del problema.
Árbol de búsqueda: Estados generados durante el proceso.
Frontera: Conjunto de estados pendientes de explorar/expandir.
f: Determina el estado más prometedor en la frontera.
Funciones de Evaluación
- Anchura: La frontera es una cola FIFO. f(n) = Profundidad(n)
- Devuelve el camino solución más corto (menos profundo).
- Es óptima si las acciones son de coste positivo e idéntico.
- Uniforme: La frontera es un HEAP. f(n) = g(n)
- Solo si las acciones son de coste positivo.
- Expande los nodos en orden creciente de coste (best-first).
- Profundidad (limitada): La frontera es una pila LIFO. f(n) = -Profundidad(n)
- No se puede garantizar la optimalidad de la solución.
- Profundidad (iterativa): Límite creciente hasta encontrar solución.
- Devuelve el camino solución más corto (menos profundo).
- Es óptima si las acciones son de coste positivo e idéntico.
Búsqueda Informada (Heurística)
- Utilizamos conocimiento específico del problema como guía.
- Dotamos de “inteligencia” al proceso de búsqueda.
- h(n): coste estimado del camino desde n a su solución óptima.
- Si n es un estado solución, entonces h(n) = 0.
- h(n) se calcula:
Búsqueda Voraz
Utiliza únicamente información heurística: f(n) = h(n)
Búsqueda A
Combina información de coste g(n) y heurística h(n): f(n) = g(n) + h(n)
Búsqueda A*
Búsqueda A con una h(n) admisible, que garantiza completitud y optimalidad.
Búsqueda No Informada Espacio estados->grafo dirigido con todos los estados diferentes del problema Arbol busqueda->estados generados durante el proceso Frontera->conjunto de estados pendientes de explorar/expandir f->Determina estado + prometedor frontera Funciones evaluación -ANCHURA->la frontera es una cola FIFO f(n)=Profundidad(n) • Devuelve el camino solucion mas corto (menos profundo). ´ • Es optima si las acciones son de coste positivo e id ´ entico. -UNIFORME->la frontera es un HEAP f(n)=g(n) • Solo si las acciones son de coste positivo. • Expande los nodos en orden creciente de coste (best-first). -PROFUNDIDAD(limitada)->la forntera es una pila LIFO f(n)=-Profundidad(n) • No se puede garantizar la optimalidad de la solucion. ´ -PRFUNDIDAD(iterativa)->limite creciente hasta encontrar solucion • Devuelve el camino solucion m ´ as corto (menos profundo). ´ •Es optima si las acciones son de coste positivo e idéntico.
| Búsqueda Informada (Heurística) • Utilizamos conocimiento específico del problema como guía. • Dotamos de “inteligencia” al proceso de busqueda. ´ • h(n): coste estimado del camino desde n a su sol. optima. ´ → Si n es un estado solucion, entonces ´ h(n) = 0. • h(n) se calcula:
Búsqueda Voraz->Utiliza unicamente inf.heurística f(n)=h(n)
Búsqueda A Combina informacion de coste ´ g(n) y heur´ística h(n): f(n) = g(n) + h(n) Búsqueda A* Busqueda A con una ´ h(n) admisible. que Garantiza completitud y optimalidad.
|
Búsqueda con Adversario
Algoritmo minimax
Algoritmo Poda alfa-beta
Sistemas Basados en Reglas
CLIPS -> herramientas para construir SBR con 3 componentes:
BASE DE HECHOS -> cada estado se presenta como unico hecho. A lo largo de la ejecución BH representa estados del problema explorados o por explorar
La parte izq, elige conjunto de estados aplicable. La parte dch añade nuevos hechos a la BH
MOTOR DE INFERENCIA-> instanciacion, seleccion y ejecucion
