Búsquedas de caminos mínimos haciendo uso de grafos reducidos

Autores/as

  • Rafael Rodríguez-Puente Universidad de las Ciencias Informáticas
  • Manuel Sabino Lazo-Cortés Universidad de las Ciencias Informáticas

Palabras clave:

Algoritmo de Dijkstra, búsqueda de camino mínimo, reducción de grafos

Resumen

Uno de los problemas de optimización ampliamente estudiados consiste en la búsqueda de caminos mínimos desde un origen a un destino. Los algoritmos clásicos que solucionan este problema no son escalables. Se han publicado varias propuestas utilizando heurísticas que disminuyen el tiempo de respuesta; pero las mismas introducen un error en el resultado. El presente trabajo propone el uso de un algoritmo de reducción de grafos sin pérdida de información, el cual contribuye a reducir el tiempo de respuesta en la búsqueda de caminos. Además, se propone una modificación al algoritmo de Dijkstra para ser utilizado sobre grafos reducidos, garantizando la obtención del óptimo en todos los casos. También se realiza una comparación entre el tiempo de ejecución de la propuesta y los algoritmos de Dijkstra y A*, la cual muestra que es posible obtener un camino óptimo en tiempos similares, e incluso inferiores, a los obtenidos por algoritmos heurísticos.

Descargas

Publicado

2016-11-11

Cómo citar

Rodríguez-Puente, R., & Lazo-Cortés, M. S. (2016). Búsquedas de caminos mínimos haciendo uso de grafos reducidos. Ingeniería Industrial, 38(1), 32–42. Recuperado a partir de https://rii.cujae.edu.cu/index.php/revistaind/article/view/497

Número

Sección

Investigación de Operaciones y Estadística