##plugins.themes.bootstrap3.article.main##

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

Resumen

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.

Descargas

Los datos de descargas todavía no están disponibles.

##plugins.themes.bootstrap3.article.details##

Cómo citar
Lasso Cardona, L. A., Franco Ocampo, D. F., & Agudelo Acevedo, A. (2020). Algoritmos Voraces y Heurísticas: Un enfoque en el problema de la Ruta mínima. Inge CuC, 16(2), 67–85. https://doi.org/10.17981/10.17981/ingecuc.16.2.2020.05
Sección
Artículos