Проблема коммивояжера с узким местом - Bottleneck traveling salesman problem

В Проблема коммивояжера с узким местом (узкое место TSP) проблема в дискретный или же комбинаторная оптимизация. Проблема в том, чтобы найти Гамильтонов цикл в взвешенный график что минимизирует вес самого тяжелого край цикла.[1] Впервые он был сформулирован Гилмор и Гомори (1964) с некоторыми дополнительными ограничениями и в полной общности Гарфинкель и Гилберт (1978).[1][2][3]

Сложность

Известно, что проблема NP-жесткий. В проблема решения версия этого "для заданной длины Икс есть ли в графе гамильтонов цикл грамм с краем не длиннее, чем Икс?", является НП-полный. NP-полнота немедленно следует снижение из проблемы нахождения гамильтонова цикла.[4]

Алгоритмы

Другое сокращение, от TSP узкого места до обычного TSP (цель которого состоит в минимизации суммы длин ребер), позволяет также использовать любой алгоритм для обычного TSP для решения TSP узкого места. заменяются любыми другими числами, имеющими тот же относительный порядок, тогда решение узкого места остается неизменным. Если, кроме того, каждое число в последовательности превышает сумму всех меньших чисел, то решение узкого места также будет равно обычному решению TSP. Например, такого результата можно достичь, сбросив каждый вес на пя куда п - количество вершин в графе и я - ранг исходного веса ребра в отсортированной последовательности весов. Например, после этого преобразования Алгоритм Хельда – Карпа может быть использован для своевременного решения проблемы TSP О(п22п).[1]

Как вариант, проблему можно решить, выполнив бинарный поиск или же последовательный поиск для самых маленьких Икс такой, что подграф ребер веса не более Икс имеет гамильтонов цикл. Этот метод приводит к решениям, время работы которых только на логарифмический множитель больше, чем время нахождения гамильтонова цикла.[1]

Вариации

В асимметричное узкое место TSP, есть случаи, когда вес из узла А к B отличается от веса от B до A (например, время в пути между двумя городами с пробкой в ​​одном направлении).

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

В задача коммивояжера с максимальным разбросом - это еще один вариант задачи коммивояжера, цель которого - найти гамильтонов цикл, который максимизирует минимальную длину ребра, а не минимизирует максимальную длину. Его приложения включают анализ медицинских изображений и планирование этапов металлообработки в авиастроении, чтобы избежать тепловыделения от расположенных поблизости ступенек как во времени, так и в пространстве. Его можно преобразовать в пример проблемы TSP узкого места, отрицая все длины ребер (или, чтобы сохранить положительные результаты, вычитая их все из достаточно большой константы). Однако, хотя это преобразование сохраняет оптимальное решение, оно не сохраняет качество приближений к этому решению.[1]

Алгоритм метрической аппроксимации

Если график метрическое пространство тогда есть эффективный алгоритм аппроксимации который находит гамильтонов цикл с максимальным весом ребра, не более чем в два раза превышающим оптимальный. Теорема Флейшнера, что квадрат из 2-вершинно-связный граф всегда содержит гамильтонов цикл. Подобрать пороговое значение несложно θ, наименьшее значение такое, что ребра веса θ образуют 2-связный граф. потом θ обеспечивает допустимую нижнюю границу веса TSP узкого места, поскольку TSP самого узкого места является двухсвязным графом и обязательно содержит ребро веса не менее θ. Однако квадрат подграфа ребер веса не более θ гамильтоново. Посредством неравенство треугольника для метрических пространств его гамильтонов цикл имеет ребра веса не более 2θ.[5][6]

Этот коэффициент приближения является наилучшим из возможных. В самом деле, любой невзвешенный граф можно преобразовать в метрическое пространство, установив веса его ребер равными 1 и установив расстояние между всеми несмежными парами вершин равным 2. Приближение с отношением лучше, чем 2 в этом метрическом пространстве можно было бы использовать, чтобы определить, содержит ли исходный граф гамильтонов цикл, NP-полную проблему.[6]

Без предположения, что вход является метрическим пространством, невозможно конечное отношение аппроксимации.[1]

Смотрите также

Рекомендации

  1. ^ а б c d е ж Кабади, Сантош Н .; Пуннен, Абрахам П. (2007), «Узкое место TSP», Гутин, Грегори; Пуннен, Абрахам П. (ред.), Задача коммивояжера и ее варианты, Комбинаторная оптимизация, Springer, стр. 697–735, Дои:10.1007/0-306-48213-4_15.
  2. ^ Gilmore, P.C .; Гоморы, Р.Э. (1964), «Последовательность машины с одной переменной состояния: разрешимый случай задачи коммивояжера», Опер. Res., 12 (5): 655–679, Дои:10.1287 / opre.12.5.655, JSTOR  167772.
  3. ^ Гарфинкель, Р. С .; Гилберт, К. С. (1978), "Проблема коммивояжера узкого места: алгоритмы и вероятностный анализ", Журнал ACM, 25 (3): 435–448, Дои:10.1145/322077.322086, S2CID  12062434.
  4. ^ Гарей, Майкл Р.; Джонсон, Дэвид С. (1979), Компьютеры и непреодолимость: руководство по теории NP-полноты, W.H. Фриман, A2.3: ND24, стр. 212, ISBN  0-7167-1045-5.
  5. ^ Паркер, Р. Гэри; Рардин, Рональд Л. (1984), "Эвристика гарантированной производительности для решения проблемы коммивояжера", Письма об исследованиях операций, 2 (6): 269–272, Дои:10.1016/0167-6377(84)90077-4.
  6. ^ а б Хохбаум, Дорит С.; Шмойс, Дэвид Б. (Май 1986 г.), «Единый подход к алгоритмам аппроксимации для проблем узких мест», Журнал ACM, Нью-Йорк, Нью-Йорк, США: ACM, 33 (3): 533–550, Дои:10.1145/5925.5933, S2CID  17975253.