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

Fernández Orchando, Jesús Manuel (2018). Cálculo de trayectos mediante algoritmos de búsqueda informada sobre grafos ponderados no dirigidos. Proyecto Fin de Carrera / Trabajo Fin de Grado, E.T.S. de Ingenieros Informáticos (UPM), Madrid, España.

Description

Title: Cálculo de trayectos mediante algoritmos de búsqueda informada sobre grafos ponderados no dirigidos
Author/s:
  • Fernández Orchando, Jesús Manuel
Contributor/s:
  • Martínez Orga, Vicente
Item Type: Final Project
Date: July 2018
Subjects:
Faculty: E.T.S. de Ingenieros Informáticos (UPM)
Department: Inteligencia Artificial
Creative Commons Licenses: Recognition - No derivative works - Non commercial

Full text

[img]
Preview
PDF - Requires a PDF viewer, such as GSview, Xpdf or Adobe Acrobat Reader
Download (1MB) | Preview

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.

More information

Item ID: 51640
DC Identifier: http://oa.upm.es/51640/
OAI Identifier: oai:oa.upm.es:51640
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 16 Jul 2018 07:34
Last Modified: 16 Jul 2018 07:35
  • Logo InvestigaM (UPM)
  • Logo GEOUP4
  • Logo Open Access
  • Open Access
  • Logo Sherpa/Romeo
    Check whether the anglo-saxon journal in which you have published an article allows you to also publish it under open access.
  • Logo Dulcinea
    Check whether the spanish journal in which you have published an article allows you to also publish it under open access.
  • Logo de Recolecta
  • Logo del Observatorio I+D+i UPM
  • Logo de OpenCourseWare UPM