Комбинаторные алгоритмы

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ 

№ 644 
МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ 

ИНСТИТУТ СТАЛИ и СПЛАВОВ 

Технологический университет 

МИСиС 

Кафедра инженерной кибернетики 

Б.В. Черкасский 

Комбинаторные алгоритмы 

Курс лекций 

Рекомендовано редакционно-издательским 
советом института 

Москва 
Издательство ´УЧЕБАª 
2006 

УДК 519.712 
Ч-48 

Рецензент 

профессор Е.А. Калашников; 

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

операций С.-Петербургского государственного университета И.В. Романовский 

Черкасский Б.В. 
Ч-48 
Комбинаторные алгоритмы: Курс лекций. – М.: МИСиС, 
2006. – 159 с. 

Курс лекций состоит из десяти разделов, охватывающих материал полугодового курса «Комбинаторные алгоритмы». 

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

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

Курс лекций предназначен для студентов третьего курса, обучающихся 
по специальности 230401 (0730) «Прикладная математика», а также может 
быть рекомендован всем, кто интересуется данной темой. 

© Московский государственный институт 
стали и сплавов (технологический 
университет) (МИСиС), 2006 

ОГЛАВЛЕНИЕ 

От автора 
4 

1. Алгоритмы: классификация, сложность 
5 

2. Представление сетей в компьютере 
16 

3. Алгоритм нахождения компонент связности графа 
32 

4. Задача построения кратчайшего связывающего дерева 
42 

5. Алгоритм построения стабильного бракосочетания 
54 

6. Задача построения кратчайших путей 
63 

7. Задача построения кратчайших путей 
(алгоритм Беллмана – Форда) 
78 

8. Задача построения кратчайших путей (алгоритм Дейкстры) 
94 

9. Кучи 
109 

10. Деревья поиска 
133 

Библиографический список 
158 

3 

От автора 

В настоящем пособии приведены лекции полугодового курса 
«Комбинаторные алгоритмы», который читается студентам третьего 
курса кафедры «Инженерная кибернетика». Создание пособия оказалось возможным благодаря тому, что студентки О. Щеголева 
В. Грошева предоставили автору свои конспекты в виде файлов, которые и послужили толчком для написания этого курса лекций. 

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

Выражаю благодарность О. Щеголевой и В. Грошевой, без которых это издание не вышло бы в свет. 

4 

1. АЛГОРИТМЫ: КЛАССИФИКАЦИЯ, 
СЛОЖНОСТЬ 

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

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

1.1. Классификация алгоритмов 
по типу решения 

Сначала приведем примерную классификацию алгоритмов с точки зрения характера получаемого решения. 

1.1.1. Точные алгоритмы 

Такие алгоритмы дают точное решение поставленной задачи. Например, задан массив из n целых чисел. Среди них надо найти минимальное. Точный алгоритм решения этой задачи знает каждый. 

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

На складе находятся n типов предметов, причем количество 
предметов одного типа не ограничено. Для каждого типа предметов 
i известен вес ai и цена ci, i = 1 .. n. 

Задана вместимость рюкзака: А – максимальный вес, который он 
может выдержать. 

Обозначим через xi количество предметов i-го типа, находящих
ся в рюкзаке (естественно, xi ≥  0 – целое число). Тогда должно выполняться следующее ограничение: 

5 

V x^a^ <A 

г=1 

Задача состоит в максимизации суммарной стоимости предметов, 
помещенных в рюкзак: 

п 

1.1.2. Приближенные 
алгоритмы 

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

Например, если в задаче о рюкзаке обозначить через С = =^x,c, 

функционал некоторого допустимого решения, через Сmax - функционал оптимального решения, а через е - заданную погрешность, 
то е-приближенным решением является такое, что С>С m a x(1-е). 

Алгоритм, который для заданного е строит е-приближенное решение, называется приближенным алгоритмом. 

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

Иногда встречаются алгоритмы, которые не ищут приближенное 

решение, а строят точное решение задачи, «близкой к исходной». 

Так, для задачи о рюкзаке такой алгоритм мог бы построить решение, для которого =^x,a,<A' = A(1 + e), при этом среди всех решений с вместимостью'рюкзака A' суммарная ценность взятых предметов максимальна. 

1.1.3. Эвристические 
алгоритмы 

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

6 

Критерием качества эвристического алгоритма является то, что 
на практике он дает удовлетворительное решение, которое «устраивает заказчика». Другим способом оценки качества эвристического 
алгоритма может служить его сравнение с другими алгоритмами, 
предназначенными для решения той же задачи. Наш алгоритм может давать лучшее решение и/или быстрее работать. 

Примером эвристического алгоритма является алгоритм «иди в 
ближайший» в задаче коммивояжера. 

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

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

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

Вообще говоря, эвристическими алгоритмами (за редким исключением) стоит пользоваться только тогда, когда ни точного, ни приближенного алгоритма мы предложить не можем или по каким-то 
причинам они нас не устраивают. Но даже в этом случае к эвристическим алгоритмам надо относиться с осторожностью: даже если 
1000 задач с его помощью решены успешно, нет никаких гарантий, 
что 1001-е решение также будет удовлетворительным. С особой осторожностью следует относиться к утверждениям авторов о том, что 
их эвристические алгоритмы «всегда отлично работают» – такое бывает, но очень редко. 

1.1.4. Вероятностные алгоритмы 

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

дить меру. Затем надо доказывать, например, что мера подмножества задач, на которых алгоритм дает точное решение, больше 0,99. 

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

1.2. Классификация алгоритмов 
по способу выполнения операций 

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

1.2.1. Последовательные 
алгоритмы 

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

1.2.2. Параллельные 
алгоритмы 

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

Так, например, с помощью п2 процессоров можно быстро перемножить две матрицы размером пхп каждая. При этом перемноже
8 

ние каждой пары «строка – столбец» осуществляется с помощью 
«своего» процессора. Разные процессоры при работе не будут зависеть друг от друга, так что ни один из них не будет ожидать результатов работы другого. 

Вообще, часто говорят, что алгоритм хорошо «распараллеливается», если от увеличения количества процессоров время решения задачи существенно уменьшается. Алгоритм перемножения матриц распраллеливается замечательно. Однако не все последовательные алгоритмы таковы. Часто приходится придумывать алгоритмы, специально предназначенные для работы на многопроцессорных системах. 
Параллельные вычисления – это особая наука, которая, в частности, 
включает в себя изучение различных классов параллельных алгоритмов и многое другое, чего мы в этом курсе лекций касаться не будем. 

1.3. Классификация алгоритмов 
по детерминированности операций 

1.3.1. Детерминированные алгоритмы 

Еще одним классифицирующим признаком является предопределенность действий алгоритма. Как правило, рассматриваемые алгоритмы являются детерминированными, но встречаются и рандомизированные алгоритмы. 

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

1.3.2. Рандомизированные алгоритмы 

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

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

9 

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

1.4. Сложность алгоритмов 

Одними из самых важных показателей качества алгоритма являются время его работы (скорость) и объем используемой памяти. 
Сложность – это теоретическая оценка качества алгоритмов с точки 
зрения их скорости. 

Каждая задача может быть по определенным правилам закодирована с помощью входного слова – последовательности символов некоторого алфавита. Обозначим через R длину входного слова – количество символов, из которых оно состоит. Число R будем называть размером задачи. 

1.4.1. Оценка сложности сверху 

Обозначим через F(R) функцию, дающую оценку сверху максимального числа операций, которые нужны алгоритму для решения 
задачи размером R; то есть для решения любой задачи размером R 
алгоритм использует не более чем F(R) операций. Такая оценка 
сложности называется оценкой сверху. Как правило, сложность алгоритмов оценивают с точностью до константы. Причина этого состоит в том, что точное количество операций алгоритма зависит от 
особенностей конкретного компьютера и используемого алгоритмического языка и считать их трудно, да и не имеет особого смысла. К 
тому же оценка сложности с точностью до константы верна для всех 
принципиально не отличающихся друг от друга компьютеров и, как 
правило, дает адекватное представление о качестве алгоритма. Будем полагать, что алгоритм имеет сложность порядка O(F(R)) , если 

на решение любой задачи размером R им будет потрачено не более 
чем С1F(R) +C2 операций, где С1 и С2 – константы, не зависящие от 
размеров задачи. 

Иногда вместо термина «сложность» мы будем употреблять как 
синоним слово «трудоемкость». 

Полезно ли умение находить оценку сложности алгоритма и 
имеют ли оценки сложности сверху какое-то отношение к практике? 
В основном да, хотя к таким оценкам, как к любой абстракции, надо 
подходить осторожно. Если оценка сверху хороша, то можно быть 

10