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

Rafael Rodríguez-Puente, Manuel Sabino Lazo-Cortés

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.

Palabras clave


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

Texto completo:

PDF


 

 

 

 

 

 

 

 

Dirección editorial:

Facultad de Ingeniería Industrial, Universidad Tecnológica de La Habana José Antonio Echeverría, Cujae,

Calle 114 No. 11901. e/ Ciclovía y Rotonda. Marianao.

La Habana, Cuba. CP 19390. Telf: (537) 266 3521

E-mail: revistaii@ind.cujae.edu.cu

URL: http://rii.cujae.edu.cu