Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem
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; optimiz...
| Main Authors: | , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Universidad de la Costa
2020-05-01
|
| Series: | Inge-Cuc |
| Subjects: | |
| Online Access: | https://revistascientificas.cuc.edu.co/ingecuc/article/view/2752 |
| _version_ | 1818893350682492928 |
|---|---|
| author | Luis Adrián Lasso Cardona Diego Fernando Franco Ocampo Alexander Agudelo Acevedo |
| author_facet | Luis Adrián Lasso Cardona Diego Fernando Franco Ocampo Alexander Agudelo Acevedo |
| author_sort | Luis Adrián Lasso Cardona |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-19T18:11:12Z |
| format | Article |
| id | doaj.art-ed579d3ea78740bbb601bfe6f9c6e687 |
| institution | Directory Open Access Journal |
| issn | 0122-6517 2382-4700 |
| language | English |
| last_indexed | 2024-12-19T18:11:12Z |
| publishDate | 2020-05-01 |
| publisher | Universidad de la Costa |
| record_format | Article |
| series | Inge-Cuc |
| spelling | doaj.art-ed579d3ea78740bbb601bfe6f9c6e6872022-12-21T20:11:19ZengUniversidad de la CostaInge-Cuc0122-65172382-47002020-05-01161678510.17981/ingecuc.16.2.2020.05Voracious and Heuristic Algorithms: A focus on the Minimum Path ProblemLuis Adrián Lasso Cardona0https://orcid.org/0000-0002-3354-1554Diego Fernando Franco Ocampo1https://orcid.org/0000-0002-4797-8263Alexander Agudelo Acevedo2https://orcid.org/0000-0003-2200-3491Universidad del Valle. Sede Buga, (Colombia)Diego Fernando Franco OcampoUniversidad del Valle. Sede Buga, (Colombia)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.https://revistascientificas.cuc.edu.co/ingecuc/article/view/2752grafo ponderadomatriz de costosmatriz de adyacenciaruta óptimaalgoritmos voracesbúsqueda codiciosaheurísticagreedya-stardijkstra |
| spellingShingle | Luis Adrián Lasso Cardona Diego Fernando Franco Ocampo Alexander Agudelo Acevedo Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem Inge-Cuc grafo ponderado matriz de costos matriz de adyacencia ruta óptima algoritmos voraces búsqueda codiciosa heurística greedy a-star dijkstra |
| title | Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem |
| title_full | Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem |
| title_fullStr | Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem |
| title_full_unstemmed | Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem |
| title_short | Voracious and Heuristic Algorithms: A focus on the Minimum Path Problem |
| title_sort | voracious and heuristic algorithms a focus on the minimum path problem |
| topic | grafo ponderado matriz de costos matriz de adyacencia ruta óptima algoritmos voraces búsqueda codiciosa heurística greedy a-star dijkstra |
| url | https://revistascientificas.cuc.edu.co/ingecuc/article/view/2752 |
| work_keys_str_mv | AT luisadrianlassocardona voraciousandheuristicalgorithmsafocusontheminimumpathproblem AT diegofernandofrancoocampo voraciousandheuristicalgorithmsafocusontheminimumpathproblem AT alexanderagudeloacevedo voraciousandheuristicalgorithmsafocusontheminimumpathproblem |