Busquedas Informadas

Búsquedas informadas

*Métodos de búsqueda no informada

*Búsqueda bidireccional

Es básicamente una búsqueda simultánea que avanza a partir del estado inicial y que retrocede a partir de la meta y que se detiene cuando ambas búsquedas se encuentran en algún punto intermedio.
No siempre es óptima, incluso si ambas búsquedas son BFS.

Se puede implementar utilizando BFS o profundizacióniterativa (pero por lo menos una frontera debe mantenerse en la memoria).

Debilidad significativa:

* Necesidad de espacio.

Completo: Sí,
Complejidad en tiempo: 2*O(b d/2) = O(b d/2)
Complejidad del espacio: O(b m/2)
Optimo: Sí

*Gráficos de búsqueda

Si el espacio de búsqueda no es un árbol, pero un gráfico, el árbol de búsqueda puede contener diferentesnodos correspondientes en el mismo estado.
El tamaño del espacio de búsqueda puede ser exponencial en el número total de estados (2n)n= nodos

*Evitar estados repetidos

1. No se debe volver al estado del que vienes.
2. No crear caminos con ciclos en ellos.
3. No generan ningún estado que no fue creado antes.

*Búsqueda de Costo-Uniforme

La búsqueda de costo uniforme expande siempre el nodo de menor costo enel margen, medido por el costo de ruta g(n) en vez del nodo de menor profundidad.
Si se cumplen ciertas condiciones, es seguro que la primera solución encontrada será la más barata.
La búsqueda en amplitud es una búsqueda de costo uniforme donde g(n) = profundidad(n).

Este método puede encontrar la solución más barata siempre y cuando se satisfaga un requisito sencillo.
El costo de rutanunca debe ir disminuyendo conforme avanzamos por la ruta, es decir, g(Sucesor(n)) ≥ g(n) para todos los nodos n.
Para que el costo de la ruta no disminuya el costo de aplicar un operador no debe ser negativo.

*Métodos de búsqueda informada
Estos suelen ser más efectivos que los no informados, estos métodos contienen funciones heurísticas.

*Heurística
Heurística son los criterios, métodoso principios para decidir que, entre varias alternativas de acción que promete ser el más eficaz para lograr algún objetivo.
La heurística se utiliza para identificar la ruta de búsqueda más prometedora.

*Búsqueda primero el mejor

La búsqueda costo uniforme es un caso especial del algoritmo de búsqueda primero el mejor. El algoritmo mantiene una cola de prioridad de los nodos a serexplorado. Una función de costes (n) se aplica a cada nodo.
 Los nodos se colocan en ABIERTOS en el orden de sus valores de f. Los nodos con menor f (n) sus valores se expanden antes.
Este es el algoritmo genérico para la búsqueda primero el mejor:

Let fringe be a priority queue containing the initial state
Loop if fringe is empty return failure Node ←remove-first (fringe)
if Node is a goal
thenreturn the path from initial state to Node
else generate all successors of Node, and
put the newly generated nodes into fringe
according to their f values
End Loop

*Búsqueda Avara

En la búsqueda avara, la idea es expandir el nodo con el menor costo estimado para alcanzar la meta.
Se usa la función heurística
f (n) = h (n)
h (n) calcula la distancia restante hasta la meta.
Losalgoritmos avaros a menudo funcionan muy bien. Tienden a encontrar buenas soluciones rápidamente, aunque no siempre las óptimas.

*Busqueda A*

A * es un algoritmo de búsqueda primero el mejor con
f (n) = g (n) + h (n)
donde
g (n) = suma de los costos de ventaja desde el principio hasta n
h (n) = estimación de la trayectoria de menor coste desde n a la meta
f (n) = distancia real hasta elmomento + la distancia restante estimada
h (n) se dice que es admisible si se subestima el costo de cualquier solución que se puede llegar desde n. Si C * (n) es el costo de la ruta de solución más barata a partir de n a un nodo meta, y, si h es admisible
h (n) <= C * (n)
podemos demostrar que si h (n) es admisible, entonces, la búsqueda encontrará una solución óptima.

El algoritmo...