C. BUSQUEDA HEURÍSTICA


BUSQUEDA HEURÍSTICA

COMLEJIDAD ALGORITMICA

La complejidad de un algoritmo, se refiere a los recursos de tiempo y de espacio de memoria que utliliza un algoritmo para encontrar la solución a un problema, y por tanto a partir de estas medidas se determina si un algoritmo es eficiente, así entonces , esta característica sera evaluada en los siguientes algoritmos de búsqueda heurística o búsqueda guiada.

Algoritmos Primero El Mejor

Algoritmo de Costo Uniforme(Uniform Cost Search)

Es un algoritmo que se aplica para búsquedas en árboles o grafos, el algoritmo inicia desde el nodo raíz del arbol o grafo y teniendo en cuenta que existe un costo para desplazarse hacia otro nodo, el objetivo es llegar a la solución utilizando el camino más económico, el costo del camino es la sumatoria del costo de todos los nodos explorados desde la raíz. Esta es una búsqueda guada, ya que al momento de recorrer un nodo, el algoritmo mira primero todos los nodos a los que se puede desplazar, y de estos escoge el que tenga menor costo. 

Algoritmo Avara(Greedy Search)

El algoritmo de búsqueda avara consiste en asignar o estimar el coste de recorrido, y así escoger el nodo de menor coste; a diferencia del algoritmo de costo uniforme, la busqueda avara no suma el coste desde el nodo raiz, sino que tiene encuenta es el costo.

Algoritmo A*

Es un algoritmo que combina las características de los dos algoritmos anteriores, de modo que al determinar el coste de los nodos a explorar, toma el costo desde la raiz(Uniform Cost search), y la función heurística

¿Como Funciona?

  1. En cada paso se selecciona el nodo más prometedor que se haya generado hasta ese momento (función heurística).
  2. A continuación se expande el nodo elegido generando todos sus sucesores.
  3. Si alguna de ellos es meta el proceso acaba. Si no continúo con el algoritmo.
  4. Es parecido a la búsqueda en profundidad, pero si en una rama por la que estoy explorando no aparece la solución la rama puede parecer menos prometedora que otras por encima de ella y que se habían ignorado. Podemos pues abandonar la rama anterior y explorar la nueva.
  5. Sin embargo al vieja rama no se olvida. Su último nodo se almacena en el conjunto de nodos generados pero aún sin expandir.

Algoritmo

1.
  1. L ← (nodo raíz)
  2. Si OPEN Є Ø. FALLO.STOP
    • sino  n ←extraer.minimo.f(OPEN)
  3. SI n = objetivo, éxito.stop
    • Sino, adicionar n a CLOSED y generar sucesores de n
  4. Para cada sucesor n' hacer:
    • si n' Є OPEN, reetiquetar n' con el camino más corto desde la raíz
    • si n' Є CLOSED, ignorar n'
    • si n' ∉ OPEN y n' ∉ CLOSED, adicionar n' a OPEN
    • ir al paso 2  

EJEMPLO

TENIENDO EN CUENTA EL COSTO UNIFORME:

Y LOS COSTOS ESTIMADOS


EL RECORRIDO ES

 

HEURISTICA

La heurística, es una función cuyo objetivo es guiar los algoritmos hacia un objetivo, buscando las rutas más cortas y economizar tiempo de esta manera.

ADMISIBILIDAD

Una heurística se considera admisible si cumple que la estimación del valor del costo para alcanzar el objetivo de la busqueda, no es mayor que el máximo costo posible, esto implica que la heurística debe tomar información del problema al momento de estimar el costo, a modo de encontrar la solución en la menor cantidad de pasos posible. 

CONSISTENCIA

Toda Heurística consistente, por defecto tiene que ser admisible. En el caso de la heurística consistente, para todo nodo n y todo sucesor n', el costo del recorrido desde n hasta el objetivo, no es mayor al costo desde n hasta n' mas el costo desde n' hasta el objetivo.

h(n)<= c(n,A,n')+h(n')

donde h(n) es el costo desde n hasta el objetivo, c(n,A,n') es el costo desde n hasta n', y h(n') es el costo desde n' hasta el objetivo.

MONOTONÍA

Toda Heurística monótona es admisible, mientras el costo estimado del objetivo, no es mayor al costo estimado de cada nodo n', que es sucesor del nodo n.

HEURISTICA MAS INFORMADA

Una heurística f2, es mas informada que otra heurística f1 si el conjunto de nodos expandidos por f2 es un subconjunto del conjunto de nodos expandidos por f1, lo que significa que f2 expande una menor cantidad de nodos que f1, entonces f2 es más informada que f1 .

REFERENCIAS

Comentarios

Publicar un comentario