Битонический тур - Bitonic tour
В вычислительной геометрии , A bitonic тур из множества точечных участков в евклидовой плоскости является замкнутым ломаным , который имеет каждый сайт в качестве одного из его вершин, такие , что любая вертикальная линия пересекает цепь не более чем в два раз.
Оптимальные битонические туры
Оптимальный bitonic тур является bitonic тур по минимальной общей длине. Разработка алгоритма с полиномиальным временем , который строит оптимальный битонический тур, является стандартным упражнением в динамическом программировании . Хотя обычный метод решения этой проблемы требует времени , известен более быстрый алгоритм со временем .
Проблема построения оптимальных битонических маршрутов часто приписывается Джону Л. Бентли, который в 1990 году опубликовал экспериментальное сравнение многих эвристик для задачи коммивояжера ; однако эксперименты Бентли не включают битонические туры. Первая публикация, описывающая bitonic появляется проблемных тур будет другой 1990 издание, первое издание учебника Введение в алгоритмы по Кормен , Лейзерсон и Рон Ривестом , в котором перечислены Bentley как создатель проблемы .
Свойства
Оптимальный битонный тур не имеет самопересечений, потому что любые два пересекающихся ребра могут быть заменены непересекающейся парой ребер с меньшей общей длиной из-за неравенства треугольника.
По сравнению с другими турами, которые могут быть не битоническими, оптимальный битонический тур - это тот, который минимизирует общее количество горизонтальных перемещений, со связями, нарушенными евклидовым расстоянием.
Для точек на плоскости с различными целочисленными координатами и с координатами с действительными числами, которые лежат в интервале длины или меньше, оптимальный битонический тур является оптимальным туром для коммивояжера.
Другие критерии оптимизации
Тот же самый алгоритм динамического программирования, который находит оптимальный битонический тур, может использоваться для решения других вариантов задачи коммивояжера, которые минимизируют лексикографические комбинации движения в фиксированном количестве координатных направлений.
На 5-й Международной олимпиаде по информатике в Мендосе, Аргентина, в 1993 году, одна из задач конкурса включала битонические туры: участники должны были разработать алгоритм, который принимал в качестве входных данных набор сайтов и набор разрешенных границ между сайтами и строил битонический тур с использованием тех ребер, которые включают как можно больше сайтов. Как и в случае с оптимальным битоническим туром, эту проблему можно решить с помощью динамического программирования.