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.
Tours bitónicos óptimos
El recorrido bitónico óptimo es un recorrido bitónico de longitud total mínima. Es un ejercicio estándar de 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 lleva tiempo, un algoritmo más rápido con el tiempo es conocida. [3]
El problema de construir recorridos bitónicos óptimos se atribuye 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 enumera a Bentley como el creador del problema. .
Propiedades
El recorrido bitónico óptimo no tiene auto-cruces, porque dos bordes que se cruzan pueden ser reemplazados por un par de bordes sin cruzar con una longitud total más corta debido a la desigualdad del triángulo.
En comparación con otros recorridos que pueden no ser bitónicos, el recorrido bitónico óptimo es el que minimiza la cantidad total de movimiento horizontal, con lazos rotos por la distancia euclidiana. [5]
Para puntos en el plano con entero distinto -coordenadas y con número real -coordenadas que se encuentran dentro de un intervalo de longitud o menos, el recorrido bitónico óptimo es un recorrido óptimo para los vendedores ambulantes. [6]
Otros criterios de optimización
El mismo algoritmo de programación dinámica que encuentra el recorrido bitónico óptimo puede usarse para resolver otras variantes del problema del viajante de comercio que minimizan las combinaciones lexicográficas de movimiento en un número fijo de direcciones de coordenadas. [5]
En la V Olimpiada Internacional de Informática , en Mendoza, Argentina en 1993, uno de los problemas del concurso involucró recorridos bitónicos: los concursantes debían idear un algoritmo que tomara como entrada un conjunto de sitios y una colección de bordes permitidos entre sitios y construir un recorrido bitónico utilizando esos bordes que incluían 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]
Referencias
- ^ Introducción a los algoritmos , 3ª ed., TH Cormen , CE Leiserson , R. Rivest y C. Stein , MIT Press , 2009. Problema 15-3, p. 405.
- ^ Pájaro, Richard S .; De Moor, Oege (1997), El álgebra de la programación , Prentice Hall, p. 213, ISBN 9780135072455.
- ^ de Berg, Mark; Buchin, Kevin; Jansen, diputado de Bart; Woeginger, Gerhard (2016), "Análisis de complejidad de grano fino de dos variantes clásicas de TSP" , en Chatzigiannakis, Ioannis; Mitzenmacher, Michael; Rabani, Yuval; Sangiorgi, Davide (eds.), 43 ° Coloquio Internacional sobre Autómatas, Idiomas y Programación (ICALP 2016) , Leibniz International Proceedings in Informatics (LIPIcs), 55 , Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum fuer Informatik, pp.5 : 1–5: 14, doi : 10.4230 / LIPIcs.ICALP.2016.5 , ISBN 978-3-95977-013-2
- ^ Bentley, Jon L. (1990), "Experimentos sobre la heurística del viajante de comercio", Proc. 1er ACM-SIAM Symp. Algoritmos discretos (SODA) , págs. 91–99.
- ^ a b Sourd, Francis (2010), "Minimizar lexicográficamente los movimientos axiales para el TSP euclidiano", Journal of Combinatorial Optimization , 19 (1): 1-15, doi : 10.1007 / s10878-008-9154-0 , MR 2579501.
- ^ Alkema, Henk; de Berg, Mark; Kisfaludi-Bak, Sándor (2020), "Euclidean TSP in Narrow Strips" , en Cabello, Sergio; Chen, Danny Z. (eds.), 36th International Symposium on Computational Geometry (SoCG 2020) , Leibniz International Proceedings in Informatics (LIPIcs), 164 , Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, págs. 4: 1 –4: 16, doi : 10.4230 / LIPIcs.SoCG.2020.4 , ISBN 978-3-95977-143-6
- ^ Informe y problemas del concurso IOI'93 .
- ^ Guerreiro, Pedro (diciembre de 2003), The Canadian Airline Problem and the Bitonic Tour: Is This Dynamic Programming? (PDF) , Departamento de Informática, Faculdade de Ciências e Tecnologia, Universidade Nova de Lisboa.