Heuristicas

Heurística Admisible:

Una heurística h(n) es admisible si para cada nodo n, h(n) <= h*(n), en el cual h*(n) es el costo verdadero para llegar al estado objetivo n. Una heurística admisible nunca sobrestima el costo para llegar al estado objetivo, es optimo. Usar una heurística admisible garantiza que un nodo en el camino optimo no pueda parecer tan malo como para no considerarlo nunca.

Heurística Monótona:

Un heurística h es monótona si para todo par de nodos n y n' se cumple que

donde k(n,n') representa el costo mínimo para ir de n a n', y por lo tanto es infinito si  no hay un camino desde n a n'.

• Esta condición asegura la optimización también cuando se utiliza el algoritmo de baqueada en grafos.
• El nodo n' es sucesor de n.
• h(n) = coste estimado desde n a t.
• h(n) cumple la desigualdad triangular.
• La evaluación heurística del estado meta es 0, h(meta) = 0.

Heurística Consistente:

Una heurística h es consistente si para todo par de nodos n y n' se cumple que 

donde c(n,n') representa el coste de la regla que lleva de n a n', y por tanto es infinito si no existe esta regla.

Si h es consistente, tenemos 

• Se puede demostrar que toda heurística consistente es también admisible.
• La consistencia es una exigencia mas estricta que la admisibilidad.
• Es difícil crear heurísticas que sean admisibles, pero no consistentes.
• Si h(n) es consistente, entonces los valores de f(n), a lo largo de cualquier camino, no disminuyen.

Heurístico mas informado:

Busqueda A*:

• Idea: Evita expandir rutas que ya son costosas.
• Función de evaluación f(n) = g(n) + h(n)

          g(n) = costo hasta ahora para llegar a n.

          h(n) = costo estimado de n al objetivo

          f(n) = costo estimado total de la ruta desde n al objetivo.

Una propiedad que nos permite comparar heurísticas entre si, y permite saber cual de ellos hará que A* necesite explorar mas nodos para encontrar una solución optima.

Se dice que el heurístico h1 es mas informado que el heurístico  h2 si se cumple la propiedad:

Poder verificar esta propiedad implica que las dos heurísticas son admisibles. Si un heurístico es mas informado que otro, al hacer uso de él en el algoritmo A*  se expandieran menos nodos durante la búsqueda, ya que su comportamiento sera mas en profundidad y habrá ciertos nodos que no se exploran.

Bibliografia:

URL: http://www.cs.us.es/~fsancho/?e=62
URL: http://profesores.elo.utfsm.cl/~tarredondo/info/soft-comp/heuristicas.pdf
URL: https://www.infor.uva.es/~arancha/IA/busqueda/busq2.pdf
URL: http://datateca.unad.edu.co/contenidos/90169/Material_de_Apoyo/Documentos_de_apoyo_unidad_2/BusquedaHeuristica.pdf
URL: http://www.iiia.csic.es/~pedro/busqueda3-A*.pdf