Citation
Gonzales Infante, Alan
(2018).
Aplicación de algoritmos de búsqueda en la
optimización de caminos de coste mínimo en grafos de
decisión.
Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.
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.