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

Abstract

El presente proyecto tratará sobre la aplicación de un algoritmo que ayude a tomar decisiones en un grafo para llegar desde un nodo a otro. Dicho grafo representará el mapa de la ciudad de Valencia, el cual tendrá tantos nodos como estaciones existan. Para dicho proyecto el objetivo es preparar y documentar el proceso que se daría a lo largo de un proyecto real de software estableciendo así tanto los requisitos como los dise˜nos de alto y bajo nivel para el mismo, un plan de pruebas, la implementación del proyecto en lenguaje java y una evaluación final que ayude a determinar la solidez de la aplicación de ese algoritmo en dicho grafo. Al igual que en los proyectos software, el desarrollo del mismo se hará en varias fases bien definidas entre sí, en las cuales se irá depurando y mejorando. Dada la dificultad del proyecto, el numero de fases establecidas ha sido de dos. En ambas se aplicarán los mismos criterios de programación y desarrollo de la documentación, entregándose así en la memoria de seguimiento la primera fase del proyecto casi en su totalidad siendo de esta forma establecida como primer Deadline de entrega del proyecto. La segunda fase, se dedicará a cumplir con los requisitos que no hayan sido superados a lo largo del primer ciclo o que se hayan decidido a˜nadir tras la finalización de la primera fase (re-análisis), finalizando así todo el proyecto en la entrega del segundo Deadline y habiendo solucionado los posibles errores de implementación encontrados en la evaluación de la primera fase.---ABSTRACT---The following project will show the application of decision making algorythms in the selection of the fastest path between two nodes. This selection will be done in a specific graph: Valencia’s Underground System. The number of nodes will be defined by the number of stations that this map has. This project will be defined and done like a software engineering project, establishing a system of requirements, the high level design and the low level design. Also, a system test will be done and the implementation of the proyect using Java language. Finally, an evaluation will be applied using the test system in order to find out the mistakes and subsequently, in a second phase fix them. The second phase will be used to finish all the requirements (including the new ones) and the mistakes of the first phase will be arranged. There will be two deadlines along the development: the first one will coincide with the delivery of the tracking memory and the second one will be on the delivery of the final memory.