Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Artículo científico |
| Langue: | en |
| Publié: |
Corporación Universitaria de la Costa
2020
|
| Sujets: | |
| Accès en ligne: | https://www.redalyc.org/articulo.oa?id=497779337005 |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
Table des matières:
- Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem Luis Adrián Lasso-Cardona Diego Fernando Franco-Ocampo Alexander Agudelo-Acevedo Ingeniería star Greedy Dijkstra heuristics cost matrix 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. Methodoly— 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. 2020 artículo científico 0122-6517 https://www.redalyc.org/articulo.oa?id=497779337005 en http://www.redalyc.org/revista.oa?id=4977 INGE CUC application/pdf Corporación Universitaria de la Costa INGE CUC (Colombia) Num.2 Vol.16