Алгоритм Хельда – Карпа - Held–Karp algorithm

В Алгоритм Хельда – Карпа, также называемый Алгоритм Беллмана – Хелда – Карпа, это динамическое программирование алгоритм, предложенный в 1962 г. независимо Bellman^[1] и от Held и Карп^[2] решить Задача коммивояжера (TSP). TSP является продолжением Проблема гамильтоновой схемы. Проблему можно описать так: найти тур по N городам в стране (при условии, что все города, которые нужно посетить, доступны), тур должен (а) посетить каждый город только один раз, (б) вернуться в исходную точку и (в ) быть на минимальном расстоянии.^[3]В общих чертах, TSP классифицируется как симметричная задача коммивояжера (sTSP), асимметричная задача коммивояжера (aTSP) и задача коммивояжера (mTSP).^{[нужна цитата ]}

Графическая модель

sTSP: Позволять V = {v₁ ,..., v_п } быть набором городов, E = {(р, s) | р, s ∈ V} - набор ребер, а d_RS = d_sр быть мерой стоимости, связанной с ребром (р, s) ∈ E.

aTSP: Если d_RS ≠ d_SR хотя бы для одного (р, s), то sTSP становится aTSP, тогда как sTSP можно определить с помощью неориентированный граф, aTSP определяется с помощью ориентированный граф.

mTSP: В задаче с несколькими TSP есть несколько продавцов из одного города; каждый город, кроме начального, должен посетить ровно один раз ровно один продавец, а сумма продолжительности их туров должна быть минимизирована. Можно рассматривать mTSP как модификацию стандартного TSP, в котором разрешено повторное посещение начального города. MTSP обычно рассматривается как расслабленный проблема с маршрутизацией автомобиля.

Алгоритм

Описание

Ниже представлена ​​процедура динамического программирования:

Для TSP есть свойство оптимизации:

   Каждый подпуть пути минимального расстояния сам является минимальным расстоянием.

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

Рекурсивная формулировка

Пронумеруйте города 1, 2,. . . , N и предположим, что мы начинаем с города 1, а расстояние между городом я и город j является d_{я, j}. Рассмотрим подмножества S ⊆ {2, . . . , N} городов и для c ∈ S, позволять D(S, c) - минимальное расстояние, начиная с города 1, до всех городов в S и заканчивая в городе c.

Первая фаза: если S = {c}, тогда D(S, c) = d_1,c. В противном случае: D(S, c) = мин._{Икс∈S−c} (D(S − c, Икс) + d_Икс,c ).

Второй этап: минимальное расстояние для полного тура по всем городам составляетM = мин_{c∈ {2, ...,N}} (D({2, . . . , N}, c) + d_c,1 )

Тур п₁ , . . ., п_N находится на минимальном расстоянии, когда удовлетворяет M = D({2, . . . , N}, п_N ) + d_пN,1 .

пример^[4]

Матрица расстояний:

${ displaystyle C = { begin {pmatrix} 0 & 2 & 9 & 10 1 & 0 & 6 & 4 15 & 7 & 0 & 8 6 & 3 & 12 & 0 end {pmatrix}}}$

Описание функций:

• г (х, S) - начиная с 1, минимальная стоимость пути заканчивается в вершине x, проходя вершины из множества S ровно один раз
• c_ху - стоимость ребра заканчивается в x от y
• р (х, S) - предпоследняя вершина для x из набора S. Используется для построения пути TSP обратно в конце.

k = 0, нулевой набор:

Установите ∅:

       g (2, ∅) = c21 = 1 г (3, ∅) = c31 = 15 г (4, ∅) = c41 = 6

k = 1, рассмотрим наборы из 1 элемента:

Установить {2}:

       g (3, {2}) = c32 + g (2, ∅) = c32 + c21 = 7 + 1 = 8 p (3, {2}) = 2 g (4, {2}) = c42 + g (2, ∅) = c42 + c21 = 3 + 1 = 4 p (4, {2}) = 2

Установить {3}:

       g (2, {3}) = c23 + g (3, ∅) = c23 + c31 = 6 + 15 = 21 p (2, {3}) = 3 g (4, {3}) = c43 + g (3, ∅) = c43 + c31 = 12 + 15 = 27 п (4, {3}) = 3

Комплект {4}:

       g (2, {4}) = c24 + g (4, ∅) = c24 + c41 = 4 + 6 = 10 p (2, {4}) = 4 g (3, {4}) = c34 + g (4, ∅) = c34 + c41 = 8 + 6 = 14 п (3, {4}) = 4

k = 2, рассмотрим наборы из 2 элементов:

Комплект {2,3}:

         g (4, {2,3}) = min {c42 + g (2, {3}), c43 + g (3, {2})} = min {3 + 21, 12 + 8} = min {24, 20} = 20 p (4, {2,3}) = 3

Установить {2,4}:

         g (3, {2,4}) = min {c32 + g (2, {4}), c34 + g (4, {2})} = min {7 + 10, 8 + 4} = min {17, 12} = 12 p (3, {2,4}) = 4

Установите {3,4}:

          g (2, {3,4}) = min {c23 + g (3, {4}), c24 + g (4, {3})} = min {6 + 14, 4 + 27} = min {20, 31} = 20 p (2, {3,4}) = 3

Продолжительность оптимального тура:

 f = g (1, {2,3,4}) = min {c12 + g (2, {3,4}), c13 + g (3, {2,4}), c14 + g (4, {2,3})} = min {2 + 20, 9 + 12, 10 + 20} = min {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.

Псевдокод^[5]

функция алгоритм TSP (G, n) является    за k: = от 2 до n делать        C ({k}, k): = d1, к    конец для    за s: = 2 к п-1 делать        для всех S ⊆ {2,. . . , n}, | S | = s делать            для всех k ∈ S делать                C (S, k): = мин.m ≠ k, m∈S [C (S  {k}, m) + dм, к]            конец для        конец для    конец для    opt: = mink ≠ 1 [C ({2, 3,..., N}, k) + dк, 1]    вернуть (опт)конечная функция

Сложность

Исчерпывающий перечень

Этот метод перебора начинается с любого города, перечисляет все возможные перестановки городов для посещения, найдите расстояние каждой перестановки и выберите одно из минимальных расстояний. Общее количество возможных маршрутов, охватывающих все ${ displaystyle N}$ города можно представить как ${ displaystyle (N-1)!}$ и ${ displaystyle { frac {1} {2}} (N-1)!}$ в aTSP и sTSP соответственно.^[6]

Подход динамического программирования

Этот алгоритм предлагает более быстрое (но все же экспоненциальное время) выполнение, чем исчерпывающее перечисление, с недостатком, заключающимся в том, что много места: наихудшая временная сложность этого алгоритма составляет ${ Displaystyle О (2 ^ {п} п ^ {2})}$ и пространство ${ Displaystyle О (2 ^ {п} п)}$.

Время: основные операции, используемые в вычислениях, - это сложение и сравнение. Количество каждого из них на первом этапе определяется выражением${ displaystyle left ( sum _ {k = 2} ^ {n-1} k (k-1) { binom {n-1} {k}} right) + (n-1) = (n -1) (n-2) 2 ^ {n-3} + (n-1)}$

и количество появлений каждого во второй фазе равно ${ Displaystyle сумма _ {к = 2} ^ {п-1} к = {п (п-1) более 2} -1}$

Космос: ${ Displaystyle влево ( сумма _ {к = 2} ^ {п-1} к { бином {п-1} {к}} справа) + (п-1) = (п-1) 2 ^ {n-2}}$

Сложность пространства можно немного улучшить, заметив, что расчет минимальных затрат для подмножеств размера s требуется только подмножество размера с-1.

Сохраняя только подмножества размера с-1 и s в любой точке алгоритма сложность пространства уменьшается до: ${ displaystyle max _ {2 leq s$

Связанные алгоритмы

Точный алгоритм решения TSP

Помимо динамического программирования, Линейное программирование и алгоритм с границей ветвей - это точные алгоритмы, которые могут решить TSP. Линейное программирование применяется к методу секущей плоскости в целочисленное программирование, т.е. решение LP, образованного двумя ограничениями в модели, а затем поиск плоскости сечения путем добавления ограничения неравенства, чтобы постепенно сходиться к оптимальному решению. Когда люди применяют этот метод, чтобы найти рубанок, они часто полагаются на свой опыт. Таким образом, этот метод редко считается общим.

Алгоритм с границей ветвей - это широко используемый алгоритм поиска, хотя он не подходит для решения крупномасштабных задач. Он управляет процессом поиска через эффективную ограничивающую границу, так что он может искать ветвь оптимального решения из дерева состояний пространства, чтобы найти оптимальное решение как можно скорее. Ключевым моментом этого алгоритма является выбор ограничительной границы. Различные ограничительные границы могут формировать разные алгоритмы ветвления.

Примерный алгоритм решения ТСП

Поскольку применение точного алгоритма для решения проблемы очень ограничено, мы часто используем приближенный алгоритм или эвристический алгоритм. Результат алгоритма можно оценить как C / C * ≤ ε. C - полное пройденное расстояние, полученное с помощью приближенного алгоритма; C * - оптимальное расстояние перемещения; ε - верхний предел отношения общего пути приближенного решения к оптимальному решению при наихудших условиях. Значение ε> 1,0. Чем больше он приближается к 1.0, тем лучше алгоритм. Эти алгоритмы включают: алгоритм интерполяции, Алгоритм ближайшего соседа, Алгоритм Кларка и Райта, алгоритм двойного остовного дерева, Алгоритм Кристофидеса, Гибридный алгоритм, Вероятностный алгоритм.

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