Aplicación de algoritmos de búsqueda en la optimización de caminos de coste mínimo en grafos de decisión

Abstract

Este proyecto se basa en la comodidad para las personas en el momento que se desee transportar en el metro de Madrid, ya que a diario hacemos uso del transporte público, en este caso nos centraremos en el metro de Madrid. Se basa en buscar todas las posibles rutinas desde una estación origen al destino, mostrandote el programa la ruta mas corta para llegar al destino. La lógica del algoritmo de búsqueda puede ir dirigido a cualquier grafo. El programa facilitará al usuario la ruta más corta al destino que quiere llegar, habrá diferentes formas de interactuar con la aplicación, será intuitiva y fácil, ya que se ha realizado un análisis para diferentes perfiles de usuarios. Existen diferentes tipos de algoritmos para este tipo de búsqueda de camino más corto, hemos obtado por emplear el algoritmo A estrella, que se basa en recorrer todas las posibles rutas que pueden existir en el mapa de metro, una vez recorrido todas las rutas posibles calcula el peso de cada una de ellas para dar la solución más óptima posible al usuario. Se ha realizado mediante el entorno del netbeans, con el desarrollo tanto de la parte back-end, front y base de datos en Java, ya que he querido emplear los conocimientos obtenidos en la carrera. La parte front se ha realizado con Jframe, backend con Java y se ha almacenado los datos en objetos Java(más adelante explicaremos la razón de esta elección para almacenar los datos). Como en diferentes proyectos, debido a su complejidad se ha divido en dos fases, adaptándose a la medida posible a los plazos estimados y realizando las pruebas y el desarrollo pertinente en las mismas. Al final del proyecto se realizará un análisis de las mejores que se pueden implementar y optimizar todo lo implementado en el proyecto.---ABSTRACT---This project is based on comfort for people, since we use public transport every day, in this case we will focus on the Madrid metro, the logic of the search algorithm can be directed to any graph. The program will provide the user with the shortest route to the destination they want to reach, there will be different ways of interacting with the application, it will be intuitive and easy, since an analysis has been carried out for different user profiles. There are different types of algorithms for this type of shortest path search, in this case the Star A algorithm has been used, which is based on traversing all the possible routes that may exist in the subway map, once all the Possible routes calculates the weight of each of them to give the user the most optimal solution possible. It has been done through the netbeans environment, with the development of both the back-end, front and database in Java, since I wanted to use the knowledge obtained in the race. The front part has been done with Jframe, backend with Java and I have stored the data in Java objects. As in different projects, due to its complexity, it has been divided into two phases, this project, adapting to the possible extent to the estimated deadlines and carrying out the tests and the pertinent development in them. At the end of the project an analysis will be made of the best that can be implemented and optimize everything implemented in the project.