Проблема коммивояжёра с узким местом
Задача коммивояжера «Узкое место» ( THP «узкое место» ) — это задача дискретной или комбинаторной оптимизации . Задача состоит в том, чтобы найти гамильтонов цикл (посещающий каждый узел ровно один раз) во взвешенном графе , который минимизирует вес ребра цикла с наибольшим весом. [1] Впервые он был сформулирован Гилмором и Гомори (1964) с некоторыми дополнительными ограничениями, а в полной общности — Гарфинкелем и Гилбертом (1978) . [1] [2] [3]
Сложность
[ редактировать ]Известно, что задача NP-сложная . Версия проблемы решения : «Существует ли для заданной длины x гамильтонов цикл в графе G с ребром длиннее x ?» является NP-полной . NP-полнота непосредственно следует из редукции к задаче нахождения гамильтонова цикла. [4]
Алгоритмы
[ редактировать ]Другое сокращение от TSP с узким местом до обычного TSP (цель которого состоит в минимизации суммы длин ребер) позволяет использовать любой алгоритм для обычного TSP для решения TSP с узким местом.Если веса ребер узкого места TSP заменить любыми другими числами того же относительного порядка, то решение узкого места останется неизменным.Если, кроме того, каждое число в последовательности превышает сумму всех меньших чисел, то решение узкого места также будет равно обычному решению TSP.Например, такого результата можно достичь, сбросив каждый вес на n я где n — количество вершин в графе, а i — ранг исходного веса ребра в отсортированной последовательности весов. Например, после этого преобразования алгоритм Хелда – Карпа можно использовать для решения узкого места TSP за время O ( n 2 2 н ) . [1]
В качестве альтернативы проблему можно решить, выполнив бинарный поиск или последовательный поиск наименьшего x, такого, что подграф ребер веса не более x имеет гамильтонов цикл. Этот метод приводит к решениям, время выполнения которых всего лишь в логарифмическом множителе превышает время нахождения гамильтонова цикла. [1]
Вариации
[ редактировать ]В асимметричном узком месте TSP бывают случаи, когда вес от узла A до B отличается от веса от B до A (например, время в пути между двумя городами с пробкой в одном направлении).
Евклидово узкое место TSP или планарное узкое место TSP — это узкое место TSP, расстояние которого равно обычному евклидову расстоянию . Проблема по-прежнему остается NP-трудной. Однако многие эвристики для него работают лучше, чем для других функций расстояния.
— Задача коммивояжера с максимальным разбросом это еще один вариант задачи коммивояжера, цель которого — найти гамильтонов цикл, который максимизирует минимальную длину ребра, а не минимизирует максимальную длину. Его приложения включают анализ медицинских изображений и планирование этапов металлообработки при производстве самолетов, чтобы избежать перегрева на этапах, находящихся поблизости как во времени, так и в пространстве. Это можно преобразовать в пример проблемы TSP с узким местом, отрицая все длины ребер (или, чтобы результаты были положительными, вычитая их все из достаточно большой константы). Однако, хотя это преобразование сохраняет оптимальное решение, оно не сохраняет качество приближений к этому решению. [1]
Алгоритм метрической аппроксимации
[ редактировать ]Если граф представляет собой метрическое пространство , то существует эффективный алгоритм аппроксимации , который находит гамильтонов цикл с максимальным весом ребра, не более чем в два раза превышающим оптимальный.Этот результат следует из теоремы Флейшнера о том, что квадрат всегда 2-вершинно-связного графа содержит гамильтонов цикл. Легко найти пороговое значение θ — наименьшее значение, при котором ребра веса θ образуют 2-связный граф. Тогда θ обеспечивает действительную нижнюю границу веса TSP узкого места, поскольку TSP узкого места сам по себе является 2-связным графом и обязательно содержит ребро с весом не менее θ . Однако квадрат подграфа ребер веса не выше θ является гамильтоновым. По неравенству треугольника для метрических пространств его гамильтонов цикл имеет ребра веса не более 2 θ . [5] [6]
Это соотношение аппроксимации является наилучшим из возможных. Ведь любой невзвешенный граф можно преобразовать в метрическое пространство, установив веса его ребер равными 1 и установив расстояние между всеми несмежными парами вершин равным 2 . Аппроксимация с отношением лучше 2 в этом метрическом пространстве может быть использована для определения того, содержит ли исходный граф гамильтонов цикл, что является NP-полной задачей. [6]
Без предположения, что входные данные являются метрическим пространством, конечный коэффициент аппроксимации невозможен. [1]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б с д и ж Кабади, Сантош Н.; Пуннен, Авраам П. (2007), «Узкое место TSP», Гутин, Грегори; Паннен, Абрахам П. (ред.), Проблема коммивояжера и ее варианты , Комбинаторная оптимизация, Springer, стр. 697–735, doi : 10.1007/0-306-48213-4_15 .
- ^ Гилмор, ПК; Гомори, Р.Э. (1964), «Секвенирование машины с одной переменной состояния: разрешимый случай задачи коммивояжера», Oper. Рез. , 12 (5): 655–679, номер документа : 10.1287/opre.12.5.655 , JSTOR 167772 .
- ^ Гарфинкель, Р.С.; Гилберт, К.К. (1978), «Проблема коммивояжера с узким местом: алгоритмы и вероятностный анализ», Journal of the ACM , 25 (3): 435–448, doi : 10.1145/322077.322086 , S2CID 12062434 .
- ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, A2.3: ND24, с. 212 , ISBN 0-7167-1045-5 .
- ^ Паркер, Р. Гэри; Рардин, Рональд Л. (1984), «Эвристика гарантированной производительности для проблемы коммивояжера с узким местом», Operations Research Letters , 2 (6): 269–272, doi : 10.1016/0167-6377(84)90077-4 .
- ^ Jump up to: а б Хохбаум, Дорит С .; Шмойс, Дэвид Б. (май 1986 г.), «Единый подход к алгоритмам аппроксимации для проблем с узкими местами» , Журнал ACM , 33 (3), Нью-Йорк, Нью-Йорк, США: ACM: 533–550, doi : 10.1145/5925.5933 , S2CID 17975253 .