Costo Uniforme, Heuristica pura y A* Inteligencia Artificial

Complejidad en costo Uniforme

El algoritmo de costo uniforme, forma parte de la búsqueda heurística. Costo uniforme, es un algoritmo completo, ya que siempre que haya una solución, este la encontrara haciendo que este sea un algoritmo optimo, que siempre encontrara la mejor solución, que sera la que tenga menor costo real en el camino recorrido. 

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 o avara. Este algoritmo no es una búsqueda completa, ya que puede perderse en un ciclo, quedandose 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éndolo así, una búsqueda, no óptima. 

Su complejidad: 

Tiempo:
Costo temporal:


Espacio:
Guarda todos los nodos en memoria:

Búsqueda A*

Es un método de búsqueda que implementa la búsqueda de costo uniforme y de heuristica pura, donde se utiliza una función de evaluación f(n) = g(n) + h'(n), donde h'(n) representa el valor heuristico del nodo a evaluar desde el actual, n, hasta el final, y g(n), el coste real del camino recorrido para llegar a dicho nodo, n, desde el nodo inicial.

Algoritmo

Complejidad en Algoritmo estrella (A*)

Es la combinación de las dos búsquedas ya antes mencionadas. Esta búsqueda es completa, si el problema tiene solución, esta siempre encontrara la respuesta, 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, el espacio de búsqueda de A* crece exponencial-mente. Usar una buena heuristica provee ventajas enormes, usualmente se queda sin espacio antes de quedarse sin tiempo, por lo que mantiene todos los nodos en memoria.

La complejidad temporal: 

O(b^d)

complejidad espacial:

O(b^d)

Heuristica

Se puede definir una heuristica como una técnica que aumenta la eficiencia de un proceso de búsqueda, la heuristica es un tipo de reglas, procedimientos, pasos a seguir a la hora de implementar una posible solucion a un problema planteado, de tal forma, que esta heuristica (reglas, procedimientos, pasos) nos ayudan a direccionar nuestra solución en busca de la mas optima o mejor solución. Los métodos de búsqueda heurística se basan de alguna información sobre la proximidad de cada estado a un estado meta, lo cual posibilita la exploración de los caminos más prometedores.

Admisibilidad

Una heuristica es admisible si el costo estimado es menor o igual que el costo mínimo de alcanzar al estado objetivo (h(n) ≤ h *(n)). La heuristica no debe sobrestimar el valor de la solución optima. 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.

Consistencia

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 llegar a la solución.Una heurística consistente es admisible, pero no todas las heurísticas admisibles son consistentes.

Monotonía

La monotonía es una condición aplicada a las funciones heurísticas. h heurística es monótona si, para cada nodo n y cada sucesor n‘ de n generada por una acción a, el costo estimado de alcanzar el objetivo de n no es mayor que el coste de paso de llegar al n’ más el costo estimado de alcanzar el objetivo de n’.

Cada heurística monótona también es admisible, monotonía es un requisito más estricto que la admisibilidad. En algunos algoritmos heurísticos, tales como A*, el algoritmo se puede considerar óptima si es monotónica.

Si h* es consistente, entonces f * crece de forma monótona en todos los caminos del árbol de búsqueda, es decir: si nj es sucesor de ni , entonces f *(nj ) ≥ f *(ni ).

Así:

h*(nj ) ≥ h*(ni ) – c(ni ,nj )

h*(nj ) + g(nj ) ≥ h*(ni ) + g(nj ) – c(ni ,nj )

h*(nj ) + g(nj ) ≥ h*(ni ) + g(ni ) + c(ni ,nj ) – c(ni ,nj )

f *(nj ) ≥ f *(ni )
Sea nm el mejor nodo meta. Si h* es consistente, entonces el algoritmo A* expande todos los nodos ni tal que f *(ni ) ≤ f *(nm )

Heuristicas mas informadas

Se dice que la heurística h1 es más informada que la heurística h2 si se cumple la propiedad:




Poder verificar esta propiedad implica que las dos heurísticas son admisibles.

Si una heurística es más informada que otroa al hacer uso de ella en el algoritmos A∗ se expandirán menos nodos durante la búsqueda, ya que su comportamiento será más en profundidad y habrá ciertos nodos que no se explorarán.

Esto podría hacer pensar que siempre hay que escoger la heurística más informada, pero se ha de tener en cuenta que la función heurística también tiene un tiempo de cálculo que afecta al tiempo de cada iteración, y que suele ser más costosa cuanto más informada sea la heurística.