Algoridmo de busqueda A*

Algoritmo de búsqueda A* (A estrella) 

El algoritmo de búsqueda A*, se encuentra entre  los algoritmos del conjunto de búsquedas con heurística, por ende es importante tener claro el concepto de lo que significa heurística ya que sin ello no se podría utilizar este algoritmo de manera correcta, este algoritmo, se caracteriza porque busca el camino más corto y de menos coste para hallar la solución del problema, por ende tiene en cuenta las dos cosas, lo que lo diferencia de costo uniforme y heurística pura.
Según lo anterior se llega a una fórmula que es considerada lo más importante en este algoritmo de búsqueda heurística que es la siguiente:
F(n) = g(n) + h(n)
En donde:
F(n) = Se entiende como el costo total
G(n) = se entiende como el valor del camino de un nodo a otro
H(n) = se entiende como el valor de la heurística de un nodo a otro
Otra cosa que hace importante este algoritmo es la estructura de abiertos y cerrados que maneja, ya que esto permite que no se irrumpa el correcto funcionamiento de este cuando se encuentren grafos cíclicos, esta estructura funciona haciendo que en la lista de abiertos se guarden los nodos que se van a evaluar, en la de cerrados se guardan los que ya se evaluaron, de esta manera, si en la estructura abierta existe un nodo que ya esté en cerrados esta se cerrara de forma inmediata.

¿Cómo funciona el Algoritmo A*?
Lo primero que se hace es expandir el primer nodo que se encuentre en la lista de abiertos, en caso de que este no sea un nodo objetivo, se calcula f(n) de todos los descendientes de este nodo, estos se insertan en la lista de abiertos, y el primer nodo o nodo raíz pasa de una vez a la lista de cerrados. Asi continua sucesivamente hasta que encuentre la solución, como se mencionó anteriormente si un nodo que este en abiertos es igual a uno que este en cerrados este pasa a cerrados de una vez.

¿Cuál es el algoritmo que utiliza A*?
1.  Crear una lista con el nodo raíz (L)
2.  Hasta que esta lista este vacía o se encuentre la solución:
Si, El primer elemento es la solución, ir al paso 3.
Sino, eliminar el primer elemento de la lista y adicionar sus sucesores aplicando F(n)
Luego, ordenar los elementos de acuerdo al costo y eliminar los repetidos de costo mayor
3.  Expandir todos los nodos con costo menor que el nodo solución

Recorrido
Paso 1

Abiertos	Cerrados
1+3

 Paso 2

Abiertos	Cerrados
2+2	1+4
2+2
2+4

Paso 3 

Abiertos	Cerrados
3+2	1+3
2+3	2+2
2+4	2+2

 Paso 4

Abiertos	Cerrados
3+2	1+3
4+2	2+2
2+4	2+2
	3+2

Paso 5  

Abiertos	Cerrados
4+2	1+3
4+2	2+2
2+4	2+2
	3+2
	2+3

Paso 6

Abiertos	Cerrados
4+2	1+3
4+2	2+2
5+2	2+2
	3+2
	2+3
	4+2

Paso 7

Abiertos	Cerrados
2+4	1+3
5+2	2+2
5+2	2+2
	3+2
	2+3
	4+2
	4+2

   
Paso 8 

Abiertos	Cerrados
3+3	1+3
5+2	2+2
5+2	2+2
	3+2
	2+3
	4+2
	4+2
	2+4

Paso 9

Abiertos	Cerrados
4+2	1+3
5+2	2+2
4+3	2+2
	3+2
	2+3
	4+2
	4+2
	2+4
	4+4

Paso 10

Abiertos	Cerrados
5+0	1+3
5+2	2+2
4+3	2+2
	3+2
	2+3
	4+2
	4+2
	2+4
	4+4
	4+2

Paso 11

Abiertos	Cerrados
5+2	1+3
4+3	2+2
	2+2
	3+2
	2+3
	4+2
	4+2
	2+4
	4+4
	4+2
	5+0 SOLUCION

Conclusiones
La complejidad del desarrollo del algoritmo A* está ligado directamente a que tan buena sea la heurística que se proporciona, como ya sabemos de cursos anteriores, la heurística es una aproximación cuantitativa de lo que falta para llegar a la solución, también sabemos que existen heurísticas muy bien definidas y otras no tanto… por ende esto es lo principal para determinar la complejidad que puede llegar a ser exponencial si este factor es de dudosa calidad, en cuanto al espacio requerido para ejecutarse se trata de un espacio exponencial respecto al tamaño del problema, ya que en un problema con muchos nodos esta se vuelve una tarea ardua al tener que considerar todos los sucesores con sus costos respectivos.