Кузюрин Н.Н. Фомин С.А. Эффективные алгоритмы и сложность вычислений

Подождите немного. Документ загружается.

1.1. Примеры задач и алгоритмов 21

Можем ли мы, как и в задаче о возведении в степень, ожи-

дать существования существенно более эффективного алгорит-

ма решения? Оказывается, это весьма маловероятно, вычисле-

ние дискретного логарифма является очень сложной задачей,

и самые быстрые из известных алгоритмов требуют сверхполи-

номиального (по длине двоичной записи p) времени. На этом

важном свойстве (свойстве односторонней эффективной вы-

числимости модульной экспоненты) основано множество про-

токолов современной криптографии.

Еще одним примером взаимно обратных преобразований

подобного рода являются операции произведения натуральных

чисел и разложение на множители. Пусть p и q — два про-

стых числа. Тогда не составляет особого труда вычислить их

произведение n = pq (применив, например, школьный алго-

ритм умножения «столбиком»). Однако если мы знаем лишь

n и требуется найти p и q, то это уже труднорешаемая задача,

для которой неизвестны эффективные алгоритмы решения. На

трудности задачи факторизации (разложения на множители)

основана одна из самых известных криптосистем RSA.

Рассмотрим одну из классических задач.

Задача 3. «Наибольший общий делитель»

Для заданных натуральных a и b найти максимальное q,

для которого a

q и b

q (a и b кратны q).

Проанализируем алгоритм Евклида (алгоритм 4 «НОД»)

для решения этой задачи (для определенности ниже будем счи-

тать, что a ≤ b.). Базовое соотношение, лежащее в основе ал-

горитма Евклида, таково:

НОД(a, b) = НОД(a, r), b = at + r, 0 ≤ r < a.

Лемма 1.1.1. Время работы алгоритма 4 «НОД» составля-

ет O(log a + log b) арифметических операций над натуральны-

ми числами.

22 Глава 1. Алгоритмы и их сложность

Алгоритм 4. Алгоритм Евклида

def gcd (a, b):

print a, b

if a = 0 :

return b

return gcd (b % a, a)

Calculating gcd(123456, 6122256):

123456 6122256

72912 123456

50544 72912

22368 50544

5808 22368

4944 5808

864 4944

624 864

240 624

144 240

96 144

48 96

0 48

gcd(123456, 6122256) = 48

Доказательство. Имеем

b ≥ a + (b mod a) ≥ 2(b mod a) ≡ 2r.

Отсюда получаем, что r ≤

. Таким образом, ar ≤ ab/2, т. е.

произведение ab уменьшается на каждой итерации вдвое, и по-

сле dlog(ab)e итераций станет меньше 1, т. е. равно нулю. А это

означает, что a = 0 (т. е. НОД уже найден).

Алгоритм 5. Неэффективный алгоритм для «НОД»

def gcd_non_eﬀective (a, b):

print a, b

if a = 0 :

return b

return gcd (max (a, b) − min (a, b), min (a, b))

Длина записи исходных данных в этой задаче есть O(log a+log b)

и по порядку совпадает с числом операций алгоритма Евклида,

т. е. алгоритм является эффективным. Отметим, что ал-

горитм 5 «Неэффективный НОД» (модификация алгорит-

ма 4 «НОД», где деление с остатком заменено на вычитание

1.1. Примеры задач и алгоритмов 23

меньшего числа из большего) не является столь же эффектив-

ным — ведь число операций вычитания пропорционально

а не сумме их логарифмов, и на входных данных, где b мно-

го больше a, алгоритм будет показывать экспоненциальную

сложность.

Таким образом, мы увидели, что, несмотря на внешнюю по-

хожесть, сложность подобных задач может существенно отли-

чаться. Для обнаружения и понимания такой разницы и нужен

анализ сложности, являющийся предметом нашего курса.

1.1.2. Задачи на графах:



Коммивояжер





Крат-

чайшие пути





Остовные деревья



$70

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$120

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$30

$10

Berlin

$50

Minsk

$120

Moscow

$60

Kiev

$80

$30

$20

$15

$50

$15

$10

NY ($60)

Moscow

$60

Berlin ($20)

$50

Kiev

$80

Minsk

Start

$15

$50

$10

$20

$15

$30

Классические задачи на гра-

фах. Различия сложности

простых алгоритмов, реша-

ющих эти задачи.

Рассмотрим несколько классических задач на графах.

Задача 4. «Коммивояжер», «TSP

». Заданы неориентиро-

ванный граф из n вершин-городов, и d

≡ d(v

, v

) — положи-

тельные целые расстояния между городами.

Чему равна наименьшая возможная длина гамильтонова

цикла (кольцевого маршрута, проходящего по одному разу че-

рез все города)? т. е. нужно найти минимально возможное

значение суммы

min

p∈





1 2 . . . n

. . . .





n−1

i=1

i+1

+ d

, (1.1)

где минимум берется по всем перестановкам p чисел 1, . . . , n.

В англоязычной литературе — Traveling Salesman Problem.

24 Глава 1. Алгоритмы и их сложность

Переборный алгоритм для задачи о коммивояжере просто

перебирает все возможные перестановки городов с фиксиро-

ванным «стартовым» городом (см. алгоритм 6 «TSP-перебор»).

При анализе его сложности видно, что вычисление индивиду-

альной суммы (1.1) не представляет особых трудностей и тре-

бует Cn операций, где C — некоторая константа. Проблема

состоит в том, что этот процесс придется повторить (n − 1)!

раз, что дает общую сложность алгоритма Ω(n!). Некоторые

значения факториала приведены в таблице 1.1.

Т а б л и ц а 1.1

Значения функции n!

n 5 8 10 13 15 30

n! 120 40320 3.6 · 10

6.2 · 10

1.3 · 10

2.7 · 10

Алгоритм 6. Переборный алгоритм для «TSP»

def TSP_BruteForce (G) :

MinPath ← MinPathLength ← None

перебор всех перестановок с фиксированным первым узлом

for path ∈ xpermutations (G.nodes ()[1 : ]):

PathLength ← getPathLength (path, G.nodes ()[0])

if ¬MinPathLength ∨ MinPathLength > PathLength:

MinPathLength, MinPath ← PathLength, path

return MinPath, MinPathLength

Иллюстрация работы показана на рис. 1.1.

Видно, что при n = 5 расчет всех вариантов согласно пе-

реборному алгоритму может быть произведен вручную. При

n = 8 для его проведения в разумный отрезок времени нужно

привлечь программируемый калькулятор, а при n = 10 — уже

более быстродействующую вычислительную технику. Когда

число городов дойдет до 13, потребуется суперкомпьютер,

1.1. Примеры задач и алгоритмов 25

а случай n = 15 выходит за пределы возможностей любой

современной вычислительной техники.

Число возможных вариантов при n = 30 превышает коли-

чество атомов на Земле

Теперь рассмотрим задачу 5, на первый взгляд — очень по-

хожую на задачу 4 «TSP».

Задача 5. «Кратчайший путь в графе»

Заданы n вершин графа (узлов сети) v

, v

, . . . , v

и поло-

жительные целые длины дуг d

≡ d(v

, v

) между ними.

Нужно для всех k ∈ (2 . . . n) найти минимальную длину

пути из v

в v

Разумеется, и эту задачу можно решать переборным алго-

ритмом, аналогичным алгоритму 6 «TSP-перебор», но интерес-

но, можно ли разработать точный эффективный алгоритм, ис-

ключающий (или, по меньшей мере, минимизирующий) непо-

средственный перебор вариантов.

Оказывается, в данном случае можно. Здесь важным фак-

том является то, что если у нас есть кратчайший путь от v

до w, проходящий через вершину y, назовем его (v → w)

∗

, то

его первая часть от v до y, (v → y)

∗

тоже будет кратчайшим

путем.

Действительно, если бы это было не так, т. е. существовал

бы путь (v → y)

длины меньшей, чем (v → y)

∗

, то можно

Конечно, разработаны различные методы сокращения перебора, кро-

ме того, переборные задачи допускают эффективное распараллеливание

для вычисления на многопроцессорных машинах или сети компьютеров.

В частности, в 2004 году для задачи 4 «TSP» на 24978 городах Швеции

было найдено оптимальное решение на многопроцессорном кластере (96

dual processor Intel Xeon 2.8 GHz). Если измерять вычислительное вре-

мя относительно одного процессора «single Intel Xeon 2.8 GHz processor»,

то было потрачено 85 лет. См. отчет http://www.tsp.gatech.edu/sweden/

index.html. Но это не отменяет высказанных соображений о непрактич-

ности использования экспоненциальных алгоритмов перебора, кроме слу-

чаев входных данных ограниченного размера.

В англоязычной литературе — Shortest Path Problem.

26 Глава 1. Алгоритмы и их сложность

Рис. 1.1. Работа алгоритма 6 «TSP-перебор»

[’NY’, ’Moscow’, ’Minsk’, ’Berlin’, ’Kiev’] 205

[’NY’, ’Moscow’, ’Minsk’, ’Kiev’, ’Berlin’] 170

[’NY’, ’Moscow’, ’Berlin’, ’Minsk’, ’Kiev’] 225

[’NY’, ’Moscow’, ’Berlin’, ’Kiev’, ’Minsk’] 275

[’NY’, ’Moscow’, ’Kiev’, ’Minsk’, ’Berlin’] 155

[’NY’, ’Moscow’, ’Kiev’, ’Berlin’, ’Minsk’] 240

[’NY’, ’Minsk’, ’Moscow’, ’Berlin’, ’Kiev’] 295

[’NY’, ’Minsk’, ’Moscow’, ’Kiev’, ’Berlin’] 225

[’NY’, ’Minsk’, ’Berlin’, ’Moscow’, ’Kiev’] 280

[’NY’, ’Minsk’, ’Berlin’, ’Kiev’, ’Moscow’] 240

[’NY’, ’Minsk’, ’Kiev’, ’Moscow’, ’Berlin’] 245

[’NY’, ’Minsk’, ’Kiev’, ’Berlin’, ’Moscow’] 275

[’NY’, ’Berlin’, ’Moscow’, ’Minsk’, ’Kiev’] 210

[’NY’, ’Berlin’, ’Moscow’, ’Kiev’, ’Minsk’] 245

[’NY’, ’Berlin’, ’Minsk’, ’Moscow’, ’Kiev’] 175

[’NY’, ’Berlin’, ’Minsk’, ’Kiev’, ’Moscow’] 155

[’NY’, ’Berlin’, ’Kiev’, ’Moscow’, ’Minsk’] 225

[’NY’, ’Berlin’, ’Kiev’, ’Minsk’, ’Moscow’] 170

[’NY’, ’Kiev’, ’Moscow’, ’Minsk’, ’Berlin’] 175

[’NY’, ’Kiev’, ’Moscow’, ’Berlin’, ’Minsk’] 280

[’NY’, ’Kiev’, ’Minsk’, ’Moscow’, ’Berlin’] 210

[’NY’, ’Kiev’, ’Minsk’, ’Berlin’, ’Moscow’] 225

[’NY’, ’Kiev’, ’Berlin’, ’Moscow’, ’Minsk’] 295

[’NY’, ’Kiev’, ’Berlin’, ’Minsk’, ’Moscow’] 205

Оптимальный путь: [’NY’, ’Moscow’, ’Kiev’, ’Minsk’, ’Berlin’] => 155

Berlin

$50

Minsk

$120

Moscow

$60

Kiev

$80

$30

$20

$15

$50

$15

$10

1.1. Примеры задач и алгоритмов 27

было бы улучшить оптимальный путь (v → w)

∗

, заменив в нем

(v → y)

∗

на (v → y)

Задачи с подобными свойствами, когда оптимальное реше-

ние можно легко получить из оптимальных решений подза-

дач, обычно хорошо решаются так называемыми «жадны-

ми алгоритмами», примером которых может служить ал-

горитм

7 «Дейкстры» для задачи 5 «SPP». В алгорит-

ме 7 «Дейкстры» мы итерационно поддерживаем два мно-

жества вершин:

• V isited — множество вершин, до которых мы уже на-

шли кратчайший путь, ассоциированных со стоимостями

кратчайших путей от стартовой вершины до них.

• T oV isit — множество вершин, которые достижимы од-

ной дугой из множества вершин V isited, ассоциирован-

ных с верхними оценками стоимости пути до них.

На каждой итерации мы выбираем из достижимых вершин вер-

шину v, самую ближнюю к стартовой вершине s, и переносим

ее из множества T oV isit в множество V isited, увеличиваем

множество «кандидатов» T oV isit ее соседями и пересчитываем

верхнюю оценку удаленности вершин из T oV isit до вершины s.

Различные варианты этого алгоритма используются при маршрути-

зации интернет-трафика. Например, см. стандарты OSPF, Open Shortest

Path First Routing Protocol, RFC 2740.

28 Глава 1. Алгоритмы и их сложность

В иллюстрации выполнения алгоритма 7 «Дейкстры» мы

показываем изменение на каждой итерации хэш-таблиц V isited

и ToV isit, а в конце изображен входной граф, где сплошными

линиями нарисованы найденные кратчайшие пути, а пункти-

ром — имеющиеся ребра с ассоциированными длинами.

Алгоритм 7. Алгоритм Дейкстры

def dijkstra (G, startNode) :

Visited ← {} # хэш (узел → стоимость) посещенных вершин

ToVisit ← {startNode: 0} # соседи посещенных (уз. → стоим.)

Paths ← {startNode: [startNode]} # узел → кратчайший путь

while ToVisit: # пока есть куда стремиться

v ← argmin (ToVisit) # выбираем ближайшую

Visited[v] ← ToVisit[v] # фиксируем откуда пришли в v

del ToVisit[v] # кратчайший путь к v найден

for w ∈ G.neighbors (v): # для всех соседей вершины v

if (w 6∈ Visited) : # еще не нашли кратчайший путь

обновляем кратчайшие пути

vwLength ← Visited[v] + G.get_edge (v, w)

if (w 6∈ ToVisit) ∨ (vwLength < ToVisit[w]) :

ToVisit[w] ← vwLength # обновляем цену

Paths[w] ← Paths[v] + [w] # посещения соседа

return (Visited, Paths)

Иллюстрация работы показана на рис. 1.2.

Лемма 1.1.2. Алгоритм 7 «Дейкстры» корректен, т. е. все

найденные им пути оптимальны.

Доказательство. Обозначим через δ(v, w) длину оптимально-

го пути из v в w. Допустим, алгоритм некорректен — это озна-

чает, что алгоритм построит неоптимальный путь до какой-то

вершины. Пусть вершина u будет первой вершиной, до кото-

рой «неоптимально» доберется наш алгоритм, построив путь

(s → u)

∗

, т. е. V isited[u] > δ(s, u), но все его подпути (s → w)

1.1. Примеры задач и алгоритмов 29

Рис. 1.2. Работа алгоритма 7 «Дейкстры»

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$10

$75

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$120

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$10

$75

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$120

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$10

$70

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$120

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$30

$10

$70

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$120

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$30

$10

$70

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$100

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$30

$10

$70

Moscow

$15

$60

Berlin

$20

$50

Vladivostok

$100

$30

Minsk

Start

$15

$50

Kiev

$15

$10

$105

$20

$15

$30

Munich

$30

$10

30 Глава 1. Алгоритмы и их сложность

еще будут оптимальными и V isited[w] = δ(s, w). Далее будем

рассматривать действия алгоритма в той итерации, в которой

он выбирает u.

Рассмотрим оптимальный путь (s → u)

(он, как мы выше

предположили, не совпадает с (s → u)

∗

). Он должен содержать

в себе предпоследнюю вершину y /∈ V isited. В противном слу-

чае, если бы предпоследняя вершина z из (s → u)

в момент

выбора u принадлежала V isited, то был бы построен оптималь-

ный кратчайший путь, т.к. V isited[z] = δ(s, z) и

T oV isit[u] ≤ V isited[z] + δ(z, u) = δ(s, u),

что приводит нас к противоречию с высказанным допущением

о неоптимальности выбранного алгоритмом пути.

Значит, в момент выбора алгоритмом вершины u должны

существовать вершины x, y, идущие подряд в оптимальном пу-

ти (s → u)

, причем y /∈ V isited, а x ∈ V isited.

Следовательно, y ∈ T oV isit и выполняется неравенство

T oV isit[y] ≤ V isited[x] + δ(x, y) = δ(s, x) + δ(x, y) = δ(s, y).

Далее, из неравенств

• δ(s, y) < δ(s, u) (в силу положительности весов, т. е. длин

дуг),

• V isited[u] ≤ T oV isit[y] = δ(s, y) (т.к. алгоритм выбрал на

этой итерации вершину u, а не y)

следует V isited[u] < δ(s, u). Противоречие.

Лемма 1.1.3. Трудоемкость алгоритма 7 «Дейкстры» со-

ставляет O(n

) операций, где n — число вершин.

Доказательство. Внешний цикл по вершинам дает множи-

тель n. Внутренний цикл содержит выбор минимального эле-

мента — O(n) плюс пересчет оценок длин для соседей выбран-

ного узла — O(n). Итого — O(n