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

Алгоритм Хелда-Карпа , также называемый алгоритмом Беллмана-Хелда-Карпа , представляет собой алгоритм динамического программирования, предложенный в 1962 году независимо Беллманом. ^[1] и Хелд и Карп ^[2] решить задачу коммивояжера (TSP), в которой входными данными является матрица расстояний между набором городов, а цель — найти тур минимальной длины, который посещает каждый город ровно один раз, прежде чем вернуться в исходную точку. Он находит точное решение этой проблемы и нескольких связанных с ней проблем, включая проблему гамильтонова цикла , за экспоненциальное время .

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

Пронумеровать города $1,2,\ldots ,n$ , с $1$ обозначен произвольно как «стартовый» город (поскольку решением TSP является гамильтонов цикл, выбор стартового города не имеет значения). Алгоритм Хелда – Карпа начинается с расчета для каждого набора городов $S\subseteq \{2,\ldots ,n\}$ и каждый город $e\neq 1$ не содержится в $S$ , кратчайший путь в одну сторону из $1$ к $e$ который проходит через каждый город в $S$ в каком-то порядке (но не через другие города). Обозначим это расстояние $g(S,e)$ , и напиши $d(u,v)$ на длину прямого края от $u$ к $v$ . Мы рассчитаем значения $g(S,e)$ начиная с самых маленьких наборов $S$ и заканчивая самым большим.

Когда $S$ имеет два или меньше элементов, затем вычисляется $g(S,e)$ требует рассмотрения одного или двух возможных кратчайших путей. Например, $g(\emptyset ,e)$ это просто $d(1,e)$ , и $g(\{2\},3)$ это всего лишь длина $1\rightarrow 2\rightarrow 3$ . Так же, $g(\{2,3\},4)$ длина любого из $1\rightarrow 2\rightarrow 3\rightarrow 4$ или $1\rightarrow 3\rightarrow 2\rightarrow 4$ , в зависимости от того, что короче.

Один раз $S$ содержит три и более городов, количество путей через $S$ быстро поднимается, но нужно просмотреть лишь несколько таких путей, чтобы найти кратчайший. Например, если $1\rightarrow 2\rightarrow 3\rightarrow 4$ короче, чем $1\rightarrow 3\rightarrow 2\rightarrow 4$ , затем $1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5$ должно быть короче, чем $1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5$ , и длина $1\rightarrow 3\rightarrow 2\rightarrow 4\rightarrow 5$ не является возможным значением $g(\{2,3,4\},5)$ . Аналогично, если кратчайший путь из $1$ через $\{2,3,4\}$ к $5$ является $1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5$ , и кратчайший путь из $1$ через $\{2,3,4,5\}$ к $6$ заканчивается краем $5\rightarrow 6$ , то весь путь от $1$ к $6$ должно быть $1\rightarrow 4\rightarrow 3\rightarrow 2\rightarrow 5\rightarrow 6$ , а не любой из пяти других путей, созданных при посещении $\{2,3,4\}$ в другом порядке.

В более общем плане, предположим $S=\{s_{1},\ldots ,s_{k}\}$ представляет собой набор $k$ города. Для каждого целого числа $1\leq i\leq k$ , писать $S_{i}=S\setminus \{s_{i}\}=\{s_{1},\ldots ,s_{i-1},s_{i+1},\ldots ,s_{k}\}$ для набора, созданного путем удаления $s_{i}$ от $S$ . Тогда если кратчайший путь из $1$ через $S$ к $e$ имеет $s_{i}$ как предпоследний город, то удаление последнего ребра этого пути должно дать кратчайший путь из $1$ к $s_{i}$ через $S_{i}$ . Это означает, что существуют только $k$ возможные кратчайшие пути из $1$ к $e$ через $S$ , по одному на каждый предпоследний город $s_{i}$ с длиной $g(S_{i},s_{i})+d(s_{i},e)$ , и $g(S,e)=\min _{1\leq i\leq k}g(S_{i},s_{i})+d(s_{i},e)$ .

Этот этап алгоритма завершается, когда $g(\{2,\ldots ,i-1,i+1,\ldots ,n\},i)$ известно для каждого целого числа $2\leq i\leq n$ , что дает кратчайшее расстояние от города $1$ в город $i$ который проходит через любой другой город. Гораздо более короткая вторая ступень добавляет эти расстояния к длине кромки. $d(i,1)$ дать $n-1$ возможные кратчайшие циклы, а затем находит самый короткий.

Сам кратчайший путь (а не только его длину), наконец, можно восстановить, сохранив рядом $g(S,e)$ метка предпоследнего города на пути из $1$ к $e$ через $S$ , что увеличивает требования к пространству лишь на постоянный коэффициент.

Алгоритмическая сложность

Алгоритм Хелда – Карпа имеет экспоненциальную временную сложность. $\Theta (2^{n}n^{2})$ , значительно лучше, чем суперэкспоненциальная производительность $\Theta (n!)$ алгоритма грубой силы. Хелд-Карп, однако, требует $\Theta (n2^{n})$ пространство для хранения всех вычисленных значений функции $g(S,e)$ , а грубая сила нужна только $\Theta (n^{2})$ место для хранения самого графика.

Время

Вычисление одного значения $g(S,e)$ для $k$ -подмножество элементов $S$ из $\{2,\ldots ,n\}$ требуется найти кратчайший из $k$ возможные пути, каждый из которых находится путем добавления известного значения $g$ и длина ребра исходного графа; то есть требуется время, пропорциональное $k$ . Есть ${\textstyle {\binom {n-1}{k}}}$ $k$ -элементные подмножества $\{2,\ldots ,n\}$ ; и каждое подмножество дает $n-k-1$ возможные значения $e$ . Вычисление всех значений $g(S,e)$ где $|S|=k$ поэтому требуется время ${\textstyle k(n-k-1){\binom {n-1}{k}}=(n-1)(n-2){\binom {n-3}{k-1}}}$ , за общее время для всех размеров подмножества ${\textstyle (n-1)(n-2)\sum _{k=1}^{n-2}{\binom {n-3}{k-1}}=(n-1)(n-2)2^{n-3}=\Theta (n^{2}2^{n})}$ . Второй этап алгоритма, нахождение полного цикла из $n-1$ кандидатов, занимает $\Theta (n)$ время и не влияет на асимптотические характеристики.

Для неориентированных графов алгоритм можно остановить раньше после ${\textstyle k=\lfloor {\frac {n-1}{2}}\rfloor }$ шаг и найти минимум ${\textstyle g(S,e)+g(S^{c}\setminus \{1,e\},e)}$ для каждого ${\textstyle \{(S,e):|S|=\lfloor {\frac {n-1}{2}}\rfloor ,e\in S^{c}\setminus \{1\}\}}$ , где ${\textstyle S^{c}}$ представляет собой дополнительный набор ${\textstyle S}$ . Это аналогично двунаправленному поиску, начинающемуся с ${\textstyle 1}$ и встреча в середине ${\textstyle e}$ . Однако это постоянное улучшение, не влияющее на асимптотические характеристики.

Космос

Сохранение всех значений $g(S,e)$ для подмножеств размера $k$ требует хранения ${\textstyle (n-k-1){\binom {n-1}{k}}=(n-1){\binom {n-2}{k}}}$ ценности. Полная таблица значений $g(S,e)$ поэтому требует места ${\textstyle \sum _{k=0}^{n-2}(n-1){\binom {n-2}{k}}=(n-1)2^{n}=\Theta (n2^{n})}$ . Это предполагает, что ${\textstyle n}$ достаточно мал, так что ${\textstyle S}$ может храниться как битовая маска , кратная машинным словам , а не как явный кортеж из k.

Если нужна только длина кратчайшего цикла, а не сам цикл, то пространственную сложность можно несколько улучшить, заметив, что вычисление $g(S,e)$ для $S$ размера $k$ требуются только значения $g$ для подмножеств размера $k-1$ . Сохраняя только ${\textstyle (n-1)\left[{\binom {n-2}{k-1}}+{\binom {n-2}{k}}\right]}$ значения $g(S,e)$ где $S$ тоже имеет размер $k-1$ или $k$ уменьшает максимальные требования алгоритма к пространству, достигаемые при ${\textstyle k=\left\lfloor {\frac {n}{2}}\right\rfloor }$ , к $\Theta ({\sqrt {n}}2^{n})$ .

Псевдокод

Источник: ^[3]

function algorithm TSP (G, n) is
    for k := 2 to n do
        g({k}, k) := d(1, k)
    end for

    for s := 2 to n−1 do
        for all S ⊆ {2, ..., n}, |S| = s do
            for all k ∈ S do
                g(S, k) := min_m≠k,m∈S [g(S\{k}, m) + d(m, k)]
            end for
        end for
    end for

    opt := min_k≠1 [g({2, 3, ..., n}, k) + d(k, 1)]
    return (opt)
end function

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

Точные алгоритмы решения ЗК.

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

Термин «ветвь и граница» впервые был использован в 1963 году в статье, опубликованной Little et al. о TSP, описывающем метод объединения меньших пространств поиска и установления нижних границ для расширения практического диапазона применения точного решения. Этот метод полезен для увеличения количества городов, которые можно учитывать с помощью вычислений, но все же не работает в крупномасштабных наборах данных.

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

Приближенные алгоритмы решения ЗК

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

Ссылки

^ «Динамическое программирование задачи коммивояжера», Ричард Беллман, Journal of Assoc. Вычисление Маха. 9. 1962.
^ «Подход динамического программирования к задачам последовательности», Майкл Хелд и Ричард М. Карп, Журнал Общества промышленной и прикладной математики 1:10. 1962 год
^ «Динамическое программирование» (PDF) . Январь 2020 г. Архивировано из оригинала (PDF) 8 февраля 2015 г.

[1] «Динамическое программирование задачи коммивояжера», Ричард Беллман, Journal of Assoc. Вычисление Маха. 9. 1962.

[2] «Подход динамического программирования к задачам последовательности», Майкл Хелд и Ричард М. Карп, Журнал Общества промышленной и прикладной математики 1:10. 1962 год

[3] «Динамическое программирование» (PDF) . Январь 2020 г. Архивировано из оригинала (PDF) 8 февраля 2015 г.

[1]

[2]

[3]