Битонический тур

Битонический тур

В вычислительной геометрии битонический обход набора точечных узлов на евклидовой плоскости представляет собой замкнутую многоугольную цепочку , в которой каждый узел является одной из вершин, так что любая вертикальная линия пересекает цепочку не более двух раз.

Оптимальные битонические туры

Оптимальный битонический тур — это битонический тур минимальной общей длины. Это стандартное упражнение в динамическом программировании — разработка алгоритма с полиномиальным временем , который строит оптимальный битонический тур. Хотя обычный метод решения таким способом требует времени $O(n^{2})$, более быстрый алгоритм со временем $O(n\log ^{2}n)$ известно.

Задачу построения оптимальных битонических туров часто приписывают Джону Л. Бентли, который опубликовал в 1990 году экспериментальное сравнение многих эвристик для задачи коммивояжера ; однако эксперименты Бентли не включают битонические туры. Первой публикацией, описывающей проблему битонического тура, по-видимому, является другая публикация 1990 года, первое издание учебника « Введение в алгоритмы» Томаса Х. Кормена , Чарльза Э. Лейзерсона и Рона Ривеста , в котором Бентли указан как создатель проблемы. .

Характеристики

Оптимальный битонический тур не имеет самопересечений, поскольку любые два пересекающихся ребра можно заменить парой непересекающихся ребер с меньшей общей длиной из-за неравенства треугольника. Следовательно, он формирует полигонализацию ввода.

По сравнению с другими турами, которые, возможно, не являются битоническими,оптимальный битонический тур — это тот, который минимизирует общую величину горизонтального движения, при этом связи разрываются на евклидово расстояние.

Для точек плоскости с различными целыми числами $x$-координаты и действительные числа $y$-координаты, лежащие в интервале длины $2{\sqrt {2}}$ или меньше, оптимальный битонический тур — это оптимальный тур коммивояжера.

Другие критерии оптимизации

Тот же алгоритм динамического программирования, который находит оптимальный битонический тур, может быть использован для решения других вариантов задачи коммивояжера, которые минимизируют лексикографические комбинации движения в фиксированном числе координатных направлений.

На 5-й Международной олимпиаде по информатике в Мендосе, Аргентина , в 1993 году одна из задач конкурса включала битонные туры: участники должны были разработать алгоритм, который принимал бы в качестве входных данных набор сайтов и набор разрешенных ребер между сайтами и строил битонический тур с использованием тех ребер, которые включали как можно больше сайтов. Как и в случае с оптимальным битоническим туром, эту проблему можно решить с помощью динамического программирования.