Una visión sobre el algoritmo de Dijkstra
“Es un gran algoritmo”, dijo Erik Demaine, un científico informático del Instituto Tecnológico de Massachusetts. “Es muy rápido, simple y fácil de implementar.” Para poner en práctica este procedimiento, se necesita decidir un sistema para organizar sus notas—una estructura de datos, en la jerga de la informática. Esto puede parecer un detalle técnico menor, pero el tiempo dedicado a buscar entre sus notas cada vez que necesita editar o eliminar una entrada puede tener un gran efecto en el tiempo total de ejecución del algoritmo.
Mejoras en la estructura de datos
El trabajo de Dijkstra utilizó una estructura de datos simple que dejó espacio para mejorar. En las décadas siguientes, los investigadores desarrollaron estructuras de datos mejores, cariñosamente denominadas “montículos”, en las que ciertos elementos son más fáciles de encontrar que otros. Aprovechan el hecho de que el algoritmo de Dijkstra solo necesita eliminar la entrada para el vértice restante más cercano. “Un montículo es básicamente una estructura de datos que te permite hacer esto muy rápidamente”, dijo Václav Rozhoň, investigador del Instituto de Informática, Inteligencia Artificial y Tecnología (INSAIT) en Sofía, Bulgaria.
El límite teórico del algoritmo
En 1984, dos científicos informáticos desarrollaron un diseño de montículo ingenioso que permitió que el algoritmo de Dijkstra alcanzara un límite teórico, o “bajo límite”, sobre el tiempo necesario para resolver el problema de los caminos más cortos desde una sola fuente. En un sentido específico, esta versión del algoritmo de Dijkstra es la mejor posible. Esa fue la última palabra sobre la versión estándar del problema durante casi 40 años. Las cosas solo cambiaron cuando algunos investigadores examinaron más de cerca lo que significa ser “el mejor.”
Comparación y optimización universal
Los investigadores suelen comparar algoritmos estudiando cómo se comportan en escenarios de peor caso. Imagina la cuadrícula de calles más confusa del mundo, y luego agrega algunos patrones de tráfico especialmente desconcertantes. Si insistes en encontrar las rutas más rápidas en estas circunstancias extremas, la versión de 1984 del algoritmo de Dijkstra es, demostrablemente, imbatible. Pero, con suerte, tu ciudad no tiene la cuadrícula de calles más mala del mundo. Y así puedes preguntar: ¿hay un algoritmo que sea imbatible en todas las redes viales? El primer paso para responder a esta pregunta es hacer la suposición conservadora de que cada red tiene patrones de tráfico de peor caso. Luego deseas que tu algoritmo encuentre los caminos más rápidos a través de cualquier posible disposición gráfica, asumiendo los pesos más desfavorables. Los investigadores llaman a esta condición “optimalidad universal.” Si tuvieras un algoritmo universalmente óptimo para el problema más simple de solo ir de un punto en un gráfico a otro, podría ayudarte a evitar el tráfico en hora pico en todas las ciudades del mundo.
Fuente y créditos: www.wired.com
Cats: Science
