Comparación de Estrategias de Búsqueda no Informada y Heurística en la Resolución de Problemas de Optimización de Rutas: Un Estudio Experimental.

Comparison of Uninformed and Heuristic Search Strategies in Solving Route Optimization Problems: An Experimental Study

Autores/as

Palabras clave:

Búsqueda no Informada, Heurística, Resolución de Problemas

Resumen

En este estudio se exploran y comparan diferentes estrategias de búsqueda, tanto no informadas como heurísticas, en la resolución de problemas de optimización de rutas. Se evaluaron los algoritmos de Búsqueda en Anchura (BFS), Búsqueda en Profundidad (DFS) y el algoritmo A* con heurísticas de distancia Manhattan y Euclídea. Los experimentos se realizaron en un entorno de simulación que emula mapas (laberintos) de diferentes tamaños y complejidades. Los resultados obtenidos muestran que el algoritmo A*, con ambas heurísticas de distancia Manhattan y Euclídea, fue el óptimo en términos de costo de la solución, superando a BFS y DFS en la mayoría de los escenarios. El algoritmo BFS demostró encontrar la ruta más corta (longitud menor), independientemente del coste de la solución, pero a costa de un mayor tiempo de búsqueda y consumo de memoria. El algoritmo DFS, aunque rápido en encontrar una solución minimizando el gasto computacional, frecuentemente resultó en rutas no óptimas, independientemente del coste de los movimientos dentro del mapa, y no garantizó la optimalidad de la solución. En resumen, el algoritmo A* con heurísticas admisibles se destaca como la mejor opción para la resolución de problemas de optimización de rutas, ofreciendo un equilibrio óptimo entre eficiencia y costo de la solución.

Biografía del autor/a

Ing. Harold Ordaz Valdes, Instituto Superior Universitario Bolivariano de Tecnología, Guayaquil, Ecuador.

Ingeniero en Ciencias Informáticas (Cuba).

Manuel Eduardo Millán Rodríguez, MSc., Instituto Superior Universitario Bolivariano de Tecnología, Guayaquil, Ecuador.

Máster Universitario en Ingeniería de Software y Sistemas Informáticos (España).

Luisa María Toyo Sánchez, MSc., Instituto Superior Universitario Bolivariano de Tecnología, Guayaquil, Ecuador

Magister en Educación Mención en Innovación y Liderazgo Educativo (Ecuador).

Citas

Ghallab, M., Nau, D., & Traverso, P. (2004). Automated planning: Theory and practice. Morgan Kaufmann.

Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Science and Cybernetics, 4(2), 100-107. https://doi.org/10.1109/TSSC.1968.300136

Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search. Artificial Intelligence, 27(1), 97-109. https://doi.org/10.1016/0004-3702(85)90084-0.

Nilsson, N. J. (1980). Principles of Artificial Intelligence. Morgan Kaufmann.

Pearl, J. (1984). Heuristics: Intelligent search strategies for computer problem solving. Addison-Wesley.

Russell, S. J., & Norvig, P. (2020). Artificial intelligence: A modern approach (4th ed.). Pearson.

Portada

Descargas

Publicado

03-12-2024

Cómo citar

Ordaz Valdes, H., Castro Cañarte, M. M., Millán Rodríguez, M. E., & Toyo Sánchez, L. M. (2024). Comparación de Estrategias de Búsqueda no Informada y Heurística en la Resolución de Problemas de Optimización de Rutas: Un Estudio Experimental.: Comparison of Uninformed and Heuristic Search Strategies in Solving Route Optimization Problems: An Experimental Study. Nobilis, 1(1), 59–77. Recuperado a partir de https://nobilis.ube.edu.ec/index.php/nobilis/article/view/26

Número

Vol. 1 Núm. 1 (2024): Julio - Diciembre

Sección

Artículos

Licencia

Derechos de autor 2024 Ing. Harold Ordaz Valdes, MSc. Luisa María Toyo Sánchez, MSc. Manuel Eduardo Millán Rodríguez

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial 4.0.

Usted es libre de:

  1. Compartir — copiar y redistribuir el material en cualquier medio o formato
  2. Adaptar — remezclar, transformar y construir a partir del material
  3. La licenciante no puede revocar estas libertades en tanto usted siga los términos de la licencia

Bajo los siguientes términos:

  1. Atribución — Usted debe dar crédito de manera adecuada , brindar un enlace a la licencia, e indicar si se han realizado cambios . Puede hacerlo en cualquier forma razonable, pero no de forma tal que sugiera que usted o su uso tienen el apoyo de la licenciante.
  2. NoComercial — Usted no puede hacer uso del material con propósitos comerciales .
  3. No hay restricciones adicionales — No puede aplicar términos legales ni medidas tecnológicas que restrinjan legalmente a otras a hacer cualquier uso permitido por la licencia.