Algoritmos Voraces y Heurísticas: Un enfoque en el problema de la Ruta mínima

Introducción: El problema de la ruta más corta o ruta de mínimo costo, ha sido uno de los temas más estudiados por áreas del conocimiento como la Investigación de Operaciones, la Ciencias de la Computación y la Decisión, las Telecomunicaciones, la Distribución en Planta, la Planeación de Proyectos,...

Full description

Autores:: Lasso Cardona, Luis Adrián
Franco Ocampo, Diego Fernando
Agudelo Acevedo, Alexander

Tipo de recurso:: Article of journal

Fecha de publicación:: 2020

Institución:: Corporación Universidad de la Costa

Repositorio:: REDICUC - Repositorio CUC

Idioma:: eng

Description
Summary:	Introducción: El problema de la ruta más corta o ruta de mínimo costo, ha sido uno de los temas más estudiados por áreas del conocimiento como la Investigación de Operaciones, la Ciencias de la Computación y la Decisión, las Telecomunicaciones, la Distribución en Planta, la Planeación de Proyectos, entre otras, buscando, por ejemplo; optimizar y reducir los costos que representan la distribución de mercancías, obtener la mínima cantidad de tiempo necesaria para finalizar un proyecto, o calcular la ruta más corta posible entre ordenadores conectados a una red. Objetivo: Estudiar el comportamiento de tres algoritmos voraces que permiten calcular la ruta de mínimo costo entre dos puntos (estado inicial y estado objetivo) en un grafo ponderado y con heurísticas. Metodología: Se implementó una aplicación en Java, y se ajustaron los algoritmos Greedy, A* y Dijkstra al problema en cuestión. Posteriormente se diseñaron dos casos de instancia, una negativa y otra positiva. Resultados: En los resultados de instancia negativa se modificó la heurística del nodo para permitir al algoritmo seleccionado escapar de óptimos locales y así, obtener un resultado completo, es decir llegar al estado objetivo, que, en algunas ocasiones, no necesariamente será el resultado más óptimo. Conclusiones: Mediante la comparación entre los tres algoritmos se pudo determinar que el algoritmo de Dijkstra siempre arroja resultados completos y óptimos. Por su parte, Greedy y A*, necesitan de heurísticas para llegar a un resultado completo, pero no óptimo.

Algoritmos Voraces y Heurísticas: Un enfoque en el problema de la Ruta mínima

Publicaciones similares