Введение

Зачем нужна эта книга

Многие из моих знакомых разработчиков пришли в профессию из самых разных областей. У одних — высшее образование в области Computer Science; другие изучали фотографию, математику или даже не окончили университет.

В последние годы я заметил, что программисты все чаще стремятся изучить Compu­ter Science по ряду причин:

• чтобы стать хорошими программистами;

• чтобы на собеседованиях отвечать на вопросы про алгоритмы;

• чтобы удовлетворить свое любопытство в области Com­puter Science или наконец перестать сожалеть о том, что в свое время у них не было возможности освоить этот предмет.

Эта книга для всех вас.

Многие найдут здесь темы, интересные сами по себе. Я попытался показать, в каких реальных (неакадемических) ситуациях эти знания будут полезны. Хочу, чтобы, прочитав эту книгу, вы получили такие же знания, как после изучения базового курса по Computer Science, а также научились их применять.

Проще говоря, цель этой книги — помочь вам стать более квалифицированным и опытным программистом благодаря лучшему пониманию Computer Science. Мне не под силу втиснуть в одну книгу 20-летний стаж преподавания в колледже и профессиональный опыт... однако я постараюсь сделать максимум того, на что способен. Надеюсь, что вы найдете здесь хотя бы одну тему, о которой сможете сказать: «Да, теперь мне это понятно» — и применить знания в своей работе.

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

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

Чего вы не найдете в издании

Смысл книги состоит в том, чтобы читатель смог лучше понимать Computer Science и применять знания на практике, а вовсе не в том, чтобы полностью заменить четыре года обучения.

В частности, это не книга с доказательствами. Действительно, начиная с части VI, рассмотрены методы доказательства, однако стандартные алгоритмы обычно приводятся здесь без доказательств. Идея в том, чтобы читатель узнал о существовании этих алгоритмов и научился их использовать, не вникая в подробности. В качестве книги с доказательствами, написанной для студентов и аспирантов, я настоятельно рекомендую Introduction to Algorithms1 («Алгоритмы. Вводный курс») Кормена (Cormen), Лейзерсона (Leiserson), Ривеста (Rivest) и Стейна (Stein) (этих авторов обычно объединяют под аббревиатурой CLRS).

Это и не книга по программированию: вы не найдете здесь рекомендаций, когда использовать числа типа int, а ко­гда — double, или объяснений, что такое цикл. Предполагается, что читатель сможет разобраться в листингах на псевдокоде, используемых для описания алго­ритмов2. Цель книги — связать концепции Computer Science с уже знакомыми читателю методами программирования.

Дополнительные ресурсы

Для тех, кто хочет подробнее изучить ту или иную тему, я включил в сноски ссылки на дополнительные материалы. Кроме того, по адресу http://www.whatwil­liamsaid.com/books/ вы найдете тесты для самопроверки к каждой главе.

Что дальше

Я был намеренно краток и старался опускать детали, которые, будучи интересными сами по себе, не требуются для понимания описываемых концепций. В следующих книгах я собираюсь более подробно остановиться на некоторых областях, представляющих особый интерес.

Чтобы предложить тему для следующей книги, подписаться на рассылку или просто задать вопрос, посетите мой сайт: http://www.whatwilliamsaid.com/books. С нетерпением жду ваших сообщений.

От издательства

Ваши замечания, предложения, вопросы отправляйте по адресу comp@piter.com (издательство «Питер», компьютерная редакция).

Мы будем рады узнать ваше мнение!

На веб-сайте издательства www.piter.com вы найдете по­дробную информацию о наших книгах.

Часть I. Основы Computer Science

1. Асимптотическое время выполнения

1.1. Что такое алгоритм

Предположим, вам нужно научить робота делать бутерброд с арахисовым маслом (рис. 1.1). Ваши инструкции могут быть примерно такими.

1. Открыть верхнюю левую дверцу шкафчика.

2. Взять банку с арахисовым маслом и вынуть ее из шкафчика.

3. Закрыть шкафчик.

4. Держа банку с арахисовым маслом в левой руке, взять крышку в правую руку.

5. Поворачивать правую руку против часовой стрелки, пока крышка не откроется.

6. И так далее...

 

Рис. 1.1. Робот — изготовитель бутербродов

Это программа: вы описали каждый шаг, который компьютер должен выполнить, и указали всю информацию, которая требуется компьютеру для выполнения каждого шага. А теперь представьте, что вы объясняете человеку, как сделать бутерброд с арахисовым маслом. Ваши инструкции будут, скорее всего, такими.

1. Достаньте арахисовое масло, джем и хлеб.

2. Намажьте ножом арахисовое масло на один ломтик хлеба.

3. Намажьте ложкой джем на второй ломтик хлеба.

4. Сложите два ломтика вместе. Приятного аппетита!

Это алгоритм: процесс, которому нужно следовать для получения желаемого результата (в данном случае бутерброда с арахисовым маслом и джемом). Обратите внимание, что алгоритм более абстрактный, чем программа. Программа сообщает роботу, откуда именно нужно взять предметы на конкретной кухне, с точным указанием всех необходимых деталей. Это реализация алгоритма, которая предоставляет все важные детали, но может быть выполнена на любом оборудовании (в данном случае — на кухне), со всеми необходимыми элементами (арахисовое масло, джем, хлеб и столовые приборы).

1.2. Почему скорость имеет значение

Современные компьютеры достаточно быстры, поэтому во многих случаях скорость алгоритма не особенно важна. Когда я нажимаю кнопку и компьютер реагирует за 1/25 секунды, а не за 1/100 секунды, эта разница для меня не имеет значения — с моей точки зрения, компьютер в обоих случаях реагирует мгновенно.

Но во многих приложениях скорость все еще важна, например, при работе с большим количеством объектов. Предположим, что у вас есть список из миллиона элементов, который необходимо отсортировать. Эффективная сортировка занимает одну секунду, а неэффективная может длиться несколько недель. Возможно, пользователь не захочет ждать, пока она закончится.

Мы часто считаем задачу неразрешимой, если не существует известного способа ее решения за разумные сроки, где «разумность» зависит от различных реальных факторов. Например, безопасность шифрования данных часто зависит от сложности разложения на множители (факторизации) больших чисел. Если я отправляю вам зашифрованное сообщение, содержимое которого нужно хранить в секрете в течение недели, то для меня не имеет значения, что злоумышленник перехватит это сообщение и расшифрует его через три года. Задача не является неразрешимой — просто наш любитель подслушивать не знает, как решить ее достаточно быстро, чтобы решение было полезным.

Важным навыком в программировании является уме­ние оптимизировать только те части программы, которые необходимо оптимизировать. Если пользовательский интерфейс работает на 1/1000 секунды медленнее, чем мог бы, это никого не волнует — в данном случае мы предпочли бы незаметному увеличению скорости удобочитаемую программу. А вот код, расположенный внутри цикла, который может выполняться миллионы раз, должен быть написан максимально эффективно.

1.3. Когда секунды (не) считаются

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

Вместо того чтобы измерять фактическую скорость выполнения каждого шага, которая будет различаться для разных роботов и кухонь, лучше подсчитать (и минимизировать) количество шагов. Например, алгоритм, который требует, чтобы робот сразу брал и нож и ложку, эффективнее, чем алгоритм, в котором робот открывает ящик со столовыми приборами, берет нож, закрывает ящик, кладет нож на стол, снова открывает ящик, достает ложку и т.д.

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

Следует признать, что не все шаги потребуют одинакового времени выполнения; скорее всего, взять нож — быстрее, чем намазать арахисовое масло на хлеб. Поэтому мы хотим не столько узнать точное количество шагов, сколько иметь представление о том, сколько шагов потребуется в зависимости от размера входных данных. В случае с нашим роботом время, необходимое для приготовления бутерброда, при увеличении количества бутербродов не увеличивается (при условии, что нам хватит джема).

Два компьютера могут выполнять алгоритм с разной скоростью. Это зависит от их тактовой частоты, объема доступной памяти, количества тактовых циклов, требуемого для выполнения каждой инструкции, и т.д. Однако обоим компьютерам, как правило, требуется приблизительно одинаковое число инструкций, и мы можем измерить скорость, с которой количество требуемых инструкций увеличивается в зависимости от размера задачи (рис. 1.2). Например, при сортировке массива чисел, если увеличить его размер в тысячу раз, один алгоритм может потребовать в тысячу раз больше команд, а второй — в миллион раз больше3.

 

Рис. 1.2. Более эффективный робот — изготовитель бутербродов

Часто мы хотим измерить скорость алгоритма несколькими способами. В жизненно важных ситуациях — например, при запуске двигателей на зонде, который приземляется на Марсе, — мы хотим знать время выполнения при самом неблагоприятном раскладе. Мы можем выбрать алгоритм, который в среднем работает немного медленнее, но зато гарантирует, что его выполнение никогда не займет больше времени, чем мы считаем приемлемым (и наш зонд не разобьется вместо того, чтобы приземлиться). Для более повседневных сценариев мы можем смириться со случайными всплесками времени выполнения, если при этом среднее время не растет; например, в видеоигре мы бы предпочли генерировать результаты в среднем быстрее, смирившись с необходимостью время от времени прерывать длительные вычисления. А бывают случаи, когда мы хотели бы знать наилучшую производительность. Однако в большинстве ситуаций мы просто рассчитываем наихудшее время выполнения, которое все равно часто совпадает со средним временем выполнения.

1.4. Как мы описываем скорость

Предположим, у нас есть два списка целых чисел, которые мы хотим отсортировать: {1, 2, 3, 4, 5, 6, 7, 8} и {3, 5, 4, 1, 2}. Сортировка какого списка займет меньше времени?

Ответ на вопрос: неизвестно. Для одного алгоритма сортировки тот факт, что первый список уже отсортирован, позволит почти сразу завершить работу. Для другого алгоритма решающим фактором может быть то, что второй список короче. Но обратите внимание, что оба свойства входных данных — размер списка и последовательность расположения чисел — влияют на количество шагов, необходимых для сортировки.

Если некоторое свойство, например «отсортированность», изменяет время выполнения конкретного алгоритма только на постоянную величину, мы можем просто его игнорировать, поскольку его влияние незаметно по сравнению с влиянием размера задачи. Например, робот может делать бутерброды с виноградным или малиновым джемом, но банка с малиновым джемом открывается немного дольше. Если робот делает миллион бутербродов, то влияние выбора джема на время приготовления бутерброда незаметно на фоне количества бутербродов. Поэтому мы можем его игнорировать и просто сказать, что приготовление миллио­на бутербродов занимает примерно в миллион раз больше времени, чем приготовление одного бутерброда.

С точки зрения математики мы вычисляем асимптотическое время выполнения алгоритма, то есть скорость увеличения времени выполнения в зависимости от размера входных данных. Нашему роботу, который делает бутерброды, требуется некоторое постоянное время c для приготовления одного бутерброда и в n раз больше времени, то есть cn, чтобы сделать n бутербродов. Мы отбрасываем константу и говорим, что наш алгоритм приготовления бутербродов занимает время O(n) (произносится как «О большое от n» или просто «О от n»). Это означает, что время выполнения в худшем случае пропорционально количеству бутербродов, которое будет сделано. Нас интересует не точное количество необходимых шагов, а скорость, с которой это число увеличивается по мере роста размера задачи (в данном случае — количества бутербродов).

1.5. Скорость типичных алгоритмов

Сколько бы бутербродов ни делал наш робот, это не увеличивает время, необходимое для изготовления одного бутерброда. Это линейный алгоритм — общее время выполнения пропорционально количеству обрабатываемых элементов. Для большинства задач это лучшее, чего можно добиться4. Типичный пример линейного алгоритма в программировании — чтение списка элементов и выполнение некоторой задачи для каждого элемента списка: время, затрачиваемое на обработку каждого элемента, не зависит от других элементов. Есть цикл, который выполняет постоянный объем работы и осуществляется один раз для каждого из n элементов, поэтому все вместе занимает O(n) времени.

Но чаще количество элементов списка влияет на объем работы, которую необходимо выполнить для отдельного элемента. Алгоритм сортировки может обрабатывать каждый элемент списка, разделяя список на два меньших списка, и повторять это до тех пор, пока все элементы не окажутся в своем собственном списке. На каждой итерации алгоритм выполняет O(n) операций и требует O(lg n) итераций, что в общей сложности составляет O(n) ×O(lg n) = O(n lg n) времени.5

Математическое предупреждение Логарифм описывает, в какую степень необходимо возвести число, указанное в основании, чтобы получить желаемое значение. Например, log10 1000 = 3, так как 103 = 1000. В компьютерах мы часто делим на 2, поэтому обычно используются логарифмы по основанию 2. Сокращенно log2 n обозначается как lg n.2 Таким образом, lg 1 = 0, lg 2 = 1, lg 4 = 2, lg 8 = 3 и т.д.

С этого момента время выполнения начинает ухудшаться. Рассмотрим алгоритм, в котором каждый элемент множества сравнивается со всеми остальными элементами множества, — здесь мы выполняем работу, занимающую O(n) времени, O(n) раз, то есть общее время выполнения алгоритма — O(n2). Это квадратичное время.

Все алгоритмы, у которых время выполнения пропорционально количеству входных данных, возведенному в некоторую степень, называются полиномиальными алгоритмами; такие алгоритмы принято считать быстрыми. Конечно, алгоритм, решение которого пропорционально количеству входных данных в сотой степени, хоть и является полиномиальным, все же не будет считаться быстрым даже при большом воображении! Однако на практике задачи, о которых известно, что они имеют полиномиальное время решения, как правило, решаются за биквадратное (четвертой степени) время или еще быстрее.

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

Вы можете загрузить файлы из облака со скоростью 10 Мбит/с (при условии, что у вас хорошее соединение). Это линейное время — количество времени, которое требуется для извлечения всех потерянных файлов, и оно более или менее прямо пропорционально зависит от размера файлов. Служба резервного копирования также предлагает загрузить файлы на внешний диск и отправить их вам — это действие занимает постоянное время, или O(1), потому что время получения этих данных не зависит от их размера7. Если речь идет о восстановлении всего нескольких мегабайтов, то загрузить их напрямую будет намного быстрее. Но, как только файл достигнет такого размера, что его загрузка будет занимать столько же времени, сколько и отправка, удобнее будет использовать внешний диск.

Если полиномиальные алгоритмы быстрые, то какие же алгоритмы медленные? Для некоторых алгоритмов (называемых экспоненциальными) число операций ограничено не размером входных данных, возведенным в некоторую постоянную степень, а константой, возведенной в степень, равную размеру входных данных.

В качестве примера рассмотрим попытку угадать числовой код доступа длиной n символов. Если это десять цифр от 0 до 9, то количество возможных кодов составляет 10n. Обратите внимание, что это число растет намного быстрее, чем n10: если n равно всего 20, полиномиальный алгоритм работает уже почти в 10 миллионов раз быстрее (рис. 1.3)!

 

Рис. 1.3. Даже при небольшом количестве входных данных различия в асимптотическом времени выполнения быстро становятся заметными

1.6. Всегда ли полиномиальное время лучше?

Как правило, специалисты по Computer Science заинтересованы получить полиномиальное решение задачи, особенно если оно выполняется за квадратичное время или еще быстрее. Однако для задач разумного (небольшого) размера экспоненциальные алгоритмы также могут быть приемлемы.

Зачастую мы можем найти приближенное решение задачи за полиномиальное время, однако получить точный (или близкий к точному) ответ можем лишь за экспоненциальное время. Рассмотрим в качестве примера задачу коммивояжера: продавец хотел бы посетить каждый город на своем маршруте ровно один раз и вернуться домой, преодолев минимальное расстояние. (Представьте себе, сколько денег сэкономили бы службы доставки UPS и FedEx, если бы сделали свои маршруты всего лишь немного более эффективными!)

Чтобы получить точный ответ, нужно вычислить все возможные маршруты и сравнить их суммарные расстояния, то есть O(n!) возможных путей. Очень близкое к оптимальному (в пределах до 1 %) решение может быть найдено за экспоненциальное время8. Но возможное «достаточно хорошее» (в пределах 50 % от оптимального) решение может быть найдено за полиномиальное время9. Это обычный компромисс: мы можем быстро получить достаточно хорошее приближение или медленнее — более точный ответ.

1.7. Время выполнения алгоритма

Рассмотрим следующий код:

foreach (name in NameCollection)

{

    Print "Hello, {name}!";

}

Здесь у нас есть коллекция из n строк; для каждой строки выводится короткое сообщение. Вывод сообщения занимает постоянное время10, то есть O(1). Мы делаем это n раз, то есть O(n). Умножив одно на другое, получим результат: время выполнения кода составляет O(n).

А теперь рассмотрим другую функцию:

DoStuff (numbers)

{

    sum = 0;

    foreach (num in numbers)

    {

        sum += num;

    }

    product = 1;

    foreach (num in numbers)

    {

        product *= num;

    }

    Print "The sum is {sum} and the

           product is {product}";

}

Здесь есть два цикла; каждый из них состоит из O(n) итераций и на каждой итерации выполняет постоянную работу, то есть общее время выполнения каждого цикла составляет O(n). Сложив O(n) и O(n) и отбросив константу, мы снова получим не O(2n), а O(n). Представленную выше функцию также можно написать так:

DoStuff (numbers)

{

    sum = 0 , product = 1;

    foreach (num in numbers)

    {

        sum += num;

        product *= num;

    }

    Print "The sum is {sum} and the

           product is {product}";

}

Теперь у нас есть только один цикл, который снова выполняет постоянную работу; просто у него константа больше, чем раньше. Помните, что нас интересует, насколько быстро растет время выполнения задачи при увеличении ее размера, а не точное число операций для данного размера задачи.

Теперь попробуем что-нибудь более сложное. Каково время выполнения этого алгоритма?

CountInventory (stuffToSell, colorList)

{

    totalItems = 0;

    foreach (thing in stuffToSell)

    {

        foreach (color in colorList)

        {

            totalItems += thing[color];

        }

    }

}

Здесь у нас есть два цикла, причем один вложен в другой. Поэтому мы будем умножать их время выполнения, а не складывать. Внешний цикл запускается один раз для каждого элемента каталога, а внутренний — один раз для каждого предоставленного цвета. Для n элементов и m цветов общее время выполнения равно O(nm). Обратите внимание, что это неO(n2); у нас нет оснований полагать, что между n и m существует взаимосвязь.

Рассмотрим еще одну функцию:

doesStartWith47 (numbers)

{

    return (numbers[0] == 47);

}

Эта функция проверяет, равен ли 47 первый элемент целочисленного массива, и возвращает результат. Объем работы, который выполняет функция, не зависит от количества входных данных и поэтому равен O(1)11.

Мы часто пишем программы, которые включают в себя двоичный поиск, следовательно, в нашем анализе будут логарифмы.

Например, рассмотрим следующий код12:

binarySearch (numarray, left, right, x)

{

    if (left > right) { return -1; }

    int mid = 1 + (right - 1)/2;

    if (numarray[mid] == x) { return mid; }

    if (numarray[mid] > x)

        { return binarySearch (numarray, left,

          mid -1, x); }

    return binarySearch (numarray, mid + 1, right, x);

}

Исходя из предположения, что массив отсортирован, мы проверяем, является ли средний элемент массива тем, что мы ищем. Если это так, то возвращаем индекс среднего элемента. Если же нет и средний элемент больше требуемого значения, то мы проделываем то же самое с первой половиной массива, а если больше — то со второй половиной. Для каждого рекурсивного вызова выполняется постоянный объем работы (проверка, что значение left не больше, чем right; это подразумевает, что мы выполнили поиск по всему массиву и искомое значение не было найдено; затем вычисление средней точки и сравнение ее значения с тем, что мы ищем). Мы выполняем O(lg n) вызовов, каждый из которых занимает O(1) времени, поэтому общая сложность двоичного поиска составляет O(lg n).

Углубленные темы Представьте, что у нас есть рекурсивная функция, которая разбивает задачу на две части, размер каждой из них составляет 2/3 от размера оригинала? Формула для вычисления такой рекурсии действительно существует; подробнее о ней и об основной теореме (Master Theorem) вы узнаете в главе 31.

1.8. Насколько сложна задача?

Если есть алгоритм для решения задачи, определить время выполнения этого алгоритма обычно довольно просто. Но что, если у нас еще нет алгоритма, но уже нужно понять, насколько сложно будет решить задачу?

Мы можем это сделать, сравнивая задачу с другими подобными задачами, для которых известно время выполнения. Мы можем разделить задачи на классы — наборы задач, имеющих сходные характеристики. Нас интересуют два основных класса: задачи, которые решаются за полиномиальное время, и задачи, решение которых можно проверить за полиномиальное время. Оба этих класса мы рассмотрим в следующей главе.

2. Структуры данных

2.1. Организация данных

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

• Необходим ли произвольный доступ, или достаточно последовательного?

• Будут ли данные при записи всегда добавляться в конец списка, или нужна возможность вставлять значения в середину?

• Допускаются ли повторяющиеся значения?

• Что важнее: наименьшее возможное время доступа или строгая верхняя граница времени выполнения каждой операции?

Ответы на все эти вопросы определяют то, как должны храниться данные.

2.2. Массивы, очереди и другие способы построиться

Возможно, самая известная структура данных — это массив, набор элементов, проиндексированных ключом. Элементы массива хранятся последовательно, причем ключ имеет форму смещения относительно начальной позиции в памяти, благодаря чему можно вычислить положение любого элемента по его ключу. Именно по­этому индексы массива13 обычно начинаются с нуля; первый элемент массива находится на нулевом расстоянии от начала, следующий — на расстоянии одного элемента от начала и т.д. «На расстоянии одного элемента» может означать один байт, одно слово и т.д., в зависимости от размера данных. Важно, что каждый элемент массива занимает одинаковое количество памяти.

Польза массивов состоит в том, что получение или сохранение любого элемента массива занимает постоянное время, а весь массив занимает O(n) места в памяти14. Если количество элементов заранее известно, то память не расходуется зря; поскольку позиция каждого элемента вычисляется просто по смещению относительно начала, нам не нужно выделять место для указателей. Поскольку элементы массива расположены в смежных областях памяти, перебор значений массива, очевидно, выполняется гораздо быстрее, чем для многих других структур данных из-за меньшего количества неудачных обращений к кэш-памяти15.

Однако требование выделения непрерывного блока памяти может сделать массивы плохим выбором, когда число элементов заранее не известно. С ростом размера массива может понадобиться скопировать его в другое место памяти (при условии, что оно есть). Избежать этой проблемы, предварительно выделив гораздо больше места, чем необходимо, бывает довольно затратно16. Другая проблема — вставка и удаление элементов массива занимает много времени (O(n)), поскольку приходится перемещать все элементы массива.

На практике массивы используются как сами по себе, так и для реализации многих других структур данных, которые накладывают дополнительные ограничения на манипулирование данными. Например, строка может быть реализована в виде массива символов. Очередь — это последовательный список, в котором элементы добавляются только в один конец списка (постановка в очередь), а удаляются из другого (извлечение из очереди); таким образом, очередь может быть реализована как массив, в котором «начало» перемещается вместе с началом очереди при условии, что максимальное количество элементов в очереди никогда не превышает размер массива. Однако очередь неопределенной длины лучше реа­лизовать на основе двусвязного списка (см. раздел 2.3). К другим структурам, реализуемым на основе массивов, относятся списки, стеки и кучи (см. раздел 2.4), очереди с приоритетом (которые часто создаются на основе куч) и хеш-таблицы (см. раздел 2.5).

2.3. Связные списки

Связный список — это структура данных, в которой каждый элемент содержит данные и указатель на следующий элемент списка (а если это двусвязный список, то также ссылку на предыдущий элемент). Указатель на связный список — это просто указатель на первый элемент, или head, списка; поскольку элементы могут размещаться в разных местах выделенной памяти, для поиска указанного элемента необходимо начать с первого элемента и пройтись по всему списку.

Как уже говорилось, многие структуры данных реализованы на основе массивов или связных списков. Во многом связный список является дополнением массива. Если сильная сторона массива — быстрый доступ к любому элементу (по его ключу), то для того, чтобы найти элемент списка, необходимо пройти по всем ссылкам, пока не будет найден нужный элемент, что в худшем случае займет O(n) времени. С другой стороны, массив имеет фиксированный размер, а элементы связного списка могут размещаться в любом месте памяти, и список может произвольно увеличиваться до тех пор, пока не будет исчерпана доступная память. Кроме того, вставка и удаление элементов массива очень затратны, а в связном списке эти операции выполняются за постоянное время, если есть указатель на предыдущий узел (рис. 2.1).

 

Рис. 2.1. Удаление узла из связного списка

Практическое применение

Представьте себе поезд как пример двусвязного списка: каждый вагон связан с предыдущим и (если он существует) со следу­ющим. В конец поезда можно легко добавить вагоны, но можно вставить вагон и в середину поезда, отсоединив и (пере)присоединив существующие вагоны перед и после добавляемых, или же можно отсоединить вагоны в середине поезда, откатить их на боковой путь и присоединить оставшиеся вагоны. А вот извлечь вагон напрямую не получится; для этого нужно сначала пройти по всему поезду и отделить нужный вагон от предыдущего.

Теоретическая глупость

Как-то мой преподаватель спросил у группы студентов, как определить, содержит ли связный список цикл. Есть несколько классических решений этой задачи. Один из способов — обратить указатели на элементы списка, когда мы их проходим; если цикл существует, то мы в итоге вернемся к началу списка. Другой способ: обходить список с двумя указателями, так что один указатель ссылается на следующий элемент, а второй — через один элемент. Если в списке существует цикл, то в итоге оба указателя когда-нибудь будут ссылаться на один и тот же элемент.

Однако преподаватель добавил условие: он сказал, что ему все равно, сколько времени займет выполнение нашего метода. Я предложил несколько глупый вариант: вычислить объем памяти, необходимый для хранения одного узла списка, и разделить на него общую память системы. Потом вычислить количество посещенных элементов. Если число посещенных элементов превышает количество узлов, которые могут быть сохранены в памяти, список должен содержать цикл.

Преимущество этого решения неоднозначно: оно требует безумно много времени (определяемого размером памяти, а не списка) и является абсолютно правильным.

2.4. Стеки и кучи

2.4.1. Стеки

Стек — это структура данных типа LIFO (Last In, First Out — «последним пришел, первым ушел»), в которой элементы добавляются или удаляются только сверху; это называется «поместить элемент в стек» (push) или «извлечь его из стека» (pop) (рис. 2.2).

Стек можно реализовать на основе массива (отслеживая текущую длину стека) или на основе односвязного списка (отслеживая head списка17). Как и в случае с очередями, реализация на основе массива проще, но она накладывает ограничение на размер стека. Стек, реализованный на основе связного списка, может расти до тех пор, пока хватает памяти.

 

Рис. 2.2. Элементы всегда помещаются в вершину стека

Стеки поддерживают четыре основные операции, каждая из которых может быть выполнена за время O(1): push (поместить элемент в стек), pop (извлечь элемент из стека), isEmpty (проверить, пуст ли стек) и size (получить количество элементов в стеке). Часто также реализуют операцию peek (просмотреть верхний элемент стека, но не удалять его), что эквивалентно извлечению верхнего элемента и его повторному помещению в стек.

При помещении элемента в стек может возникнуть исключение, если размер стека ограничен, и в настоящее время стек заполнен (ошибка переполнения), а при извлечении элемента из стека возникает исключение, если в данный момент стек пуст (ошибка обнуления).

Несмотря на то что в стеках не допускается произвольный доступ, они очень полезны в тех компьютерных вычислениях, для которых требуется ведение истории, от операций Undo до рекурсивных вызовов функций. В этом случае стек обеспечивает возможность обратного перебора, если необходимо вернуться к предыдущему состоянию. В разделе 13.3 вы увидите, как стеки используются для реализации магазинных автоматов, способных распознавать контекстно свободные языки.

Типичным примером использования стека является проверка сбалансированности фигурных скобок. Рассмотрим язык, в котором скобки должны быть парными: каждой правой скобке (}) предшествует соответствующая левая скобка ({). Мы можем прочитать строку и каждый раз, когда встречается левая скобка, помещать ее в стек. Все­гда, когда встречается правая скобка, мы будем извлекать левую скобку из стека. Если попытаться извлечь фигурную скобку из стека, но стек окажется пустым, это будет означать, что у правой фигурной скобки нет соответствующей левой скобки. Если в конце строки стек окажется непустым, это будет означать, что считано больше левых скобок, чем правых. В противном случае все скобки в строке окажутся парными.

2.4.2. Кучи

Кучи, подобно стекам, как правило, реализуются на основе массивов. Как и в стеке, в куче можно удалить за один раз только один элемент. Однако это будет не последний добавленный, а наибольший (для max-кучи) или наименьший элемент (для min-кучи). Куча частично упорядочена по ключам элементов, так что элемент с наивысшим (или низшим) приоритетом все­гда хранится в корне кучи (рис. 2.3).

 

Рис. 2.3. Узлы-братья (узлы с одним и тем же родителем) в куче никак не взаимосвязаны; просто каждый узел имеет более низкий приоритет, чем его родитель

Словом «куча» называют структуру данных, которая удовлетворяет свойству упорядоченности кучи: неубывания (min-куча) (значение каждого узла не меньше, чем у его родителя) либо невозрастания (max-куча) (значение каждого узла не больше, чем у родителя). Если не указано иное, то, говоря о куче, мы имеем в виду двоичную кучу, которая является полным двоичным деревом18, которое удовлетворяет свойству упорядоченности кучи; в число других полезных видов кучи входят левосторонние кучи, биномиальные кучи и кучи Фибоначчи.

Max-куча поддерживает операции поиска максимального значения (find-max) (peek), вставки (insert) (push), извлечения максимального значения (extract-max) (pop) и увеличения ключа (increase-key) (изменения ключа узла с последующим перемещением узла на новое место на графе). Для двоичной кучи после создания кучи из списка элементов за время O(n) каждая из этих операций занимает время O(lg n)19.

Кучи используются в тех случаях, когда нужен быстрый доступ к наибольшему (или наименьшему) элементу списка без необходимости сортировки остальной части списка. Именно поэтому кучи используются для реализации очередей с прио­ритетом: нас интересует не относительный порядок всех элементов, а только то, какой элемент является следующим в очереди, — это всегда текущий корень кучи. Более подробно кучи рассмотрены в разделах 5.3 и 8.3.

2.5. Хеш-таблицы

Предположим, мы хотим определить, содержится ли в массиве некий элемент. Если массив отсортирован, можно выполнить двоичный поиск и найти этот элемент за время O(lg n); если же нет, можно перебрать весь массив за время O(n). Конечно, если бы мы знали, где находится этот элемент, то мы бы просто обратились туда напрямую за время O(1).

В некоторых случаях, таких как сортировка подсчетом (см. подраздел 8.4.1), в качестве индекса массива используется сам сохраняемый элемент или его ключ, и поэтому можно просто перейти в нужное место без поиска. А что, если бы для произвольного объекта у нас была функция, которая бы принимала ключ этого объекта и преобразовывала его в индекс массива, так что мы бы точно знали, где находится объект? Именно так работают хеш-таблицы.

Первая часть хеш-таблицы — это хеш-функция; она преобразует ключ элемента, который помещается в хеш. Этому ключу соответствует определенное место в таблице. Например, наши ключи представляют собой набор строк, а хеш-функция ставит в соответствие каждой строке количество символов этой строки20. Тогда слово cat попадет в ячейку 3, а penguin — в ячейку 7. Если место ограничено, то мы делим хеш-код по модулю на размер массива; тогда, если массив ограничен десятью ячейками (0–9), строка sesquipedalophobia (хеш-код которой равен 18) попадет в ячейку 721, 22.

Что произойдет, если мы уже поместили в хеш-таблицу слово cat, но попытаемся вставить туда слово cat еще раз? В хеш-таблицах допускается хранить только один экземпляр каждого элемента; в некоторых реализациях в каждой ячейке хранится счетчик, который увеличивается по мере необходимости, чтобы отслеживать количество копий элемента. Но что, если мы попытаемся вставить слово dog, которое попадет в ту же ячейку? Есть два способа решить эту проблему. Можно рассматривать каждую ячейку как группу объектов, представленных в виде связного списка (который нужно пройти, чтобы найти правильное животное); это называется методом цепочек. Или же можно просмотреть близлежащие ячейки, найти свободную и поместить dog туда — это называется открытой адресацией. Размер хеш-таблицы с цепочками не ограничен, однако производительность будет снижаться по мере увеличения количества элементов в ячейке. При открытой адресации таблица имеет фиксированный максимальный размер; как только все ячейки будут заполнены, в таблицу нельзя будет вставить новые элементы.

Способ организации хеш-таблицы зависит от того, предпочитаем ли мы свести к минимуму коллизии (несколько значений, которые попали в одну ячейку) или объем памяти. Чем больше места выделено под таблицу относительно количества вставляемых элемен­тов, тем меньше вероятность коллизий. За счет увеличения памяти мы получаем повышение скорости: после того как ключ захеширован, сохранение или извлечение элемента (при условии отсутствия коллизий) занимает O(1) времени. Однако при коллизиях наихудшее время извлечения в хеш-таблице (когда для каждого элемента возникает коллизия) составляет O(n).

Практическое применение

В C# есть класс Hashtable, позволяющий хранить произвольные объекты. Каждый объект, добавляемый в Hash­table, должен реализовывать функцию GetHashCode(),  она возвращает значение int32, которое можно использовать для хеширования объекта. Dictionary<TKey,TValue> предоставляет тот же функционал, но только для объектов типа TValue, который (при условии, что TValue не установлен в Object) позволяет программисту избегать упаковки и распаковки сохраненных элементов. Для внутреннего представления в обоих случаях используется структура данных хеш-таблицы, но с разными методами предотвращения коллизий. В Hashtable применяется перехеширование (поиск другой ячейки, если первая занята), а в Dictionary — метод цепочек (несколько элементов с одинаковым хешем просто добавляются в одну ячейку)

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

2.6. Множества и частично упорядоченные множества

Множество — это неупорядоченная коллекция уникальных предметов. Существует три основные операции над множествами, каждая из которых принимает два множества в качестве аргументов и возвращает еще одно множество в качестве результата.

Uni­on(A, B) — объединение мно­жеств — это множество, со­­де­ржащее каждый элемент, ко­то­рый принадлежит хотя бы од­ному из множеств A и B. Обы­чно объединение обозначается как A∪B (рис. 2.4).

 

Рис. 2.4. Объединение множеств A и B

Inter­sec­tion(A, B) — пересечение множеств — это множество элементов, содержащихся как в A, так и в B, обозначается как A∩B (рис. 2.5).

 

Рис. 2.5. Пересечение множеств A и B

Differen­ce(A, B) — разность множеств (рис. 2.6) — обозначается как A – B — это множество, в которое входят все элементы, содержащиеся в A, но отсутствующие в B.

 

Рис. 2.6. Разность множеств A и B (A – B)

Наконец, есть еще одна операция, которая возвращает логическое ­значение: подмножество Subset(A, B). Ее результатом будет истина (true), если A является подмножеством B (то есть каждый элемент множества A — элемент множества B). Если A является подмножеством B и не равно B, то такое подмножество называется собственным. Мы используем обозначения A⊆B (A является подмножеством B), A⊆/ B (A не является подмножеством B), A⊂B (A является собственным подмножеством B) и A⊂/ B (A не является собственным подмножеством B). Если A⊆B и B⊆A, то A = B. Существуют также дополнительные операции, которые применяются к множествам строк; они рассмотрены в подразделе 13.2.2.

Существует несколько видов мно­жеств (рис. 2.7). Мульти­множество — это множество, в котором допускается дублирование элементов, то есть хранятся несколько копий одного и того же значения либо просто ведется подсчет того, сколько раз данное значение присутствует в множестве.

 

Рис. 2.7. Множество целых чисел

Частично упорядоченное множество — множество, в котором некоторые элементы расположены в определенном порядке. Это означает, что для некоторой двоичной операции23 ≤ между элементами b и c может быть истиной b ≤ c, в других — c ≤ b или же между b и c может не существовать отношений.

Если все элементы множества связаны операцией ≤, то есть для любых двух элементов f и g множества либо f ≤ g, либо g ≤ f, то операция ≤ определяет полный порядок множества. Например, стандартная операция «меньше или равно» — это порядок для множества действительных чисел: любые два числа либо равны, либо одно больше другого.

Необходимо, чтобы отношение было рефлексивным (каждый элемент множества меньше или равен самому себе), антисимметричным (если b меньше или равно c, то c не может быть меньше или равно b, если только b не равно c) и транзитивным (если b меньше или равно c, а c меньше или равно d, то b меньше или равно d).

Практический пример

Пусть ≤ означает отношение «является потомком», причем по определению каждый человек является потомком самого себя. Тогда такое отношение является антисимметричным (если я твой потомок, то ты не можешь быть моим потомком) и транзитивным (если я твой потомок, а ты потомок дедушки, то я тоже потомок дедушки). Это частичное, а не полное упорядочение, поскольку, возможно, ни я не являюсь твоим потомком, ни ты — моим.

Обратите внимание, что ку­ча — частично упорядоченное мультимножество (рис. 2.8): в ней может существовать несколько копий одного и того же значения и каждое значение имеет определенную связь только со своим родителем и потомками.

 

Рис. 2.8. Мультимножество целых чисел

Практическое применение

Реляционные базы данных24 содержат таблицы, в которых хранятся наборы строк. Упорядоченность может быть задана при выводе данных (в SQL это делается с помощью оператора ORDER BY), но такое ограничение не накладывается на фактически сохраненные данные, поэтому нельзя считать, что строки в базе данных хранятся в каком-либо определенном порядке.

2.7. Специализированные структуры данных

Далее в книге мы рассмотрим более специализированные структуры данных. В главе 5 описаны некоторые распространенные графовые структуры данных. В главе 32 представлена концепция амортизированного времени выполнения (общего времени, затрачиваемого на серию операций, а не времени выполнения отдельной операции), а в главе 33 описана структура данных, которую мы проанализируем с использованием амортизированного времени выполнения.

3. Классы задач

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

Самые простые задачи, класса P, могут быть решены за полиномиальное время. Это все задачи, у которых время решения — количество входных данных, возведенное в некоторую постоянную степень. Принято считать, что такие задачи имеют эффективные решения. К этому классу относятся многие широко известные задачи, например такие, как сор­тировка списков. Задачи класса P также называют легкоразрешимыми. Как правило, если можно доказать, что задача относится к классу P, значит, ее можно решить за разумное время.

Класс P является собственным подмножеством множества задач EXP, которые решаются за экспоненциальное время; любая задача, которая может быть решена за время O(n2), также может быть решена за время O(2n).

Математическое предупреждение: возвращаясь к главе 2 Для двух множеств A и B множество A является подмножеством B, а B — надмножеством A, если каждый элемент множества A также является элементом множества B. Это обозначается так: A ⊆ B и B ⊇ A. Если множество B содержит все элементы множества A, а также что-то еще, то B является собственным надмножеством множества A, а A — собственным подмножеством B. Это обозначается так: A ⊂ B и B ⊃ A. Например, множество {1, 2, 3} является собственным подмножеством множества {1, 2, 3, 4, 5}.

Но в множество EXP входят и другие классы, кроме P. Один из них — это недетерминированный полином (Non­de­terministic Polynomial, NP). Задача относится к классу NP, если она может быть решена недетерминированно25 за полиномиальное время. Другими словами, существует алгоритм, который решает эту задачу путем принятия ряда решений, причем в каждой точке принятия решения алгоритм случайным образом (и удачно) делает правильный выбор. Пока остается ряд шагов, ведущих к ответу, алгоритм выбирает правильные шаги. Другой (более полезный) способ показать, что задача относится к классу NP, — убедиться, что ее решение можно проверить (детерминированно, то есть следуя предварительно определенной последовательности шагов) за полиномиальное время. NP является надмножеством P; любое решение, которое может быть найдено за полиномиальное время, также может быть проверено за полиномиальное время.

Один из важнейших вопросов Computer Science, на который до сих пор не получен ответ: является ли NP собственным надмножеством P? Существуют ли задачи, которые относятся к NP, но не принадлежат P, или это одно и то же множество задач? Другими словами: любая ли задача, решение которой быстро проверяется компьютером, также быстро решается компьютером? Большинство специалистов в области Computer Science считают, что P ≠ NP, но никаких математических доказательств найдено не было26 (рис. 3.1).

 

Рис. 3.1. Проблема P = NP: это одно и то же множество (слева) или же P является собственным подмножеством NP(справа)?

Рассмотрим задачу разбиения множества чисел (рис. 3.2). Для заданного мультимножества (множества, в котором могут присутствовать повторяющиеся элементы) натуральных чисел нужно определить, можно ли разбить такое множество на два подмножества таким образом, чтобы сумма чисел в первом множестве равнялась сумме чисел во втором. Если мультимножество разделено на два подмножества {S1, S2}, то задача решается тривиально: нужно сложить значения в каждом множестве и определить, идентичны ли эти две суммы. Но выяснить, какие значения следует поместить в каждое из множеств, за поли­номиальное время невозможно (при условии, что P ≠ NP).

 

Рис. 3.2. Простой пример задачи разбиения множества чисел. Мультимножество {1, 1, 2, 3, 4, 5, 6} можно разделить на мультимножества {1, 1, 2, 3, 4} и {5, 6}. Сумма элементов каждого из них равна 11

Некоторые задачи класса NP называются NP-сложными; NP-сложная задача (несколько рекурсивно) определяется как любая задача, которая по крайней мере столь же сложна, как и самая сложная задача класса NP. Чтобы понять, что это значит, рассмотрим принцип сокращения.

Углубляясь в подробности Выше мы говорили о том, что задача разбиения не может быть решена за полиномиальное время при условии, что P ≠ NP. Это верно только в том случае, если обратить внимание на важное различие между значением и размером входных данных. Сложность задачи часто зависит от того, как входные данные закодированы. С технической точки зрения задача относится к классу P, если ее можно решить с помощью алгоритма, который выполняется за полиномиальное время, в зависимости от длины входных данных, то есть от числа битов, необходимых для представления входных данных. Алгоритм выполняется за псевдополиномиальное время, если он является полиномиальным, в зависимости от числового значения входных данных, длина которых изменяется экспоненциально. Рассмотрим задачу с количеством входных данных 1 миллиард и алгоритмом, который требует n операций. Если n — это количество цифр, необходимое для представления числа (в данном случае 10, при условии, что основанием системы счисления является 10), то алгоритм является полиномиальным. Если n — значение входных данных (1 000 000 000), то алгоритм будет псевдополиномиальным. В последнем случае количество требуемых операций растет намного быстрее, чем количество битов входных данных.

Задача B может быть сокращена до задачи C, если решение задачи C позволило бы решить задачу B за полиномиальное время. Другими словами, если у нас есть оракул, который дает ответ на задачу C, то мы можем (за полиномиальное время) преобразовать его в ответ на задачу B. Решение задачи является NP-сложным, если любая задача класса NP может быть сведена к этому решению, то есть эффективное решение задачи также приведет к эффективному решению любой задачи класса NP.

Обратите внимание, что сама NP-сложная задача не обязательно должна принадлежать к классу NP; она должна быть как минимум такой же сложной, как все задачи класса NP. Это означает, что некоторые NP-сложные задачи (не принадлежащие классу NP) могут быть намного сложнее, чем другие задачи, которые принадлежат к классу NP.

Задача, которая и является NP-сложной, и относится к классу NP, называется NP-полной. Поскольку каждая NP-полная задача может быть сокращена до любой другой NP-полной задачи, сокращение NP-полной задачи к новой задаче и демонстрация того, что новая задача принадлежит к классу NP, достаточны, чтобы доказать, что данная задача является NP-полной.

Углубляясь в подробности Если NP-полная задача имеет псевдополиномиальное решение, она называется слабо NP-полной. Если же это не так (или P = NP), то задача называется сильно NP-полной.

Для того чтобы ответить на вопрос, действительно ли P = NP, нужно либо предоставить алгоритм, который бы решал NP-полную задачу за (детерминированное) полиномиальное время (в этом случае P = NP), либо доказать, что такого алгоритма не существует (в таком случае P ≠ NP).

Углубленные темы: NP-полное сокращение

Предположим, что у нас есть следующие задачи.

Сумма подмножества. Для заданного мультимножества S целых чисел и значения w определить, существует ли непустое подмножество множества S, сумма элементов которого равна w?

Разделение. Можно ли разделить мультимножество S целых чисел на два подмножества — S1 и S2, суммы элементов которых равны?

Поскольку сумма подмножества — NP-полная задача, можно доказать, что разбиение также является NP-полной задачей, следующим образом.

Первый шаг — показать, что задача разбиения относится к классу NP. Для данных подмножеств S1 и S2 можно найти сумму элементов каждого множества и сравнить их за время, пропорциональное общему количеству значений. Поскольку решение может быть проверено за линейное (полиномиальное) время, задача принадлежит к классу NP.

Второй шаг — показать, что разбиение является NP-сложным. Для этого мы покажем, что решение новой задачи за полиномиальное время также даст решение за полиномиальное время задачи, которая, как изестно, является NP-сложной, поэтому разбиение — столь же сложная задача, как и эта задача.

Допустим, что у нас есть алгоритм, который решает за полиномиальное время и задачу разбиения, и задачу суммы подмножества, которую мы хотели бы решить. Есть множество S, и мы хотим знать, существует ли у него подмножество, сумма элементов которого равна w. Это эквивалентно вопросу, можно ли разбить множество S с суммой |S| на мультимножество S1 с суммой w1 и мультимножество S2 с суммой w2 = |S| – w.

Пусть x — разность между w1 и w2. Добавим это число в множество S, а затем выполним алгоритм разбиения для нового множества. Если задача разрешима, то алгоритм вернет два разбиения с одинаковой суммой, которая равна половине от |S| + x. Вследствие того, как мы выбрали значение x, удаление этого элемента теперь дает множества S1 и S2, одно из которых является решением исходной задачи суммы подмножества. Поскольку дополнительная работа заняла линейное время, решение задачи суммы подмножества заняло полиномиальное время.

Пример:

S = {5, 10, 10, 30, 45}, w = 25

|S| = 100, w2 =100 – 25 = 75, x = 75 – 25 = 50

Sa = {5, 10, 10, 30, 45, 50}

S1 = {5, 10, 10, 50}

S2 = {30, 45}

Решение: {5, 10, 10}

Этот пример показывает, что задача разбиения является NP-полной, а ее решение за полиномиальное время было бы доказательством того, что P = NP.

Существует еще несколько классов сложности, но те два, которые мы обсудили в этом разделе, наиболее известны. Другие классы, как правило, определяются в терминах машин Тьюринга, которые мы рассмотрим позже в этой книге.

Дополнительные источники информации Некоторые наиболее известные NP-полные задачи рассмотрены в приложении Б. Более подробную информацию о классах задач вы найдете в главах 13 и 14.

Часть II. Графы и графовые алгоритмы

4. Введение в теорию графов

4.1. Семь кенигсбергских мостов

Я считаю, что введение в теорию графов обязательно должно начинаться с задачи о кенигсбергских мостах. Эта задача важна не сама по себе, а потому, что с нее начался новый раздел математики — теория графов.

В городе Кенигсберге (ныне Калининград) протекает река. Она делит город на четыре части, которые соединяются семью мостами (рис. 4.1). Вопрос: можно ли прогуляться по городу, проходя каждый мост ровно один раз?

Однажды этот вопрос задали математику Леонарду Эйлеру. Он объявил задачу тривиальной, но она все же привлекла его внимание, поскольку ни одна из существующих областей математики не была достаточной для ее решения. Главным заключением является то, что топологические деформации неважны для решения; другими словами, изменение размера и формы различных деталей не меняет задачу при условии, что не меняются соединения27.

 

Рис. 4.1. Находящаяся в открытом доступе карта Кенигсберга. Merian-Erben, 1652

Таким образом, мы можем упростить карту, изображенную на рис. 4.1, заменив каждую часть города вершиной, а каждый мост — ребром, соединяющим две вершины. В результате получим граф, показанный на рис. 4.2.

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

 

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

4.2. Мотивация

Графы в Computer Science чрезвычайно важны: очень многие задачи можно представить в виде графов. В случае с кенигсбергскими мостами представление города в виде графа позволяет игнорировать неважные детали — фактическую географию города — и сосредоточиться на важном — на связях между различными частями города. Во многих случаях возможность свести постановку задачи к эквивалентной задаче для определенного класса графов дает полезную информацию о том, насколько сложно ее решить. Некоторые задачи являются NP-сложными на произвольных графах, но имеют эффективные (часто O(n)) решения на графах, имеющих определенные свойства.

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

Определение Класс графов — это (как правило, бесконечный) набор графов, который обладает определенным свойством; принадлежность данного графа к этому классу зависит от того, есть ли у этого графа это свойство.

Пример Двудольные графы — это такие графы, в которых вершины можно разделить на два множества, так что каждое ребро соединяет вершину из одного множества с вершиной из другого множества.

4.3. Терминология

Граф — это способ представления взаимосвязей в множестве данных. Графы часто изображаются в виде кружков, которыми обозначаются вершины, и линий между ними, представляющих ребра. Но вы узнаете и о других способах представления графов. Две вершины являются смежными, если между ними есть ребро, и несмежными, если между ними нет ребра.

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

4.3.1. Части графов

Я буду часто ссылаться на подграф или порожденный подграф графа. Подграфом графа является любое количество вершин графа вместе с любым количеством ребер (которые также принадлежат исходному графу) между этими вершинами. Порожденный подграф — это любое подмножество вершин вместе со всеми ребрами графа, соединяющими эти вершины.

Строгое подмножество множества содержит меньше элементов, чем исходное множество; другими словами, собственное подмножество вершин графа содержит меньше вершин, чем исходный граф, в то время как регулярное подмножество может содержать все множество вершин.

4.3.2. Графы со всеми ребрами или без ребер

Полный (под)граф, или клика, — это такой граф, который содержит все возможные ребра между его вершинами. Независимое (или внутренне устойчивое) множество — это множество вершин без ребер между ними. На рис. 4.3 показан граф K8; в теории графов буква K с целочисленным индексом означает полный граф с соответствующим количеством вершин.

 

Рис. 4.3.K8 — полный граф из восьми вершин

Граф или подграф, в котором существует путь от любой вершины к любой другой вершине, называется связным; граф, который не является связным, состоит из нескольких компонент связности29.

Для данного графа G его дополнение G' также является графом с теми же вершинами; для любой пары вершин G' ребро между ними существует тогда и только тогда, когда такого ребра нет в графе G. На рис. 4.4 показан граф, который является дополнением к графу K6; вместо того чтобы содержать все возможные ребра, он не имеет ни одного ребра.

 

Рис. 4.4. Разъединенный граф с шестью компонентами связности размером 1

Математическое предупреждение

Символ штриха (') используется в математике для представления объекта, который был получен из другого объекта. Здесь я использую этот символ для обозначения графа G', который мы получаем из G, удаляя из него все ребра и добавляя ребра там, где их раньше не было. Это похоже на использование данного символа в теории множеств для обозначения дополнения множества.

При обсуждении языков в главе 13 используется альтернативная нотация — обозначение дополнения языка А как А-. Эта нотация (также широко распространенная) облегчает работу с дополнениями дополнений.

4.3.3. Петли и мультиграфы

Обычно мы работаем с простыми графами, то есть с графами, которые не содержат петель (ребро, которое заканчивается в той же вершине, в которой началось) или кратных ребер (несколько ребер, соединяющих одни и те же вершины). Говоря «граф» и не указывая иное, мы всегда имеем в виду простой граф. Граф с петлями можно назвать непростым графом, а граф с кратными ребрами — мультиграфом. Далее в книге, встретив слово «граф», считайте, что оно означает простой неориентированный граф30, если не указано иное.

4.4. Представление графов

Когда мы говорим о размере графа, то обычно используем обозначение n для числа вершин и m — для числа ребер31. На рис. 4.3 n = 8 и m = 28, на рис. 4.4 — n = 6 и m = 0. Количество места в памяти, необходимое для хранения графа, зависит от того, как именно мы его храним; как правило, графы хранятся в виде списков смежности и матриц смежности.

4.4.1. Представление графов в виде списков смежности

При использовании представления в виде списка смежности каждая вершина графа сохраняется вместе со списком смежных с ней вершин (рис. 4.5, 4.6). Если реализовать это в виде множества связных списков, то объем занимаемого пространства составит O(n + m)32. В случае разреженного графа (с очень небольшим числом ребер) этот объем сократится до O(n). Для плотного графа (графа с большим количеством ребер, такого как полный или почти полный граф) этот объем составит O(n2).

Рис. 4.5. Представление списка смежности графа, показанного на рис. 4.3		Рис. 4.6. Представление списка смежности графа, показанного на рис. 4.4

4.4.2. Представление графов в виде матрицы смежности

Еще одним популярным способом хранения графа является матрица смежности (рис. 4.7, 4.8), которая представляет собой матрицу со следующими свойствами:

• каждая ячейка матрицы равна либо 0, либо 1;

• ячейка в позиции (i, j) равна 1 тогда и только тогда, когда существует ребро между вершинами i и j. Это верно и для ячейки в положении (j, i);

• из предыдущего пункта следует, что число единиц в матрице равно удвоенному числу ребер в графе;

• диагональные ячейки всегда равны нулю, потому что ни у одной вершины нет ребра, которое и начинается, и заканчивается в ней33;

Рис. 4.7. Представление матрицы смежности графа, показанного на рис. 4.3		Рис. 4.8. Представление матрицы смежности графа, показанного на рис. 4.4

• матрица состоит из n строк и n столбцов и поэтому занимает n2 места. Для плотного графа линейная зависимость от размера матрицы сохраняется34.

В мультиграфе, где присутствуют петли, некоторые из этих условий не выполняются. В частности, значения могут быть больше 1 (потому что между двумя вершинами может существовать несколько ребер) и диагональ может быть ненулевой (петли могут соединять вершину с самой собой).

4.4.3. Представление графов в памяти

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

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

Выбор представления графа зависит от плотности графа и от того, как вы планируете его использовать. Для разреженного графа список смежности намного эффективнее по объему памяти, чем матрица смежности, поскольку нам не нужно хранить O(n2) нулей и можно легко перебрать все существующие ребра. Кроме того, в случае динамического графа (который изменяется со временем) в списке смежности проще добавлять и удалять вершины.

С другой стороны, в матрице смежности более эффективно организован доступ к ребрам. Чтобы определить, являются ли вершины i и j смежными, достаточно проверить, равно ли A[i] [j] единице. Не нужно сканировать весь список, что может занять до O(n) времени. Таким образом, в матрице смежности поиск выполняется не только быстрее, но и занимает постоянное количество времени, что делает матрицы смежности лучшими для приложений, где необходима предсказуемость35.

4.5. Направленные и ненаправленные графы

В задаче о кенигсбергских мостах все ребра графа были ненаправленными; если по мосту можно идти в одном направлении, то можно идти и в обратном. Графы, для которых это верно, называются ненаправленными или просто графами и описывают ситуации, в которых если (вершина) A связана с B, то B также связана с A. Например, если Алиса — двоюродная сестра Веры, то Вера также является двоюродной сестрой Алисы.

В ориентированном графе, или орграфе, каждое ребро имеет направление, в котором следует данная связь. Если Алиса любит проводить время с Верой и мы обозначаем это стрелкой из A в B, это еще не говорит о том, что Вера тоже любит проводить время с Алисой. Если это так, то также существует стрелка из B в A. Орграф является симметричным, когда для каждого ориентированного ребра в нем существует ребро, соединяющее те же две вершины, но направленное в противоположную сторону. Такой граф эквивалентен ненаправленному графу с одним ребром между каждой парой вершин, где есть пара направленных ребер, поэтому обычные графы можно рассматривать как особый случай орграфов.

И наоборот, возможна ситуация, при которой между любыми двумя вершинами может существовать только одно ориентированное ребро; такой граф называется направленным или антисимметричным. Например, если Алиса является родителем Влада, то Влад не может быть родителем Алисы (по крайней мере никаким социально приемлемым способом). Если взять ненаправленный граф и задать направление каждому из ребер (превратить ребро в ориентированное), получим направленный граф.

4.6. Циклические и ациклические графы

Один из способов классификации графов — разделить их на циклические или ациклические. Ациклический граф имеет не более одного пути между любыми двумя вершинами; другими словами, не существует пути a-b-c-a, где {a, b, c} — различные вершины графа36. Циклический граф имеет хотя бы один цикл: можно найти путь, который начинается и заканчивается в одной и той же вершине (рис. 4.9). В случае ориентированных графов добавляется условие, что все ребра цикла должны иметь одинаковое направление — по часовой стрелке или против часовой стрелки; другими словами, в циклическом орграфе можно найти путь от вершины к самой себе, следуя по направлению стрелок. При программировании графовых алгоритмов необходимо соблюдать осторожность при обработке циклов, иначе программа может попасть в бесконечный цикл.

 

Рис. 4.9. Любой полный граф является циклическим

4.6.1. Деревья

Многие важные алгоритмы в теории графов оперируют с деревьями. Дерево — это просто связный граф, не имеющий циклов. Как правило, удобно описывать дерево, начиная с корня; мы назначаем одну вершину корнем дерева и определяем остальные вершины по их отношению к корню. Следующие определения для дерева являются эквивалентными:

• ациклический граф, в котором появится простой (без повторяющихся вершин) цикл, если добавить в него любое ребро37;

• связный граф, который перестанет быть связным, если удалить из него любое ребро;

• граф, в котором любые две вершины связаны уникальным простым путем.

Узлы дерева бывают двух типов: внутренние узлы (у которых есть хотя бы один дочерний элемент) и листья (у которых нет дочерних элементов) (рис. 4.10).

 

Рис. 4.10. Дерево с десятью вершинами. Это звезда, представляющая собой дерево ровно с одним внутренним узлом

4.6.2. Бесхордовые циклы

В большинстве случаев нас особенно интересуют бесхордовые циклы. Хорда — это ребро между двумя вершинами цикла, которое само не является частью цикла. Бесхордовый цикл — это цикл, который состоит хотя бы из четырех вершин и не содержит хорд (рис. 4.11). Другими словами, это такой цикл, в котором нет ребер между любыми двумя вершинами, не являющимися последовательными в цикле38.

 

Рис. 4.11.C5, бесхордовый цикл из пяти вершин

В главе 7 речь пойдет о нескольких классах графов, которые (по крайней мере частично) определяются отсутствием порожденных бесхордовых циклов, являющихся порожденными подграфами, содержащими циклы без хорд. Граф без порожденных бесхордовых циклов называется, что неудивительно, хордальным графом.

4.7. Раскраска графа

Многие графовые задачи связаны с раскраской — способом маркировки вершин (или ребер) графа. Правильная раскраска вершин — такая, при которой смежные вершины (то есть вершины, между которыми есть ребро) раскрашены в разные цвета. Другими словами, раскраска — это разделение вершин на независимые множества.

Математическое предупреждение Когда мы говорим о поиске раскраски графа, это не значит, что мы должны в буквальном смысле использовать цвета. Иногда при создании раскраски в роли цветов может выступать набор целых чисел. Даже если мы используем реальные цвета, компьютер все равно будет обрабатывать их как список целых чисел, а затем при визуализации преобразовывать целые числа в цвета.

Аналогично правильная раскраска ребер — это такая, при которой два ребра, инцидентные39 одной и той же вершине, раскрашены в разные цвета. Если не указано иное, то, говоря о раскраске графа, мы будем иметь в виду правильную раскраску вершин.

Первые результаты раскраски графов включали в себя раскраску плоских графов40 в виде карт. В гипотезе о четырех цветах41, выдвинутой в 1852 году, говорится, что для правильной раскраски любой карты, состоящей только из связных областей42 с границами конечной длины, требуется не более четырех цветов.

Доказательство этого утверждения было представлено Альфредом Кемпе в 1879 году и считалось общепринятым, пока в 1890 году не было доказано, что оно неверно43. В итоге задачу решили с помощью компьютера в 1976 году; теперь у нас есть алгоритмы квадратичного времени для любой четырехцветной карты44. До сих пор не существует доказательств, не требующих использования компьютера.

Несмотря на то что задача раскраски карты, в сущности, не представляла особого интереса для создателей карт, она интересна с теоретической точки зрения и имеет практическое применение. Так, судоку — это форма раскраски графа, «цветами» которого являются числа от единицы до девяти.

Хроматическое число графа — это количество цветов, необходимых для его правильной раскраски. Другая формулировка теоремы о четырех цветах состоит в том, что хроматическое число плоского графа — не больше четырех.

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

Проверка того, может ли произвольный граф быть двухцветным, занимает линейное время45 — достаточно окрасить одну вершину в красный цвет, затем окрасить все ее соседние вершины в синий, потом все соседние вершины этих вершин, которые еще не были окрашены, — в красный и т.д. Работа прекращается, когда либо все вершины окрашены, либо обнаружена вершина, у которой соседняя вершина имеет тот же цвет. А вот трехцветная раскраска является NP-полной задачей! Известно, что алгоритмы, определя­ющие, является ли граф k-раскрашиваемым, занимают экспоненциальное время. Однако, если знать, что граф принадлежит конкретному классу46, найти раскраску можно за полиномиальное время.

Алгоритмы раскраски обычно используются в таких приложениях, как планирование, анализ данных, работа в сетях и т.п. Например, рассмотрим задачу назначения времени для собраний длительностью один час, когда на разные собрания приглашаются разные люди и используется разное оборудование. Мы представляем каждое собрание в виде вершины и добавляем ребро между двумя вершинами, если в них задействованы одни и те же человек или оборудование. Нахождение минимальной раскраски говорит нам о необходимости назначить разное время для встреч (рис. 4.12).

 

Рис. 4.12. Граф C5 с минимальной раскраской

4.8. Взвешенные и невзвешенные графы

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

То, что конкретно означает вес, зависит от того, что описывает граф. На графе крупных городов ребра с весами могут представлять расстояния в милях по кратчайшему шоссе между двумя городами. На электрической схеме веса — это максимальный ток через данное соединение.