Búsqueda óptima en grafos de decisión

Cardiel Otero, Inés (2020). Búsqueda óptima 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: Búsqueda óptima en grafos de decisión
Author/s:
  • Cardiel Otero, Inés
Contributor/s:
  • Martínez Orga, Vicente
Item Type: Final Project
Degree: Grado en Ingeniería Informática
Date: June 2020
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 (9MB) | Preview

Abstract

Los problemas de búsquedas son el núcleo fundamental de muchos procesos inteligentes. Aparecen en todos los tipos de problemas donde la adquisición o recuperación de información y/o conocimiento constituye una parte de los mismos. En este contexto, la finalidad de este proyecto se centra en el desarrollo de un sistema informático basado en la toma de decisiones sobre un grafo, donde el principal objetivo será el de hallar el camino óptimo entre los distintos nodos del mismo. Cada uno de estos nodos va a representar las estaciones del metro de la ciudad de Praga, conformando así un total de 61 nodos. Para lograrlo, se aplicará uno de los algoritmos de búsqueda informada más conocido y del que posteriormente se hablará, denominada Algoritmo A*. Su implementación irá acompañada de una interfaz gráfica a través de la cual el usuario tendrá la oportunidad de interactuar con el sistema. Con el propósito de que este sistema sea estable y satisfaga las necesidades del usuario dentro del tiempo establecido para ello, se llevará a cabo para el desarrollo del proyecto, una metodología propia de la Ingeniería del Software. Ésta consta de una serie de etapas perfectamente definidas (Especificación de requisitos software, Diseño de alto nivel, Diseño de bajo nivel, Implementación, Plan de Pruebas y Evaluación de la fase). Señalar que, en proyectos software reales, la división en distintas fases es fundamental, sobre todo si la complejidad de su desarrollo es elevada, pues permite establecer un reparto de objetivos claves a cumplir en deadlines concretos, los cuales además, se pueden ir mejorando y refinando en sucesivas fases. Así, para simular un proyecto real, se ha decidido establecer dos fases para el desarrollo de este trabajo, en cada uno de los cuales se detallarán las etapas mencionadas previamente.---ABSTRACT---In this context, this project aims to develop a computer system based on graphs decision-making, where the main objective will be to find the optimal path between the different nodes of the project. Each of these nodes will represent the metro stations of the city of Prague, making up a total of 61 nodes. To achieve this, one of the best-known and most widely-discussed informed search algorithms will be applied, called Algorithm A*. Its implementation will be accompanied by a graphical interface through which the user will have the opportunity to interact with the system. To achieve this system to be stable and meet the needs of the user within the time established for this purpose, a methodology specific to Software Engineering will be carried out for the development of the project. This consists of a series of perfectly defined stages (Specification of Software Requirements, High-Level Design, Low-Level Design, Implementation, Test Plan and Phase Evaluation). Note that, in real software projects, the division in different phases is essential, especially if the complexity of its development is high, as it allows to establish a distribution of key objectives to be met in specific deadlines, which can also be improved and refined in successive phases. To simulate a real project, it has been decided to establish two phases for the development of this work, in each of which the above mentioned stages will be detailed.

More information

Item ID: 63034
DC Identifier: http://oa.upm.es/63034/
OAI Identifier: oai:oa.upm.es:63034
Deposited by: Biblioteca Facultad de Informatica
Deposited on: 15 Jul 2020 14:43
Last Modified: 15 Jul 2020 14:43
  • 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