Файл: Изложение Вся основная информация в одной книге Графы, алгоритмы поиска, ранжирования и многое другое.pdf

36 ГЛАВА 1
организованы вводные данные, может существенно повлиять на способ ре- шения задачи. В целом линейное время — это лучшее, что можно ожидать от алгоритма, которому необходимо прочитать весь ввод, так как для n эле- ментов это потребует O(n) времени.
Если совместить линейное и логарифмическое время, получится алго- ритм логлинейного времени, продолжительность выполнения которого равна
n, умноженному на его логарифм, nlgn. Лучший алгоритм для сортировки
(то есть для упорядочивания элементов) имеет сложность O(nlgn). Это мо- жет показаться немного неожиданным, ведь если у вас есть n элементов и вы хотите сравнить каждый из них со всеми остальными, вам потребуется время
O(n
2
), что больше, чем O(nlgn). Кроме того, если вы хотите отсортировать n элементов, для их полного перебора точно понадобится время O(n). Их сор- тировка требует умножения этого n на коэффициент, меньший, чем само это число. Позже вы увидите, как этого можно добиться.
К следующей категории вычислительной сложности относится n, возве- денное в фиксированную степень, O(n
k
); это так называемая полиномиальная
сложность. Алгоритмы полиномиального времени эффективны, если не счи- тать редких случаев, когда k является большим числом. Мы обычно радуемся, когда при решении вычислительной задачи удается разработать алгоритм по- линомиального времени.
Сложность вида O(k
n
) называют экспоненциальной. Обратите внимание на то, что, в отличие от полиномиальной сложности, степень здесь изме- няется. Мы уже видели примеры взрывного экспоненциального роста. Вре- мени, оставшегося до тепловой смерти вселенной, не хватит для вычисления экспоненциальных алгоритмов с нетривиальным вводом. Такие алгоритмы интересны с теоретической точки зрения, так как они показывают, что ре- шение можно найти. Мы можем попытаться подобрать более подходящие ал- горитмы с меньшей сложностью или доказать, что их не существует; в по- следнем случае можно пойти на компромисс и удовлетвориться, к примеру, приблизительным решением.
Но кое-что растет даже быстрее, чем экспонента. Речь идет о факто-
риале. Напомним, что факториал натурального числа n (записывается как
n!) — это просто произведение всех натуральных чисел вплоть до (и вклю- чая) n: 100! = 1 × 2 × 3 × … × 100. Но если с 100! вы еще не сталкива- лись, то факториал 52! вам уже, наверное, попадался, даже если вы об этом не знаете. Это количество возможных комбинаций в колоде карт. Алго- ритмы, время выполнения которых измеряется факториалами, имеют фак-
ториальную сложность.

Числа вроде 100! являются довольно экзотическими, но они встречаются во многих повседневных ситуациях, и не только в карточных играх. Возьмем, к примеру, следующую задачу: «Если у нас есть список городов и расстояний между каждой парой, как найти кратчайший маршрут для посещения каж- дого города с последующим возвращением в исходную точку?». Это так назы- ваемая задача коммивояжера, и ее очевидное решение состоит в том, чтобы проверить каждый возможный маршрут, охватывающий все города. К со- жалению, это будет n! для n городов. Если количество городов превышает, скажем, 20, задача становится практически нерешаемой. Существуют алго- ритмы с немного лучшим временем выполнения, чем O(n!), но даже они яв- ляются непрактичными. Как ни удивительно, единственный способ решения такой прямолинейной задачи за приемлемое время — нахождение неопти- мального, но достаточно близкого к нему решения. Многие задачи, имею- щие большое практическое значение, являются труднорешаемыми, то есть нам неизвестен практичный алгоритм, который может дать точный резуль- тат. Тем не менее поиск аппроксимационных алгоритмов остается динамич- ной областью информатики.
В приведенной ниже таблице приводятся результаты различных функций, разделенных по рассмотренным только что категориям сложности, для раз- ных значений n. В первой строке указаны значения n, соответствующие ли- нейной сложности; в следующих строках сложность возрастает. Вместе с n увеличивается и результат функции, но это происходит по-разному. Функция
n
3
переходит от миллиона сразу к квинтиллиону, но это ничто по сравнению с 2 100
или 100!. Мы сделали отступ после n
k
, чтобы отделить практичные алго- ритмы от непрактичных. Границей здесь выступают алгоритмы полиноми- ального времени, которые, как мы уже видели, можно использовать на прак- тике. Все, что сложнее, обычно не имеет практического применения.
n
lgn
nlgn
1 10 100 1000 1 000 000 0
3 32 6 64 9 97 19 93 0
33 22 664 39
,
,
,
,
,
,
99 965 78 1 9 10 1
100 10 000 1 000 000 10 1
1000 1 000 000 7
2 12 3
,
,
×
n
n
110 10 1
10 100 1000 1 000 000 2
2 1024 1 3 10 10 10 9
18 30 301 1
n
k
k
k
k
k
n
, ×
00 157 2567 10 5 5 6 7 1 3 628 800 9 33 10 4 10 10
,
,
!
,
n
×
×

38 ГЛАВА 2
ГЛАВА 2
ГРАФЫ
В восемнадцатом веке славные жители Кёнигсберга прогуливались по своему городу воскресными днями. Кёнигсберг был построен на берегах реки Прегель, которая сформировала внутри городских стен два больших острова; эти ост- рова соединялись с континентальной частью и между собой семью мостами.
Из-за превратностей европейской истории Кёнигсберг часто переходил из рук в руки: от рыцарей Тевтонского ордена к Пруссии, России, Веймарской республике и нацистской Германии; после Второй мировой войны он стал частью СССР и был переименован в Калининград — это название он носит и по сей день. В наши дни он принадлежит России, хотя и не имеет с ней пря- мого сухопутного сообщения. Калининград находится в российском анклаве на берегу Балтийского моря, зажатый между Польшей и Литвой.
Когда-то славные горожане озаботились таким вопросом: возможно ли прогуляться по городу, перейдя все семь мостов ровно по одному разу? Это так называемая задача о семи кёнигсбергских мостах. Чтобы понять, о чем идет речь, взгляните на изображение Кёнигсберга того времени. Мосты об- ведены овалами. У города есть два острова, но на гравюре полностью виден только один из них; другой уходит вправо за пределы карты.

ГРАФЫ 39
Мы точно не знаем как, но об этой задаче узнал известный швейцарский математик Леонард Эйлер; она упоминается в письме от 9 марта 1736 года, ко- торое ему отправил мэр Данцига, прусского города, расположенного 129 ки- лометрами восточнее Кёнигсберга (в настоящее время Данциг называется
Гданьск и принадлежит Польше). Переписка с Эйлером, по всей видимости, была одной из инициатив мэра по развитию математики в Пруссии.
В то время Эйлер жил в Санкт-Петербурге. Он занялся этой задачей и 26 ав- густа 1735 года представил свое решение членам Санкт-Петербургской акаде- мии наук. В следующем году Эйлер написал на латыни научный доклад с объ- яснением своего решения. Ответ на изначально поставленный вопрос был
отрицательным: по городу нельзя было прогуляться так, чтобы перейти каж- дый мост всего один раз. Это не просто занимательный исторический факт: решив эту задачу, Эйлер положил начало целому новому разделу математики, который посвящен графам.
Но, прежде чем переходить к графам, давайте посмотрим, как Эйлер подо- шел к решению этой задачи. Для начала он сделал ее максимально абстракт- ной. Для ее представления не требуется подробной карты Кёнигсберга. Эйлер нарисовал следующую диаграмму.
Он обозначил два острова буквами A и D, а два берега континентальной части — буквами
B и C. Эту диаграмму можно сделать еще более абстрактной, избавившись от физической гео- метрии, и свести все к связям между мостами, островами и континентальной частью, так как именно это имеет отношение к задаче.
Мы обозначили части суши окружностями и соединили их линиями — мостами. Теперь
A
C
B
D

40 ГЛАВА 2
задачу можно переформулировать следующим образом: если у вас есть ка- рандаш, возможно ли приложить его к любому кругу и, не отрывая его от бу- маги, пройтись им по каждой линии ровно один раз?
Эйлер предложил следующее решение. При посещении суши вы должны ее покинуть, за исключением тех случаев, когда это начало и конец вашей прогулки. Для этого каждая часть суши, если не считать начала и конца, дол- жна иметь четное количество мостов, чтобы вы могли зайти на нее по одному мосту, а выйти по другому. Теперь взгляните на рисунок и посчитайте коли- чество мостов, соединяющих каждую часть суши. Вы обнаружите, что в каж- дом случае это число нечетное: у A пять мостов, а у B, C и D их три. Где бы вы ни решили начать и закончить свою прогулку, у вас все равно останется две части суши, которые вам нужно посетить, и каждая из них имеет нечетное количество мостов. Мы не можем пройтись по каждому из этих мостов всего один раз.
Действительно, если в какой-то момент нашей прогулки мы посетим B, это означает, что мы уже прошлись по мосту, который ведет к этой части суши.
Чтобы ее покинуть, мы переходим по второму мосту. Позже нам нужно бу- дет пройти по третьему мосту, так как этого требует условие. Но в этом слу- чае мы застрянем в B, так как четвертого моста не существует, а мосты, кото- рые мы уже посетили, нельзя переходить повторно. То же самое относится к C и D, у которых также по три моста. Но тот же принцип применим и к точке A, если она является промежуточной: после перехода по всем ее пяти мостам мы не сможем ее покинуть, так как шестого моста попросту нет.
Наша диаграмма состоит из кругов и линий, которые их соединяют. Ис- пользуя правильную терминологию, мы создали структуру, составленную из узлов, или вершин, соединенных ребрами, или звеньями. Структура, состоя- щая из множества узлов и ребер, называется графом; Эйлер был первым, кто начал считать графы структурами и исследовать их свойства. Говоря совре- менным языком, задача о кёнигсбергских мостах имеет отношение к путям; путь в графе — это последовательность ребер, которые соединяют последо- вательность узлов. Таким образом данная задача сводится к поиску эйлерова
пути: маршрута, который проходит через каждую вершину графа ровно один раз. Путь, начинающийся и заканчивающийся в одном и том же узле, назы- вается циклом. Если совпадают начало и конец эйлерова пути, получается
эйлеров цикл.
Графы имеют настолько обширное применение, что им посвящены це- лые книги. Все, что можно смоделировать в виде узлов, соединенных с дру- гими узлами, подходит под определение графа. Это позволяет задавать

ГРАФЫ 41
всевозможные интересные вопросы; здесь эта тема затрагивается лишь по- верхностно.
Но, прежде чем двигаться дальше, упомянем об одной детали, чтобы удо- влетворить самых скрупулезных читателей. Мы упоминали о том, что граф — это структура, состоящая из множества вершин и ребер. В математике эле- менты множества не повторяются. Но в нашем представлении Кёнигсберга некоторые ребра используются больше одного раза — например, те, что со- единяют A и B. Ребро определяется его начальной и конечной точками, по- этому два моста между A и B на самом деле являются двумя экземплярами одного ребра. Таким образом, совокупность ребер является не множеством, а мультимножеством, которое допускает дублирование элементов. Поэтому диаграмма мостов Кёнигсберга — это не граф, а, скорее, мультиграф.

Довольно общее определение графа охватывает все, что можно описать в виде объектов, соединенных с другими объектами.

ГРАФЫ 43
A
B
C
D
Еще один (огромный) пример графа — Всемирная паутина. Ее можно представить в виде узлов (веб-страниц) и ребер (гиперссылок, соединяющих каждую пару страниц). Это направленный граф, поскольку страница, на ко- торую ссылаются, может не содержать обратной ссылки.
Если граф можно обойти, вернувшись в исходный узел, это означает, в нем есть цикл. Циклы имеют не все графы. У кёнигсбергского графа есть цикл, хоть и не эйлеров. В истории науки известен знаменитый циклический граф (на самом деле мультиграф): модель молекулярной структуры бензола, которую создал Август Кекуле:
Граф, у которого нет цикла, называется ациклическим. Направленные ациклические графы относятся к отдельной важной категории. Их обычно обозначают аббревиатурой DAG (от англ. directed acyclic graph). У них есть много применений; например, они используются для представления прио- ритетов выполнения задач (задачи — узлы, а приоритеты — ребра между ними), зависимостей, предварительных условий и других похожих конструк- ций. Пока оставим ациклические графы и займемся циклическими; это будет наше первое знакомство с алгоритмами для работы с графами.
Пути и ДНК
Одним из самых важных научных достижений последних десятилетий была расшифровка человеческого генома. Благодаря методикам, созданным в ходе