7.6.Задача коммивояжера.
Число гамильтоновых циклов в графе G=(V,E), |V|=n, |E|=m, с матрицей весов ребер C=(cij), равно (n-1)!. Сумму весов ребер одного гамильтонова цикла можно найти за O(n). Общая трудоемкость алгоритма O(n!) = O((n/e)n+1/2). Так может быть здесь, как и в предыдущем случае, можно ее сократить до простого полинома? Оказывается нельзя. На сегодня не существует полиномиальных алгоритмов решения задачи коммивояжера, лучшие алгоритмы имеют экспоненциальную трудоемкость «в худшем случае».
В таких случаях на практике вместо точного решения пытаются найти приближенное или используют методы «направленного перебора» (методы ветвей и границ), но об этом мы поговорим позже.
7.7.Задача о кратчайшем пути.
В графе G=(V,E), |V|=n, |E|=m, с матрицей весов ребер C=(cij) для двух фиксированных вершин ищется путь наименьшей длины между ними. (Длина пути – сумма весов входящих в него ребер). Если мы будем искать его методом полного перебора, то снова получим экспоненциальную оценку. И ничего с ней поделать нельзя, если веса ребер – произвольные числа. А если они неотрицательны, то можно избежать переборного алгоритма и построить более эффективный.
Алгоритм Дейкстры.
Схема алгоритма.
Обозначения. w[ij] — вес (длина) ребра ij; s — вершина, расстояния от которой ищутся; U — множество посещенных вершин; d[u] — по окончании работы алгоритма равно длине кратчайшего пути из s до вершины u; p[u] — по окончании работы алгоритма содержит кратчайший путь из s в u (это вектор, который вначале содержит только s при каждом последующем дополнении: p[u]=p[v*] u
в него включается очередная вершина пути).
В простейшей реализации для хранения чисел d[i] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевых переменных. В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом. Массив флагов заполняется нулями. Затем запускается основной цикл. На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин i c флагом 0 d[i]-∞. Последний случай возможен тогда и только тогда, когда граф G не связан. Так мы хаходим кратчайшие пути из s во все вершины графа. Если нужно найти кратчайший путь в конкретную вершину t, то алгоритм останавливается как только выполнится неравенство d[t]<∞.
begin
d[s]=0
p[s]= s
U=0
for each u
d[u]=∞
while
d[v*]=
for each u
if
and (v*,u)
E
then
if d[u] > d[v*] + w(v*,u) then
d[u]=d[v*]+w(v*,u)
p[u]=p[v*] u
U=U v*
end
Пусть все веса неотрицательны. Положимь l(v) — длина кратчайшего пути из вершины s в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина s. В этот момент d(s)=l(s)=0. Шаг. Пускай мы выбрали для посещения вершину z s. Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется d[v]≥l[v] (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P — кратчайший путь из s в z, y — первая непосещённая вершина на P, x — предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из s через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y) (если существует k, такое что l(k) + w(ky) < l(x) + w(xy) то x не принадлежит P). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть. d[z] ≤d[y]=l[y]≤l[z]. Комбинируя это с d[z]≥l[z], имеем d(z)=l(z), что и требовалось доказать.Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G.
В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
Для разреженных графов (то есть таких, для которых m много меньше n²) непосещенные вершины можно хранить в двоичной пирамиде, а в качестве ключа использовать значения d[i], тогда время извлечения вершины станет log n, при том, что время модификации d[i] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(nlog n + mlog n)
Если для хранения непосещенных вершин использовать фибоначчиева пирамида, для которой удаление происходит в среднем за O(log n), а уменьшение значения в среднем за O(1), то время работы алгоритма составит O(nlog n + m).
Сложность алгоритма резко растет, если допустить отрицательные веса, в этом случае могут появиться циклы отрицательной длины, прохождение по которым уменьшает текущее значение минимального расстояния от s.