Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem

Resumen

Introduction: The problem of the shortest route or minimum cost route, has been one of the topics most studied by areas of knowledge such as Operations Research, Computer Science and Decision, Telecommunications, Plant Distribution, Planning of Projects, among others, searching, for example; optimize and reduce the costs that represent the distribution of goods, obtain the minimum amount of time necessary to complete a project, or calculate the shortest possible route between computers connected to a network.

Objective: We will study the behavior of three voracious algorithms that allow us to calculate the minimum cost route between two points (initial state and objective state) in a weighted graph and with heuristics.

Method: Was implemented in Java, and the Greedy, A* and Dijkstra algorithms were adjusted to the problem in question. Subsequently, two instance cases were designed, one negative and one positive.

Results: In the negative instance results the heuristic of the node was modified to allow the selected algorithm to escape from local optima and thus obtain a complete result, that is to say reach the objective state, which, in some cases, will not necessarily be the most optimal result.

Conclusions: By comparing the three algorithms, it was determined that the Dijkstra algorithm always yields complete and optimal results. For its part, Greedy and A *, need heuristics to reach a complete result, but not optimal.

Palabras clave: Grafo ponderado, matriz de costos, matriz de adyacencia, ; ruta óptima, ; algoritmos voraces, búsqueda codiciosa, heurística, Greedy, A-star, Dijkstra

Referencias

N. Ojekudo & N. Akpan. "Anapplication of Dijkstra’s Algorithm to shortest route problem". IOSR Journal of Mathematics (IOSR-JM), 13(1). 2017. DOI: 10.9790/5728-1303012032

B. Obregón. "Teoría de redes: El problema de la ruta más corta". Thesis, Programa de Maestría y Doctorado en Ingeniería, Universidad Nacional Autónoma de México. 2005. Available at: http://www.ptolomeo.unam.mx:8080/xmlui/bitstream/handle/132.248.52.100/539/obregonquintana.pdf?sequence=12

J. Barelles. "Algoritmos para la resolución de problemas en redes". Thesis, Matemática Computacional, Universitat Jaume I, 2017. Available at: http://repositori.uji.es/xmlui/bitstream/handle/10234/173687/TFG_2017_BarellesMenes_Jorge.pdf?sequence=1&isAllowed=y

Y. Talebiy and H. Rashmanlouz. "Application Of Dominating Sets In Vague Graphs". 2017. Available at: https://www.emis.de/journals/AMEN/2017/AMEN-170503.pdf

M. Dod. "Domination in graphs with application to network reliability". Doctor, Faculty of Mathematics and Computer Science of the Technische Universitat Bergakademie Freiberg, Deutschland. 2015. Available at: http://tubaf.qucosa.de/api/qucosa%3A23011/attachment/ATT-0/

S. Guze. "An application of the selected graph theory domination concepts to transportation networks modelling". Scientific Journals Zeszyty Naukowe, [Online]. 52 (124), 97‒102. 2017. DOI: 10.17402/250

S. Vishwanathan, N. Schraudolph, R. Kondor and K. Borgwardt. "Graph Kernels". Journal of Machine Learning Research. 11. 2010. Available at: http://www.jmlr.org/papers/volume11/vishwanathan10a/vishwanathan10a.pdf

K. Abdulkalek and A. Kilicman. "Topologies on the Edges Set of Directed Graphs". International Journal of Mathematical Analysis. 12(2), 71-84. 2018. https://doi.org/10.12988/ijma.2018.814

N. Jicy and M. Sunil. "Some new connectivity parameters for weighted graphs". Journal of Uncertainty in Mathematics Science. 2014. https://doi.org/10.5899/2014/jums-00002

A. Ban. (2017). Decomposing Weighted Graphs. Blavatnik School of Computer Science, Tel Aviv University, Tel Aviv, Israel. [Online]. Available at: https://doi.org/10.1002/jgt.22124

S. Mathew. "Partial trees in weighted graphs-I, Proyecciones". Journal of Mathematics, Universidad Católica del Norte, Chile, 30(2), 163-174. 2011. https://doi.org/10.1002/jgt.22124

C. Salas. "Un Algoritmo de Dos Fases para la Optimización de Costos en el Traslado de Cargas con Exceso de Dimensiones". Tesis de Maestría. Universidad Autónoma del Estado de Hidalgo, México, 2014. Available at: http://dgsa.uaeh.edu.mx:8080/bibliotecadigital/bitstream/handle/231104/1918/AT18381.pdf?sequence=3&isAllowed=y

G. Gonzalez and F. Gonzalez. "Metaheurísticas aplicadas al ruteo de vehículos. Un caso de estudio. Parte 2: algoritmo genético, comparación con una solución heurística". Revista Ingeniería e Investigación. [Online]. 27(1), 149-157. 2007. Available at: https://revistas.unal.edu.co/index.php/ingeinv/article/view/14795/15626

L. Rodríguez and A. Varona. "Técnicas de diseño de algoritmos. Algoritmos voraces". Departamento de Electricidad y Electrónica. Facultad de Ciencia y Tecnología, Universidad del País Vasco. 2015. Available at: https://ocw.ehu.eus/pluginfile.php/9410/mod_resource/content/1/03_Algoritmos_Voraces/03_Algoritmos_Voraces.pdf

A. Subhadra. "Greedy Algorithms: Analysis, Design & Applications". International Journal of Informative & Futuristic Research. [Online]. 3, 1749-1764. 2016. Available at: https://www.academia.edu/21855750/Greedy_Algorithms_Analysis_Design_and_Applications

D. Maxwell. "Optimal Structure Identification With Greedy Search". Journal of Machine Learning Research. [Online]. 3, 507-554. 2002. Available at: http://www.jmlr.org/papers/volume3/chickering02b/chickering02b.pdf

B. Simmons, C. Hoeppke and W. "Sutherland. Beware greedy algorithms". Journal of Animal Ecology. 88, 804–807. 2019. https://doi.org/10.1111/1365-2656.12963

A. Malik, A. Sharma and V. Saroha. "Greedy Algorithm". International Journal of Scientific and Research Publications. 3(8). 2013. Available at: http://www.ijsrp.org/research-paper-0813/ijsrp-p2014.pdf

O. Debdi. "Aprendizaje Interactivo de Algoritmos Voraces: del Enfoque Individual al Colaborativo". Tesis Doctoral. Universidad Rey Juan Carlos. 2014. Available at: https://eciencia.urjc.es/bitstream/handle/10115/13242/Tesis-OuafaeDebdi-Final.pdf?sequence=1&isAllowed=y

U. Faigle. "The greedy algorithm for partially ordered sets, Discrete Mathematics". 28, 153-159. 1979. https://doi.org/10.1016/0012-365X(79)90092-X

M. Abad. Algoritmos voraces, Facultat d’Informàtica, U.P.C. 2017. Available at: http://www.cs.upc.edu/~mabad/ADA/curso0708/GREEDY.pdf

N. Shrikant and A. Selvakumar. "Implementation of A* Algorithm to Autonomous Robots-A Simulation Study". 1(3). 2018. Available at: https://pdfs.semanticscholar.org/2c58/e7674a64615a2ae0cef64abddfce0e6dea90.pdf

P. Sudhakara and V. Ganapathy. "Trajectory Planning of a Mobile Robot using Enhanced A-Star Algorithm" Indian Journal of Science and Technology, 9(41). 2016. https://doi.org/10.17485/ijst/2016/v9i41/93816

J. Peng, Y. Huang and G. Luo. "Robot Path Planning Based on Improved A* Algorithm". Cybernetics And Information Technologies. 15(2). 2015. https://doi.org/10.1515/cait-2015-0036

R. Rodríguez and M. Lazo. "Búsquedas de caminos mínimos haciendo uso de grafos reducidos". Ing. Ind. 38(1). 2017. Available at: http://scielo.sld.cu/scielo.php?script=sci_arttext&pid=S1815-59362017000100004

F. Duchon, A. Babineca, M. Kajana, P. Beño, M. Floreka, T. Ficoa and L. Jurišica. "Path planning with modified A star algorithm for a mobile robot, Modelling of Mechanical and Mechatronic Systems MMaMS". 2014. Available at: https://www.sciencedirect.com/science/article/pii/S187770581403149X. https://doi.org/10.1016/j.proeng.2014.12.098

X. Dai, S. Long, Z. Zhang and D. Gong. "Mobile Robot Path Planning Based on Ant Colony Algorithm With A* Heuristic Method". Frontiers Neurorobotics. 2019. https://doi.org/10.3389/fnbot.2019.00015

A. KumarGuruj, H. Agarwal and D. Parsediya. "Time-Efficient A* Algorithm for Robot Path Planning, Procedia Technology". 23, 144-149. 2016. https://doi.org/10.1016/j.protcy.2016.03.010

A. Beriain. Matemáticas en un Navegador GPS: Algoritmos de Camino más Corto y Calculo de Posición, Grado en Matemáticas, Universidad de la Rioja. 2016. Available at: https://biblioteca.unirioja.es/tfe_e/TFE002201.pdf

M. Nosrati, R. Karimi and H. Hasanvand. "Investigation of the * (Star) Search Algorithms: Characteristics, Methods and Approaches". World Applied Programming. 2(4), 251-256. 2012. Available at: https://pdfs.semanticscholar.org/831f/f239ba77b2a8eaed473ffbfa22d61b7f5d19.pdf

N. Gupta, K. Mangla, A. Kumar and M. Umar. "Applying Dijkstra’s Algorithm in Routing Process". International Journal of New Technology and Research (IJNTR). 2(5), 122-124. 2016. Available at: https://www.ijntr.org/download_data/IJNTR02050040.pdf

Descargas

La descarga de datos todavía no está disponible.
Publicado
2020-05-15
Cómo citar
Lasso Cardona, L., Franco Ocampo, D., & Agudelo Acevedo, A. (2020). Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem. INGE CUC, 16(2). https://doi.org/10.17981/10.17981/ingecuc.16.2.2020.05