Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem
| Autor: | Luis Adrián Lasso Cardona, Diego Fernando Franco Ocampo, Alexander Agudelo Acevedo |
|---|---|
| Jazyk: | English<br />Spanish; Castilian |
| Rok vydání: | 2020 |
| Předmět: | |
| Zdroj: | Inge-Cuc, Vol 16, Iss 1, Pp 67-85 (2020) |
| Druh dokumentu: | article |
| ISSN: | 0122-6517 2382-4700 |
| DOI: | 10.17981/ingecuc.16.2.2020.05 |
| Popis: | 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. |
| Databáze: | Directory of Open Access Journals |
| Externí odkaz: |
|