Jump to content

Проблема коммивояжёра с узким местом

Задача коммивояжера «Узкое место» ( 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]

См. также

[ редактировать ]
  1. ^ Перейти обратно: а б с д и ж Кабади, Сантош Н.; Пуннен, Авраам П. (2007), «Узкое место TSP», Гутин, Грегори; Паннен, Абрахам П. (ред.), Проблема коммивояжера и ее варианты , Комбинаторная оптимизация, Springer, стр. 697–735, doi : 10.1007/0-306-48213-4_15 .
  2. ^ Гилмор, ПК; Гомори, Р.Э. (1964), «Секвенирование машины с одной переменной состояния: разрешимый случай задачи коммивояжера», Oper. Рез. , 12 (5): 655–679, номер документа : 10.1287/opre.12.5.655 , JSTOR   167772 .
  3. ^ Гарфинкель, Р.С.; Гилберт, К.К. (1978), «Проблема коммивояжера с узким местом: алгоритмы и вероятностный анализ», Journal of the ACM , 25 (3): 435–448, doi : 10.1145/322077.322086 , S2CID   12062434 .
  4. ^ Гэри, Майкл Р .; Джонсон, Дэвид С. (1979), Компьютеры и трудноразрешимые проблемы: Руководство по теории NP-полноты , WH Freeman, A2.3: ND24, с. 212 , ISBN  0-7167-1045-5 .
  5. ^ Паркер, Р. Гэри; Рардин, Рональд Л. (1984), «Эвристика гарантированной производительности для проблемы коммивояжера с узким местом», Operations Research Letters , 2 (6): 269–272, doi : 10.1016/0167-6377(84)90077-4 .
  6. ^ Перейти обратно: а б Хохбаум, Дорит С .; Шмойс, Дэвид Б. (май 1986 г.), «Единый подход к алгоритмам аппроксимации для проблем с узкими местами» , Журнал ACM , 33 (3), Нью-Йорк, Нью-Йорк, США: ACM: 533–550, doi : 10.1145/5925.5933 , S2CID   17975253 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a40f916113fa0fe29b74f715c4507767__1721103720
URL1:https://arc.ask3.ru/arc/aa/a4/67/a40f916113fa0fe29b74f715c4507767.html
Заголовок, (Title) документа по адресу, URL1:
Bottleneck traveling salesman problem - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)