Ensayo Heuristica

Heurística

¿Qué es heurística?

Heuristica es el conjunto de técnicas o métodos para resolver un problema, dado por por la vida cotidiana, esta es determinada como la habilidad de inventar por parte de los seres humanos, con la intencion de tomar decisiones y realizar estrategias para dichas tomas de decisiones.

Por otra parte la heuristica se basa en la experiencia del individuo que recolecta de su entorno para encontrar la solución mas viable respecto al problema.

Esto al formar parte del analisis y la toma de decisiones hace enfasis en realizar a través de medios, principios o reglas concluir la toma de decisiones pero sin la necesidad de que sea la mas idónea como solución del problema.

En la heurística existen varios procedimientos que permiten el abordaje para la solución de un problema.

• Principios heurísticos: los cuales establecen sugerencias para hallar la solución idonea al problema.
• Reglas heurísticas: Son las que señalan los medios para resolver el problema.
• Estrategias heuristicas: Son aquellas que permiten la organización de los materiales o recursos a los que dispone para la búsqueda de la solución del problema.

La heuristica puede ser tomada como una ciencia o disciplina que hace parte del arte del descubrimiento debido a que esta consiste en en la investigación e innovación. como tambien puede ser tomada como los principios o conjuntos de reglas para determinar y encontrar la solución a un problema.

Heuristica Admisible:

La heuristica admisible es toda aquella que busca alcanzar el menos una posible solución para de un problema determinados.

En esto se incluyen los algoritmos de búsqueda por nodos, se determina admisble cuando el costo estimado sea siempre menor o igual al costo mínimo de alcanzar el estado objetivo o final, de una forma factible para llegar a este ultimo.

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.