Cálculo de trayectos mediante algoritmos de búsqueda informada sobre grafos ponderados no dirigidos

Abstract

El problema de búsqueda es un campo ampliamente desarrollado en el área de la Inteligencia Artificial. En este proyecto se propone la implementación de un sistema de búsqueda de trayectos en grafos ponderados no dirigidos minimizando el coste de dichos caminos. Como particularidad sobre los algoritmos ya existentes, el sistema emplea una clasificación de los nodos del grafo que permite obtener la solución del problema de una forma más eficiente. A su vez, esta clasificación permite reducir de manera considerable el espacio necesario para almacenar toda la información acerca de la definición del problema. La herramienta es aplicable sobre distintos grafos siempre y cuando cumplan una serie de condiciones. El sistema presentado se ha aplicado sobre un ejemplo concreto de grafo: la Red de Metro de Barcelona. El usuario solicitará el cálculo de un trayecto entre dos estaciones cualesquiera de la red y el sistema responderá con un camino a través del grafo, que representa el trayecto entre las dos estaciones dadas minimizando la duración de éste e imprimiendo dicho tiempo/coste mínimo. Gracias a la arquitectura software de sistema y la modularidad del mismo pueden realizarse modificaciones de manera sencilla tanto en la definición del problema, ya sea otra red del mismo transporte público u otro tipo de grafo, como en el algoritmo de búsqueda empleado para el cálculo de los caminos de coste mínimo.