Tour bitónico

En geometría computacional , un recorrido bitónico de un conjunto de puntos en el plano euclidiano es una cadena poligonal cerrada que tiene a cada punto como uno de sus vértices, de tal manera 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. Es un ejercicio estándar en programación dinámica 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 requiere tiempo${\displaystyle O(n^{2})}$, un algoritmo más rápido con el tiempo${\displaystyle O(n\log ^{2}n)}$es conocido. ^{[ 3 ]}

El problema de construir recorridos bitónicos óptimos se suele atribuir a Jon L. Bentley, quien publicó en 1990 una comparación experimental de varias heurísticas para el problema del viajante ; ^{[ 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 otra publicación de 1990, la primera edición del libro de texto Introduction to Algorithms 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, ya que cualquier par de aristas que se cruzan puede reemplazarse por un par de aristas no cruzadas con una longitud total menor debido a la desigualdad triangular. Por lo tanto, constituye 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 aquel que minimiza la cantidad total de movimiento horizontal, y los empates se resuelven mediante la distancia euclidiana. ^{[ 5 ]}

Para puntos en el plano con entero distinto${\displaystyle x}$-coordenadas y con número real${\displaystyle y}$-coordenadas que se encuentran dentro de un intervalo de longitud${\displaystyle 2{\sqrt {2}}}$o menos, el recorrido bitónico óptimo es un recorrido óptimo de vendedor ambulante. ^{[ 6 ]}

El mismo algoritmo de programación dinámica que encuentra el recorrido bitónico óptimo puede utilizarse para resolver otras variantes del problema del viajante que minimizan combinaciones lexicográficas de movimiento en un número fijo de direcciones de coordenadas. ^{[ 5 ]}

En la V Olimpiada Internacional de Informática , celebrada en Mendoza, Argentina, en 1993, uno de los problemas del concurso consistía en recorridos bitónicos: los participantes debían diseñar un algoritmo que, a partir de un conjunto de sitios y una colección de aristas permitidas entre ellos, construyera un recorrido bitónico utilizando dichas aristas, incluyendo la mayor cantidad de sitios posible. Al igual que con el recorrido bitónico óptimo, este problema puede resolverse mediante programación dinámica. ^{[ 7 ] [ 8 ]}