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

Qiu, Yifu (2017). 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.

Description

Title: Aplicación de algoritmos de búsqueda en la optimización de caminos de coste mínimo en grafos de decisión
Author/s:
  • Qiu, Yifu
Contributor/s:
  • Martínez Orga, Vicente
Item Type: Final Project
Degree: Grado en Ingeniería Informática
Date: June 2017
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

Debido a la gran cantidad de estaciones de metro que hay en Comunidad de Madrid, para las personas que no utilizan coches y que tienen que ir a trabajar lejos, es muy importante encontrar una ruta óptima entre su estación de partida y su estación de meta. El presente proyecto consiste en desarrollar una aplicación de toma de decisión en un mapa para desplazarse entre estaciones de ese mapa. Se ha elegido el mapa de metro de la Comunidad de Madrid como el mapa por defecto y, el algoritmo A* para determinar la ruta óptima entre estación de partida y estación de meta. El mapa de metro de Madrid contiene 241 estaciones (no están incluidas las estaciones de metro ligero), el usuario de la aplicación elige una estación de partida y una de meta, como resultado la aplicación muestra una ruta óptima al usuario. Una vez implementado la función de cálculo de la ruta óptima entre las estaciones de metro de Madrid, se ha hecho que aparte del mapa de metro de la Comunidad de Madrid, la aplicación permite al usuario introducir cualquier otro mapa al sistema, siempre y cuando introduzca también las informaciones de dicho mapa (nombre, coordenadas, líneas…), y que deja al usuario calcular la ruta óptima entre las estaciones de dicho mapa.---ABSTRACT---Due to the large number of metro stations that are in Community of Madrid, for people who do not use cars and they must go to work far, it is very important to find an optimal path between his origin station and his destiny station. The present project consists of developing an application of pathfinding on a map to move between stations of that map. The metro map of the Community of Madrid has been chosen as the default map and the algorithm A * to determine the optimal path between the origin station and the destiny station. The chosen map contains 241 stations (light rail stations are not included), the user of the application chooses an origin station and a destiny station, as a result the application shows an optimal path to the user. Once the function of calculating the optimal path between Madrid's metro stations has been successful implemented, apart from the metro map of the Community of Madrid, the application allows the user to introduce any other map to the system, as long as it also introduces the information of the map (name, coordinates, lines ...), and that allows the user to calculate the optimal path between the stations of the map.

More information

Item ID: 55748
DC Identifier: http://oa.upm.es/55748/
OAI Identifier: oai:oa.upm.es:55748
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 17 Jul 2019 10:53
Last Modified: 17 Jul 2019 10:53
  • 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