Busqueda Heurística

BÚSQUEDA HEURÍSTICA

COMPLEJIDAD COSTO UNIFORME

El algoritmo de costo uniforme, forma parte de la búsqueda heurística, en primero es mejor.  Costo uniforme, es un algoritmo completo, ya que siempre que haya una solución, este la encontrara, haciendo así, que este sea un algoritmo optimo, que siempre encontrara la mejor solución, que en este caso sería la cual cuente con un menor costo real en el camino recorrido. A continuación, hablaremos sobre su complejidad:

·         Tiempo:

·                          Número de nodos con g<= costo en la solución óptima:

·         Espacio:

·                          Número de nodos con g<= costo en la solución óptima  

Podemos ver que la complejidad en ambos casos, tanto en tiempo como en espacio, esta expresada en forma exponencial.

COMPLEJIDAD HEURISTICA PURA

El algoritmo de heurística pura, también llamado búsqueda de greedy o avara, es uno de los métodos de búsqueda, de primero el mejor, en búsqueda heurística. Este algoritmo no es una búsqueda completa, ya que puede perderse en un ciclo, quedándose ahí de forma infinita y no encontrar una solución al problema, por lo cual no puede asegurar que siempre encuentre la mejor solución, haciéndola así, una búsqueda, no óptima. A continuación, explicaremos su complejidad: 

·         Tiempo:

·                          Costo temporal de:

·         Espacio:

·                          Guarda todos los nodos en memoria:

COMPLEJIDAD A*

Búsqueda de A*, es la última en formar parte de primero el mejor, en búsqueda heurística, haciendo alusión a que esta, es la combinación de las dos búsquedas ya antes mencionadas, que son la búsqueda uniforme y heurística pura. Esta búsqueda es completa, porque si el problema tiene solución, este siempre se encontrará, también es una búsqueda optima, ya que siempre encontrara la mejor solución, que hace referencia a la de menor costo total estimado en el camino, para llegar al objetivo.

·         Tiempo:

·                          Costo temporal exponencial:

·         Espacio:

·                          Guarda todos los nodos en memoria:

HEURÍSTICA

La heurística consiste en la capacidad de realizar innovaciones positivas, para así conseguir los fines que se pretenden; también se puede definir como la solución de problemas, en la que esta es hallada. La heurística es una función que asigna a cada estado una estimación del costo óptimo a la solución.
Guían la búsqueda por el lugar que poseen menor costo, eliminando aquellos que pueden proporcionar un costo mucho más grande. 

ADMISIBLE

Una heurística es admisible cuando el costo estimado es siempre menor o igual que el costo mínimo de alcanzar el estado objetivo, esta heurística es usada para estimar el costo de alcanzar el estado objetivo en un algoritmo de búsqueda informada.

Para resolver problemas de búsqueda se debe encontrar una heurística admisible, para hacerlo, se deben resolver problemas relajados, que son los que se parecen mucho a que se intenta resolver.

Las heurísticas admisibles por su naturaleza son optimistas, porque siempre creerán que el costo de solucionar el problema, será menor que el que realmente es.

COSISTENCIA

Una heurística es consistente, si al generar un nodo y expandirlo, el costo de llegar a la solución desde el nodo padre, no es mayor que el de generar el nodo hijo más el costo de la solución.

Una heurística consistente es admisible, pero no todas las heurísticas admisibles son consistentes.

MONOTONIA

La monotonía se aplica a las funciones heurísticas, por lo tanto, si cada nodo N y cada sucesor del mismo, el costo de alcanzar la solución, no es mayor que el costo de pasar por el sucesor del mismo, más el costo de llegar a la solución. 

Una heurística monótona es admisible. El algoritmo A*, se considera óptimo, si es monótono.

HEURISTICAS MÁS INFORMADAS

Para entender de forma más sencilla el término de heurísticas más informadas, hay que expresarlo de la siguiente forma:

Si se tienen dos heurísticas admisibles, cada cualquier nivel, se dice que una de las dos es más informada, si cada uno de los nodos examinados por esta, han sido expandidos por el otro nodo.

ALGORITMO A*

El algoritmo A*, hace parte de primero el mejor, en búsqueda heurística. La idea de este algoritmo, es combinar la heurística de cada nodo, teniendo en cuenta el costo de llegar al nodo actual.

Función:

                                                    F(n) = g(n) + h(n)

g(n) = Coste para llegar al nodo n

h(n) = Coste estimado para llegar a un nodo solución desde el nodo n

F(n) = Coste total estimado del camino para llegar al nodo objetivo a través del nodo n

El algoritmo de A*, es un método completo de búsqueda, siempre encuentra la solución y encuentra la más óptima.

A continuación, se mostrará un ejercicio de las torres de Hanói aplicado a dos discos, en el cual usaremos el algoritmo A*, para llegar a la solución:

 

 Árbol generado por el ejercicio planteado: