Алгоритм Хелда — Карпа

Алгоритм Хелда — Карпа — это метод динамического программирования для решения задачи коммивояжёра (TSP), позволяющий находить точное решение за время O(2ⁿ·n²), где n — количество городов. Алгоритм был независимо разработан американскими математиками Майклом Хелдом и Ричардом Карпом в 1962 году. Он относится к классу экспоненциальных алгоритмов, но остаётся одним из наиболее эффективных точных методов для задачи коммивояжёра при n ≤ 20–25.

История

Задача коммивояжёра (TSP) является классической NP-трудной задачей комбинаторной оптимизации. До появления алгоритма Хелда — Карпа точные методы решения TSP, такие как полный перебор всех перестановок (n! вариантов), были практически неприменимы для n > 10. В 1962 году Майкл Хелд и Ричард Карп, работавшие в IBM Research, опубликовали статью «A Dynamic Programming Approach to Sequencing Problems», в которой предложили метод, основанный на принципе оптимальности Беллмана. Идея заключалась в том, чтобы разбить задачу на подзадачи, связанные с подмножествами городов, и решать их рекурсивно, сохраняя промежуточные результаты. Это позволило сократить временную сложность с O(n!) до O(2ⁿ·n²), что стало значительным прорывом для своего времени. Впоследствии алгоритм был усовершенствован и адаптирован для различных вариантов TSP, включая асимметричную задачу (ATSP).

Описание алгоритма

Основная идея

Алгоритм Хелда — Карпа использует динамическое программирование для вычисления минимальной длины пути, который начинается в заданном начальном городе (обычно городе 0), проходит через все остальные города ровно один раз и возвращается в начальный город. Для этого вводится функция dp[S][i], где S — подмножество городов (включая начальный), а i — последний посещённый город в этом подмножестве. Значение dp[S][i] равно минимальной длине пути, который начинается в городе 0, проходит через все города из S и заканчивается в городе i.

Рекуррентное соотношение

Базовый случай: dp[{0, i}][i] = dist[0][i] для всех i ≠ 0, где dist[0][i] — расстояние от начального города до города i.

Переход: для любого подмножества S, содержащего город 0 и город i, и для любого j ∈ S, j ≠ i, выполняется: dp[S][i] = min_{j ∈ S, j ≠ i} (dp[S \ {i}][j] + dist[j][i])

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

Финальный ответ

После заполнения таблицы dp для всех подмножеств, содержащих все n городов, минимальная длина полного цикла (гамильтонова цикла) вычисляется как: min_{i ≠ 0} (dp[V][i] + dist[i][0]) где V — множество всех городов. Это соответствует возвращению в начальный город из последнего посещённого города i.

Псевдокод

``` function held_karp(dist): n = len(dist) # количество городов dp = массив размера (1 << n) × n, заполненный ∞

Базовый случай: путь из города 0 в город i

for i from 1 to n-1: dp[1 << i | 1][i] = dist[0][i]

Перебор всех подмножеств

for mask from 1 to (1 << n) - 1: if mask & 1 == 0: # подмножество должно содержать город 0 continue for i from 0 to n-1: if mask & (1 << i) == 0: # i не входит в подмножество continue if i == 0: # начальный город не может быть последним continue prev_mask = mask ^ (1 << i) for j from 0 to n-1: if prev_mask & (1 << j) == 0: continue dp[mask][i] = min(dp[mask][i], dp[prev_mask][j] + dist[j][i])

Финальный ответ

full_mask = (1 << n) - 1 ans = ∞ for i from 1 to n-1: ans = min(ans, dp[full_mask][i] + dist[i][0]) return ans ```

Вычислительная сложность

Временная сложность

Алгоритм Хелда — Карпа имеет временную сложность O(2ⁿ·n²). Это объясняется тем, что необходимо перебрать все 2ⁿ подмножеств городов (с учётом того, что начальный город всегда включён, фактически 2ⁿ⁻¹), и для каждого подмножества и каждого города i (n вариантов) выполняется цикл по j (до n вариантов). Таким образом, общее количество операций составляет примерно 2ⁿ·n². Для n = 20 это около 400 миллионов операций, что выполнимо на современных компьютерах за несколько секунд. Для n = 25 время возрастает до 10–20 миллиардов операций, что уже требует значительных вычислительных ресурсов.

Пространственная сложность

Пространственная сложность составляет O(2ⁿ·n), так как хранится таблица dp размером 2ⁿ × n. Для n = 20 это около 20 миллионов записей, что при хранении чисел с плавающей точкой (8 байт) требует 160 МБ памяти. Для n = 25 память возрастает до 2⁵⁰ × 25 ≈ 800 миллионов записей, что требует около 6,4 ГБ, что может быть проблематично для некоторых систем.

Применение

Алгоритм Хелда — Карпа применяется в тех случаях, когда требуется точное решение задачи коммивояжёра для небольшого числа городов (обычно n ≤ 20–25). Он используется в:

• Логистике и транспорте: оптимизация маршрутов доставки для небольшого числа точек.
• Производстве: планирование последовательности операций на станках (задача о порядке обработки деталей).
• Генетике: секвенирование ДНК, где задача коммивояжёра возникает при сборке фрагментов генома.
• Компьютерных играх: поиск оптимального пути для персонажа или группы объектов.
• Образовании: как классический пример динамического программирования для обучения студентов.

Ограничения и альтернативы

Ограничения

• Экспоненциальный рост времени: при n > 25 алгоритм становится непрактичным из-за огромного времени выполнения.
• Потребление памяти: таблица dp размером 2ⁿ·n может превысить доступную память для n > 30.
• Только для симметричной задачи: в оригинальной формулировке алгоритм предполагает, что расстояние от i до j равно расстоянию от j до i. Для асимметричной задачи (ATSP) требуется модификация, которая увеличивает сложность.

Альтернативы

Для больших n (n > 100) используются приближённые и эвристические методы:

• Метод ветвей и границ (Branch and Bound) — точный, но с экспоненциальной сложностью в худшем случае.
• Муравьиные алгоритмы (Ant Colony Optimization) — эвристика, основанная на поведении муравьёв.
• Генетические алгоритмы — эволюционный подход.
• Метод имитации отжига (Simulated Annealing) — вероятностный метод.
• Алгоритм Линна — Кернигана — один из лучших эвристических методов для TSP.

Интересные факты

• Алгоритм Хелда — Карпа был разработан независимо, но Майкл Хелд и Ричард Карп опубликовали совместную статью. Карп впоследствии получил премию Тьюринга в 1985 году за вклад в теорию алгоритмов.
• Алгоритм часто называют «алгоритмом Беллмана — Хелда — Карпа», так как идея динамического программирования для TSP была впервые предложена Ричардом Беллманом в 1960 году.
• Для n = 10 полный перебор требует 10! = 3 628 800 операций, а алгоритм Хелда — Карпа — около 2¹⁰·10² = 102 400 операций, что в 35 раз быстрее.
• В 2010 году алгоритм был использован для решения задачи коммивояжёра для 24 городов на суперкомпьютере за несколько минут.

Источники

• Held, M., & Karp, R. M. (1962). A Dynamic Programming Approach to Sequencing Problems. Journal of the Society for Industrial and Applied Mathematics, 10(1), 196–210.
• Bellman, R. (1960). Dynamic Programming Treatment of the Travelling Salesman Problem. Journal of the ACM, 9(1), 61–63.
• Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press. — Глава 15.3 «Dynamic Programming for the Traveling-Salesman Problem».
• Papadimitriou, C. H., & Steiglitz, K. (1998). Combinatorial Optimization: Algorithms and Complexity. Dover Publications.