En geometría computacional , un recorrido bitónico de un conjunto de sitios puntuales en el plano euclidiano es una cadena poligonal cerrada que tiene cada sitio como uno de sus vértices, de modo que cualquier línea vertical cruza la cadena como máximo dos veces.
El recorrido bitónico óptimo es un recorrido bitónico de longitud total mínima. Un ejercicio estándar en programación dinámica es diseñar un algoritmo de tiempo polinomial que construya el recorrido bitónico óptimo. [1] [2] Aunque el método habitual para resolverlo de esta manera lleva tiempo , se conoce un algoritmo más rápido con el tiempo . [3]
El problema de construir recorridos bitónicos óptimos se atribuye a menudo a Jon L. Bentley, quien publicó en 1990 una comparación experimental de muchas heurísticas para el problema del viajante de comercio ; [4] sin embargo, los experimentos de Bentley no incluyen recorridos bitónicos. La primera publicación que describe el problema del recorrido bitónico parece ser una publicación diferente de 1990, la primera edición del libro de texto Introducción a los algoritmos de Thomas H. Cormen , Charles E. Leiserson y Ron Rivest , que menciona a Bentley como el creador del problema.
El recorrido bitónico óptimo no tiene autocruces, porque dos aristas cualesquiera que se crucen pueden ser reemplazadas por un par de aristas no cruzadas con una longitud total más corta debido a la desigualdad del triángulo. Por lo tanto, forma una poligonalización de la entrada.
En comparación con otros recorridos que podrían no ser bitónicos, el recorrido bitónico óptimo es el que minimiza la cantidad total de movimiento horizontal, y los empates se rompen mediante la distancia euclidiana. [5]
Para puntos en el plano con coordenadas enteras distintas y con coordenadas de números reales que se encuentran dentro de un intervalo de longitud o menos, el recorrido bitónico óptimo es un recorrido de vendedor viajero óptimo. [6]
El mismo algoritmo de programación dinámica que encuentra el recorrido bitónico óptimo se puede utilizar para resolver otras variantes del problema del viajante que minimizan las combinaciones lexicográficas de movimiento en un número fijo de direcciones de coordenadas. [5]
En la V Olimpíada Internacional de Informática , en Mendoza, Argentina , en 1993, uno de los problemas del concurso involucraba recorridos bitónicos: los concursantes debían idear un algoritmo que tomara como entrada un conjunto de sitios y una colección de aristas permitidas entre sitios y construir un recorrido bitónico usando esas aristas que incluyera tantos sitios como fuera posible. Al igual que con el recorrido bitónico óptimo, este problema puede resolverse mediante programación dinámica. [7] [8]
