Laberinto con algoritmos de busqueda y pygame.

OBJETIVOS :

Implementar algoritmos de búsqueda en python.

Implementar la librería de pygame en nuestro juego.

Recordar conocimientos adquiridos. 

Explicación del algoritmo A*

El algoritmo A* ^[24]es un algoritmo de búsqueda que puede ser empleado para el cálculo de caminos mínimos en una red. Se va a tratar de un algoritmo heurístico, ya que una de sus principales características es que hará uso de una función de evaluación heurística, mediante la cual etiquetará los diferentes nodos de la red y que servirá para determinar la probabilidad de dichos nodos de pertenecer al camino óptimo.

Esta función de evaluación que etiquetará los nodos de la red estará compuesta a su vez por otras dos funciones. Una de ellas indicará la distancia actual desde el nodo origen hasta el nodo a etiquetar, y la otra expresará la distancia estimada desde este nodo a etiquetar hasta el nodo destino hasta el que se pretende encontrar un camino mínimo. Es decir, si se pretende encontrar el camino más corto desde el nodo origen s, hasta el nodo destino t, un nodo intermedio de la red n tendría la siguiente función de evaluación f(n) como etiqueta:

f(n)= g(n) + h(n)

Donde:

-g(n) indica la distancia del camino desde el nodo origen s al n.

-h(n) expresa la distancia estimada desde el nodo n hasta el nodo destino t.

h(n) se trata de una función heurística, expresa la idea de cuán lejos aún se está de alcanzar el nodo destino, y de su correcta elección dependerá en gran medida el rendimiento del algoritmo A* al aplicarlo en una red. 

La imagen anterior muestra como se implementa esta solución a nuestro proyecto.



Algoritmo hill climbing.


En ciencia de la computación, el algoritmo hill climbing, también llamado Algoritmo de Escalada Simple o Ascenso de colinas es una técnica de optimización matemática que pertenece a la familia de los algoritmos de búsqueda local. Es un algoritmo iterativo que comienza con una solución arbitraria a un problema, luego intenta encontrar una mejor solución variando incrementalmente un único elemento de la solución. Si el cambio produce una mejor solución, otro cambio incrementar se le realiza a la nueva solución, repitiendo este proceso hasta que no se puedan encontrar mejoras. Suele llamarse a esta búsqueda algoritmo voraz local, porque toma un estado vecino "bueno" sin pensar en la próxima acción.






Conclusiones recomendaciones y algo mas.........

Se recomienda tener conocimiento medio en el tema de la programación.
También la investigación por parte del estudiante es fundamental para la culminacion de este proyecto.
Se recomienda finalmente profundizar conocimientos en python y sus derivadas como la librería de pygame que es de mucha utilidad en nuestro campo, y practicar y recordar conocimientos adquiridos.
Nuestro proyecto fue realizado con la ayuda de python y la librería de pygame como lo muestra la imagen adjunta, que demuestra el código fuente, y la demostración del juego.

Fig.2. Código en python.

 Realizado por: Fabrico Gomez Avila.