Рубрики

Задача коммивояжера | Набор 2 (Приблизительно используя MST)

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

Треугольное неравенство: наименее удаленный путь для достижения вершины j из i всегда должен достигать j непосредственно из i, а не через какую-либо другую вершину k (или вершины), т. Е. Dis (i, j) всегда меньше или равно dis (i, k) + dist (k, j). Треугольное неравенство имеет место во многих практических ситуациях.
Когда функция стоимости удовлетворяет неравенству треугольника, мы можем разработать приблизительный алгоритм для TSP, который возвращает тур, стоимость которого никогда не превышает стоимость оптимального тура более чем в два раза. Идея состоит в том, чтобы использовать M inimum S paning T ree (MST). Ниже приведен алгоритм на основе MST.

Алгоритм:
1) Пусть 1 будет начальной и конечной точкой для продавца.
2) Построить MST из 1 в качестве корня, используя алгоритм Прима .
3) Перечислите вершины, посещенные в ходе предварительного заказа построенного MST, и добавьте 1 в конце.

Давайте рассмотрим следующий пример. Первая диаграмма — это заданный граф. Вторая диаграмма показывает MST, построенный с 1 как корень. Обход предзаказа MST 1-2-4-3. Добавление 1 в конце дает 1-2-4-3-1, который является выходом этого алгоритма.

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

Как этот алгоритм 2-приближенный? Стоимость вывода, полученного с помощью вышеуказанного алгоритма, никогда не более чем вдвое превышает стоимость наилучшего возможного выхода. Давайте посмотрим, как это гарантируется приведенным выше алгоритмом.
Давайте определим термин « полная прогулка», чтобы понять это. Полный обход — перечисление всех вершин, когда они впервые посещаются в предзаказе, а также перечисление вершин, когда они возвращаются после посещения поддерева в предзаказе. Полная прогулка над деревом будет 1-2-1-4-1-3-1.
Ниже приведены некоторые важные факты, которые доказывают 2-приближенность.
1) Стоимость самого лучшего тура Traveling Salesman никогда не бывает меньше стоимости MST. (Определение MST гласит, что это дерево минимальной стоимости, которое соединяет все вершины).
2) Общая стоимость полной прогулки не более чем вдвое превышает стоимость MST (каждый край MST посещается максимум дважды)
3) Вывод вышеупомянутого алгоритма меньше стоимости полного обхода. В приведенном выше алгоритме мы печатаем предварительный заказ ходьбы в качестве вывода. В режиме предварительного заказа два или более ребер полного обхода заменяются одним ребром. Например, 2-1 и 1-4 заменены на 1 ребро 2-4. Так что если график следует неравенству треугольника, то это всегда верно.

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

Мы обсудили очень простой 2-приближенный алгоритм для задачи коммивояжера. Есть и другие, более приближенные алгоритмы решения задачи. Например, алгоритм Christofides представляет собой 1,5 приближенный алгоритм. Мы скоро будем обсуждать эти алгоритмы как отдельные посты.

Ссылки:
Введение в алгоритмы 3-е издание Клиффорд Стейн, Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест
http://www.personal.kent.edu/~rmuhamma/Algorithms/MyAlgorithms/AproxAlgor/TSP/tsp.htm

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Задача коммивояжера | Набор 2 (Приблизительно используя MST)

0.00 (0%) 0 votes