Held-Карп алгоритм , называемый также Беллмана-Held-Карп алгоритм , является динамическое программирование алгоритм , предложенный в 1962 году независимо друг от друга Беллмана [1] и Held и Карп [2] , чтобы решить эту проблему коммивояжера (TSP), в котором input - это матрица расстояний между набором городов, и цель состоит в том, чтобы найти тур минимальной продолжительности, который посещает каждый город ровно один раз, прежде чем вернуться в начальную точку. Он находит точное решение этой проблемы и нескольких связанных проблем, включая проблему гамильтоновой схемы , за экспоненциальное время .
Алгоритм
Описание
Ниже представлена процедура динамического программирования:
Для TSP есть свойство оптимизации:
Каждый подпуть пути минимального расстояния сам является минимальным расстоянием.
Вычислите решения всех подзадач, начиная с наименьшей. Всякий раз, когда для вычисления решения требуются решения для более мелких проблем с использованием приведенных выше рекурсивных уравнений, найдите эти решения, которые уже вычислены. Чтобы вычислить маршрут с минимальным расстоянием, используйте окончательное уравнение для создания 1-го узла и повторите для других узлов. Для этой проблемы мы не можем знать, какие подзадачи нам нужно решить, поэтому мы решаем их все.
Рекурсивная формулировка
Пронумеруйте города 1, 2,. . . , N, и предположим, что мы начинаем с города 1, а расстояние между городом i и городом j равно d i, j . Рассмотрим подмножества S ⊆ {2,. . . , N } городов и, для c ∈ S , пусть D ( S , c ) будет минимальным расстоянием, начиная с города 1, посещая все города в S и заканчивая в городе c .
Первая фаза: если S = { c }, то D ( S , c ) = d 1, c . В противном случае: D ( S , c ) = min x ∈ S - c ( D ( S - c , x ) + d x , c ).
Второй этап: минимальное расстояние для полного тура по всем городам составляет M = min c∈ {2, ..., N } ( D ({2, ..., N }, c ) + d c , 1 )
Экскурсия п 1 ,. . ., n N имеет минимальное расстояние как раз тогда, когда оно удовлетворяет M = D ({2,..., N }, n N ) + d n N , 1 .
Пример [3]
Матрица расстояний:
Описание функций:
- g (x, S) - начиная с 1, минимальная стоимость пути заканчивается в вершине x, проходя вершины в множестве S ровно один раз
- c xy - стоимость ребра заканчивается в x от y
- p (x, S) - предпоследняя вершина до x из множества S. Используется для построения пути TSP обратно в конце.
k = 0, нулевой набор:
Установите ∅:
g (2, ∅) = c 21 = 1 г (3, ∅) = с 31 = 15 г (4, ∅) = с 41 = 6
k = 1, рассмотрим наборы из 1 элемента:
Установить {2}:
g (3, {2}) = c 32 + g (2, ∅) = c 32 + c 21 = 7 + 1 = 8 p (3, {2}) = 2 g (4, {2}) = c 42 + g (2, ∅) = c 42 + c 21 = 3 + 1 = 4 p (4, {2}) = 2
Установить {3}:
g (2, {3}) = c 23 + g (3, ∅) = c 23 + c 31 = 6 + 15 = 21 p (2, {3}) = 3 g (4, {3}) = c 43 + g (3, ∅) = c 43 + c 31 = 12 + 15 = 27 p (4, {3}) = 3
Комплект {4}:
g (2, {4}) = c 24 + g (4, ∅) = c 24 + c 41 = 4 + 6 = 10 p (2, {4}) = 4 g (3, {4}) = c 34 + g (4, ∅) = c 34 + c 41 = 8 + 6 = 14 p (3, {4}) = 4
k = 2, рассмотрим наборы из 2 элементов:
Комплект {2,3}:
g (4, {2,3}) = min {c 42 + g (2, {3}), c 43 + g (3, {2})} = min {3 + 21, 12 + 8} = min {24, 20} = 20 p (4, {2,3}) = 3
Установить {2,4}:
g (3, {2,4}) = min {c 32 + g (2, {4}), c 34 + g (4, {2})} = min {7 + 10, 8 + 4} = min {17, 12} = 12 p (3, {2,4}) = 4
Установите {3,4}:
g (2, {3,4}) = min {c 23 + g (3, {4}), c 24 + g (4, {3})} = min {6 + 14, 4 + 27} = min {20, 31} = 20 p (2, {3,4}) = 3
Продолжительность оптимального тура:
f = g (1, {2,3,4}) = min {c 12 + g (2, {3,4}), c 13 + g (3, {2,4}), c 14 + g ( 4, {2,3})} = мин. {2 + 20, 9 + 12, 10 + 20} = мин. {22, 21, 30} = 21
Предшественник узла 1: p (1, {2,3,4}) = 3
Предшественник узла 3: p (3, {2,4}) = 4
Предшественник узла 4: p (4, {2}) = 2
Предшественник узла 2: p (2, {}) = 1
Следовательно, оптимальный тур TSP задается как 1 → 2 → 4 → 3 → 1.
Псевдокод [4]
Функциональный алгоритм TSP (G, n) предназначен для k: = от 2 до n do C ({k}, k): = d 1, k end для для s: = от 2 до n − 1 сделать для всех S ⊆ {2,. . . , n}, | S | = s do для всех k ∈ S do C (S, k): = min m ≠ k, m∈S [C (S \ {k}, m) + d m, k ] конец за конец за конец для opt: = min k ≠ 1 [C ({2, 3,..., n}, k) + d k, 1 ] return (opt) конечная функция
Сложность
Исчерпывающий перечень
Этот метод грубой силы, начиная с любого города, перечисляет все возможные перестановки городов для посещения, находит расстояние каждой перестановки и выбирает одно из минимальных расстояний. Общее количество возможных маршрутов, охватывающих все города можно представить как а также в aTSP и sTSP соответственно. [5]
Подход динамического программирования
Этот алгоритм предлагает более быстрое (но все же экспоненциальное время) выполнение, чем исчерпывающее перечисление, с недостатком, заключающимся в том, что много места: наихудшая временная сложность этого алгоритма составляет и пространство .
Время: основные операции, используемые в вычислениях, - это сложение и сравнение. Количество каждого из них на первом этапе определяется выражением
и количество появлений каждого из них во второй фазе равно
Космос:
Сложность пространства можно немного улучшить, заметив, что для вычисления минимальных затрат для подмножеств размера s требуются только подмножества размера s-1 .
Сохраняя только подмножества размера s-1 и s в любой точке алгоритма, сложность пространства уменьшается до:
Связанные алгоритмы
Точный алгоритм решения TSP
Помимо динамического программирования, линейное программирование и алгоритм ветвления - это точные алгоритмы, которые могут решить TSP. Линейное программирование применяется к методу секущей плоскости в целочисленном программировании , т. Е. Решает LP, образованную двумя ограничениями в модели, и затем ищет секущую плоскость путем добавления ограничения неравенства, чтобы постепенно сходиться к оптимальному решению. Когда люди применяют этот метод, чтобы найти рубанок, они часто полагаются на свой опыт. Таким образом, этот метод редко считается общим.
Алгоритм с границей ветвей - это широко используемый алгоритм поиска, хотя он не подходит для решения крупномасштабных задач. Он управляет процессом поиска через эффективную ограничивающую границу, так что он может искать ветвь оптимального решения из дерева состояний пространства, чтобы найти оптимальное решение как можно скорее. Ключевым моментом этого алгоритма является выбор ограничительной границы. Различные ограничительные границы могут формировать разные алгоритмы ветвления.
Примерный алгоритм решения ТСП
Поскольку применение точного алгоритма для решения проблемы очень ограничено, мы часто используем приближенный алгоритм или эвристический алгоритм. Результат алгоритма можно оценить как C / C * ≤ ε. C - полное пройденное расстояние, полученное с помощью приближенного алгоритма; C * - оптимальное расстояние перемещения; ε - это верхний предел отношения общего пути приближенного решения к оптимальному решению при наихудших условиях. Значение ε> 1,0. Чем больше он приближается к 1.0, тем лучше алгоритм. Эти алгоритмы включают в себя: алгоритм интерполяции, алгоритм ближайшего соседа, алгоритм Кларка и Райта, алгоритм двойного связующего дерева, алгоритм Кристофидеса , гибридный алгоритм, вероятностный алгоритм.
Рекомендации
- ^ «Динамическое программирование решения задачи коммивояжера», Ричард Беллман, Journal of Assoc. Вычислительная Мах. 9. 1962 год.
- ^ «Подход динамического программирования к проблемам последовательности», Майкл Хелд и Ричард М. Карп, Журнал Общества промышленной и прикладной математики 1:10. 1962 г.
- ^ http://www.mafy.lut.fi/study/DiscreteOpt/tspdp.pdf
- ^ http://www.lsi.upc.edu/~mjserna/docencia/algofib/P07/dynprog.pdf [ постоянная мертвая ссылка ]
- ^ Гутин, Григорий, и Авраам П. Punnen, ред. Задача коммивояжера и ее варианты. Vol. 12. Springer, 2002.