Este trabajo estudia la mejor manera de encontrar el camino óptimo entre dos nodos específicos en un grafo. Para ello, se va a utilizar el algoritmo A* (A Estrella), un método de búsqueda “mejor primero” que selecciona nodos basándose en una función coste y otra heurística para determinar el camino mínimo de un origen a un destino. Este algoritmo se ha desarrollado en una versión adaptada del mapa del metro de Estocolmo, permitiendo a los usuarios elegir su punto de partida y destino para calcular la ruta óptima entre ambas estaciones. La implementación se ha realizado en Python, un lenguaje adecuado para el manejo de estructuras de datos complejas como los grafos, destacando por su versatilidad y la disponibilidad de bibliotecas especializadas. Para facilitar la interacción del usuario con el sistema, se ha desarrollado una interfaz web usando HTML, que es accesible y comprensible para usuarios de diversos niveles técnicos. Esta interfaz, que también integra CSS y Python, permite a los usuarios seleccionar estaciones mediante desplegables, proporcionando una experiencia de usuario fluida y eficiente. La aplicación de este algoritmo ayudará a optimizar las rutas de un origen a un destino en cuanto a tiempo y distancia, mejorando la experiencia del usuario y fomentando el uso del transporte público. Esto será una opción más sostenible con un menor impacto en el medio ambiente.
ABSTRACT
This work studies the best way to find the optimal path between two specific nodes in a graph. For this purpose, the A* (A Star) algorithm will be used, a “best-first” search method that selects nodes based on a cost function and a heuristic function to determine the shortest path from a source to a destination. This algorithm has been developed using an adapted version of the Stockholm metro map, allowing users to choose their starting point and destination to calculate the optimal route between the two stations. The implementation has been carried out in Python, a language suitable for handling complex data structures like graphs, known for its versatility and the availability of specialized libraries. To facilitate user interaction with the system, a web interface has been developed using HTML, which is accessible and understandable to users of various technical levels. This interface, which also integrates CSS and Python, allows users to select stations through dropdown menus, providing a smooth and efficient user experience. The application of this algorithm will help optimize routes from a source to a destination in terms of time and distance, improving the user experience and encouraging the use of public transportation. This will be a more sustainable option with a lower environmental impact.
Este trabajo estudia la mejor manera de encontrar el camino óptimo entre dos nodos específicos en un grafo. Para ello, se va a utilizar el algoritmo A* (A Estrella), un método de búsqueda “mejor primero” que selecciona nodos basándose en una función coste y otra heurística para determinar el camino mínimo de un origen a un destino. Este algoritmo se ha desarrollado en una versión adaptada del mapa del metro de Estocolmo, permitiendo a los usuarios elegir su punto de partida y destino para calcular la ruta óptima entre ambas estaciones. La implementación se ha realizado en Python, un lenguaje adecuado para el manejo de estructuras de datos complejas como los grafos, destacando por su versatilidad y la disponibilidad de bibliotecas especializadas. Para facilitar la interacción del usuario con el sistema, se ha desarrollado una interfaz web usando HTML, que es accesible y comprensible para usuarios de diversos niveles técnicos. Esta interfaz, que también integra CSS y Python, permite a los usuarios seleccionar estaciones mediante desplegables, proporcionando una experiencia de usuario fluida y eficiente. La aplicación de este algoritmo ayudará a optimizar las rutas de un origen a un destino en cuanto a tiempo y distancia, mejorando la experiencia del usuario y fomentando el uso del transporte público. Esto será una opción más sostenible con un menor impacto en el medio ambiente.
ABSTRACT
This work studies the best way to find the optimal path between two specific nodes in a graph. For this purpose, the A* (A Star) algorithm will be used, a “best-first” search method that selects nodes based on a cost function and a heuristic function to determine the shortest path from a source to a destination. This algorithm has been developed using an adapted version of the Stockholm metro map, allowing users to choose their starting point and destination to calculate the optimal route between the two stations. The implementation has been carried out in Python, a language suitable for handling complex data structures like graphs, known for its versatility and the availability of specialized libraries. To facilitate user interaction with the system, a web interface has been developed using HTML, which is accessible and understandable to users of various technical levels. This interface, which also integrates CSS and Python, allows users to select stations through dropdown menus, providing a smooth and efficient user experience. The application of this algorithm will help optimize routes from a source to a destination in terms of time and distance, improving the user experience and encouraging the use of public transportation. This will be a more sustainable option with a lower environmental impact. Read More
Related posts:
Algoritmo de recomendación de restaurantes para grupos basado en bases de datos con grafos
System for the design and implementation of user experience assessments with UEQ
Desarrollo de una aplicación web para backtesting de estrategias de trading
Diseño e implementación de una plataforma de gestión financiera personal
Aplicación para el seguimiento eficiente de gastos personales
Estudio y prototipo exploratorio para el análisis, detección y predicción de patrones oscuros web con reconocimiento de imágenes