close

Вход

Забыли?

вход по аккаунту

?

1067.Методы построения эффективных алгоритмов учебное пособие Волченков

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. Г. Демидова
С.Г. Волченков, Ю.В. Богомолов
Методы построения
эффективных алгоритмов
Учебное пособие
Рекомендовано
Научно-методическим советом университета
для студентов специальности Математическое обеспечение
и администрирование информационных систем
Ярославль 2005
1
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 510.5
ББК В127я73
В 68
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2005 года
Рецензенты:
кандидат педагогических наук Н.Л. Дашниц;
кафедра теории и методики обучения информатике
Ярославского государственного педагогического университета
им. К.Д. Ушинского
В 68
Волченков, С.Г., Богомолов, Ю.В. Методы построения эффективных алгоритмов : учебное пособие / С.Г. Волченков,
Ю.В. Богомолов ; Яросл. гос. ун-т. – Ярославль : ЯрГУ, 2005. –
146 с.
ISBN 5-8397-0401-6
Учебное пособие (продолжение одноименного учебного пособия, изданного в 2004 г.) посвящено различным аспектам построения и анализа эффективных алгоритмов решения некоторых задач. Материал разбит на главы по предметным областям и
по методам решения задач. Главы посвящены геометрическим
методам в задачах информатики, рекурсии, динамическому программированию и структурам данных.
Пособие рассчитано на студентов факультетов информатики
и вычислительной техники, обучающихся по специальности
351500 Математическое обеспечение и администрирование информационных систем (дисциплина "Методы построения эффективных алгоритмов", блок ДС), очной формы обучения, а также
может оказаться интересным для школьников, принимающих
участие в олимпиадах по информатике.
УДК 510.5
ББК В127я73
ISBN 5-8397-0401-6
© Ярославский государственный университет, 2005
© С.Г. Волченков, Ю.В. Богомолов, 2005
2
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Предисловие
Данное пособие не претендует на описание всех существующих методов построения эффективных алгоритмов.
Достаточно сказать, что учебник по алгоритмам, недавно
выпущенный в Массачусетском технологическом институте
[1] и переведенный на русский язык, содержит 955 страниц!
И этот учебник, в свою очередь, тоже далеко не полон. Считается, что относительной полнотой обладает трёхтомник
Д. Кнута [2], правда, в нём очень сильно ограничен круг
рассматриваемых вопросов, но те, что рассматриваются, разобраны чрезвычайно пунктуально и интересно. Также существуют учебники и монографии, которые, как правило,
либо узкоспециализированны, либо, напротив, пытаясь охватить возможно более широкий круг алгоритмов, носят поверхностный характер и не содержат достаточного круга задач [3 – 7, 9 – 13]. Создалась парадоксальная ситуация, когда при относительно широком освещении рассматриваемой тематики литература, которую можно было бы рекомендовать для изучения в рамках соответствующего учебного курса, труднодоступна.
Предлагаемое учебное пособие является продолжением
пособия, изданного в 2004 году. В нем рассмотрены методы
построения алгоритмов на графах, алгоритмов сортировки и
поиска, а также рассматриваются вопросы переключения
алгоритмов.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 1
Алгоритмы на графах
Введение
В одной из компьютерных игр как-то встретилась такая головоломка. На неровной шахматной доске, состоящей из 10 клеток
(рис.1), расположены два белых и два черных коня. Требуется
поменять коней местами, т.е. расположить белых на места черных и наоборот. Коней разрешается переставлять по правилам
шахматной игры, т.е. передвигать "буквой Г" на любую свободную клетку. За один ход можно передвинуть одного коня.
Рис. 1
Несколько попыток решить задачу сходу ни к чему не привели. Вооружившись карандашом и бумагой, я попытался фиксировать промежуточные положения коней, но скоро убедился, что
записей стало катастрофически много. Вздохнув и призвав на
помощь знания ранее встречавшихся головоломок и задач, я стал
строить математическую модель задачи. Во-первых, я обозначил
клетки доски числами от 1 до 10 и соединил отрезками центры
клеток, которые связаны друг с другом ходом коня. Получился
рисунок, содержащий всевозможные траектории передвижения
коней по доске (рис. 2)
•
•
•
•
•
•
•
4
•
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
•
•0
Рис. 2
Теперь можно было заметить, что траектории движения коней довольно сильно запутаны, и в них трудно разобраться. Распутать их было несложно, разместив числа, соответствующие
клеткам, в другом порядке: так чтобы клетки, соединенные друг с
другом, были размещены рядом. Получился рисунок 3.
Рис. 3
Теперь на получившейся схеме отметим коней: белых – кружочками, черных – квадратиками (рис. 4).
Рис. 4
Остается вспомнить, что нам надо сделать. Надо поменять
местами "встретившихся на одной тропинке коней". Для маневра
оставлена клетка 6, на которую может встать один из коней, чтобы пропустить мимо себя других. Теперь решение задачи рождается несложно.
Белого коня с клетки 4 передвигаем на клетку 6, пропускаем
черных коней с их начальных позиций на клетки 7 и 1. Затем белого коня с клетки 6 перегоняем на клетку 3. Один конь на месте!
Отгоняем черных коней на клетки 10 и 2, чтобы освободить
для белого коня, стоящего на клетке 5, проход к клетке 6. Когда
тот туда проходит, черный конь с клетки 10 беспрепятственно
продвигается на клетку 5. Второй конь на месте!
Теперь второй черный конь с клетки 2 проходит мимо клетки
6 на клетку 1, освобождая проход для белого коня. Тот немедленно пользуется этой ситуацией и продвигается на свое место с
клетки 6 на клетку 2.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Последний черный конь становится на требуемую позицию с
поля 1 на 4. Кавалерийский маневр завершен!
А теперь приведем полный список ходов коней, с помощью
которых удалось решить задачу.
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
4–6
2 – 10
10 – 4
4 –1
1–7
3–9
9–8
8–2
2 – 10
10 – 4
4–1
6–4
4 – 10
10 – 2
2–8
8–9
9–3
1–4
4 – 10
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
10 – 2
7 –1
1–4
4 –10
5–7
7–1
1–4
4–6
10 – 4
4–1
1–7
7–5
2 –10
10 – 4
4–1
6–4
4 – 10
10 – 2
1–4
Более подробный анализ показывает, что полученный алгоритм, содержащий 38 ходов, является кратчайшим из всех возможных!
Определения и примеры
Итак, в предыдущей части, чтобы успешно решить задачу,
нам потребовалось представить её условие наглядно. Для этого
мы воспользовались рисунком, на котором отметили возможные
6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
переходы коней с одной позиции на другую. Подобные рисунки
принято называть графами.
Наглядное представление о графе можно получить, если
представить себе некоторое множество точек плоскости X, называемых вершинами, и множество отрезков U, соединяющих все
или некоторые из вершин. Если при этом рассматриваемые отрезки являются направленными, то они называются дугами, а если ненаправленными, то ребрами. Дуги используются для обозначения несимметричных отношений между вершинами, например отношение "отец – сын", или возможных переходов от одной
вершины к другой, например если вершины изображают шахматные позиции, то иногда из одной в другую можно перейти, а наоборот нельзя (ход пешкой или рокировка). Ребра же изображают
симметричные отношения между вершинами, например, если
вершины – люди, то наличие ребра между вершинами может означать, что люди знакомы друг с другом. Принято при изображении графов на дугах рисовать стрелку, идущую из начальной
вершины в конечную.
Итак, что же такое граф? Постараемся дать более формальное
определение графа и его компонентов, а также привести примеры.
Математически граф G можно определить как пару множеств
Х и U: G = (Х,U), где X – конечное множество, называемое множеством вершин, а U – некоторое множество пар вершин их X.
На рис. 5 изображен граф, вершинами которого являются
точки а, b, с, d, е, g, h, а дугами – отрезки (а, а), (с, b), (с, d), (с, е),
(d, с), (d, d), (е, d), (g, h). Примерами графов являются отношения
отцовства и материнства на множестве людей, карта дорог на местности, схема соединений электрических приборов, отношения
превосходства одних участников турнира над другими, и т.п.
Введем некоторые понятия и определения, служащие для
описания частей графов и их различных видов.
Подграфом GA графа G = (X, Г) называется граф, в который
входит лишь часть вершин графа G, образующих множество А,
вместе с некоторыми дугами, соединяющими эти вершины, например очерченная пунктиром область на рис. 5.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 5. Граф и подграф
Другими важными понятиями являются понятия пути и контура. Ранее было дано определение дуги как направленного отрезка, соединяющего две вершины. Дуга, соединяющая вершины
а и b и направленная от а к b, обозначается u = (а, b).
Путем в графе G называют такую последовательность дуг
m = (Ui, ...,Uk), в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь m, последовательными вершинами которого являются вершины а, b, ..., m, обозначается через
m = (a, b, ..., m).
Длиной пути m = (u1, ..., ur) называют число l(m) = k, равное
числу дуг, составляющих путь m. Иногда каждой дуге Ui приписывают некоторое число l(ui), называемое длиной дуги. Тогда
длина пути определяется как сумма длин дуг, составляющих путь
Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.
Контур - это конечный путь m = (Xi,...,Xk), у которого начальная вершина Xi совпадает с конечной Xk. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур
единичной длины, образованный дугой вида (а, а), называется
петлей. Так, на рис. 5 (е, d, с, b) – путь, (с, е, d, с) – контур, (d, d) петля.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 6. Неориентированный граф
Иногда граф рассматривают без учета ориентации дуг, тогда
его называют неориентированным графом. Для неориентированного графа понятие "дуга", "путь" и "контур" заменяются понятиями "ребро", "цепь", "цикл". Ребро - это отрезок, соединяющий
две вершины. Цепь - последовательность ребер. Цикл - цепь, у
которой начальная и конечная вершины совпадают.
На рис. 6 приведен пример неориентированного графа, у которого вершины обозначены цифрами, а ребра - буквами латинского алфавита.
Приведем еще несколько определений, служащих для характеристики неориентированных графов.
Степенью вершины, х, обозначаемой deg(x) или dx, называют число ребер, инцидентных вершине х. Так, для графа на рис. 3
имеем: deg(b) = 2, deg(c) = 2, deg(a) = 3, deg(e) = 0. Если deg(x) = 1,
то вершину х называют висячей (вершина 4), если deg(x) = 0, то
вершину называют изолированной (вершина 5).
Нетрудно заметить, что сумма степеней всех вершин графа – четное число.
Доказательство следует из того, что каждое ребро добавляет
единицу к степени каждой из двух вершин, которые оно соединяет, т. е. добавляет 2 к сумме степеней уже имеющихся вершин.
Следствие. В каждом графе число вершин нечетной степени
четно.
Для неориентированного графа понятия "подграф" и "частичный граф" аналогичны соответствующим понятиям для ориентированного графа.
С понятием неориентированного графа связана важная характеристика, называемая связностью графа. Говорят, что граф
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
связен, если любые две его вершины можно соединить цепью.
Если граф G не связен, то его можно разбить на такие подграфы
Gi, что все вершины в каждом подграфе связны, а вершины из
различных подграфов не связны. Такие подграфы G, называют
компонентами связности графа G.
Если из графа на рис. 6 исключить изолированную вершину
5, то полученный граф будет связным. Граф на рис. 7 не связен и
имеет две компоненты связности, его можно превратить в связный, добавив ребро (мост), соединяющее вершины 3 и 5 (штриховая линия). Удаление моста превращает связный граф в несвязный.
Рис. 7. Мост в графе
Для того чтобы определить связность ориентированного
графа, не нужно обращать внимание на ориентацию дуг. Граф,
изображенный на рис. 5, несвязный. Однако его подграф, состоящий из вершин a, с, d, е, является связным. Для ориентированного графа существует понятие сильной связности. Граф
сильно связен, если для любых двух вершин (х и у) существует
путь, идущий из х в у.
Представления графов в компьютере
Описать неориентированный граф G можно путем задания
пары множеств (X, U), где Х – множество вершин; U – множество
ребер. Однако более удобным, особенно в случае представления
графа в компьютере, является описание неориентированного
графа с помощью матрицы смежности или инциденции, которые
строятся аналогично соответствующим матрицам для ориентированных графов с той разницей, что не делается различия между
заходящей в вершину и исходящей из нее дугами. При этом вер10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
шины x и у называют смежными, если существует соединяющее
их ребро, а само это ребро называется инцидентным вершинам х
и у. Для графа рис. 6 матрицы смежности и инциденции имеют
вид:
Матрица смежности:
Вершины
Вершины
1
2
3
4
5
1
0
1
1
1
0
2
1
0
1
0
0
3
1
1
0
0
0
4
1
0
0
0
0
5
0
0
0
0
0
Матрица инциденции:
Вершины
Ребра
1
2
3
4
5
a
1
1
0
0
0
b
0
1
1
0
0
c
1
0
1
0
0
d
1
0
0
1
0
Использование матриц смежности или инцидентности удобно далеко не всегда. Представим, например, граф железных дорог
России, где вершинами являются отдельные станции, а ребрами –
участки дороги, соединяющие соответствующие эти станции. Ясно, что в таком графе много тысяч вершин, а значит, в матрице
смежности – несколько миллионов элементов. Причем, в каждой
строке этой матрицы количество элементов почти всегда равно
двум (через станцию почти вседа проходит только один путь, т.е.
она соединена только с двумя соседними станциями). Таким об11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
разом, почти все элементы матрицы смежности равны нулю, и
значит, матрица содержит крайне мало информации. При этом
она занимает много места, и работать с ней неудобно.
Гораздо экономнее представлять дуги в виде списка, но при
этом появляется еще одна неприятность – очень трудно становится определить, какие дуги выходят из данной вершины, а такая
информация в графе, как правило, является главной.
Чтобы сохранить возможность быстрого определения множества дуг, исходящих из данной вершины, можно поступать следующим образом. Рассмотрим сначала работу с ориентированными графами, а затем распространим результат и на неориентированные графы.
Во-первых, список дуг отсортируем по первой вершине. Сначала в таком отсортированном списке будут следовать дуги, исходящие из первой вершины, затем – из второй, и т.д. Искать
нужные дуги, конечно, станет легче, но можно пойти и дальше.
Заведем вспомогательный массив, состоящий из n элементов, в
котором i-ый элемент означает, с какого места в списке дуг начинаются дуги, выходящие их i-ой вершины. Назовем новый массив
справочным.
Таким образом, список дуг и соответствующий справочный
массив для графа, изображенного на рис. 6, будут выглядеть следующим образом:
Список дуг:
1. (1, 2)
2. (1, 3)
3. (1, 4)
4. (2, 1)
5. (2, 3)
6. (3, 1)
7. (3, 2)
8. (4, 1)
Справочный массив:
1. 1
2. 4
3. 6
4. 8
Заметим, что при таком представлении становится ненужным
хранить в списке дуг информацию о первой вершине!
Поэтому список дуг с оглавлением может выглядеть следующим образом:
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Список дуг:
1. 2
2. 3
3. 4
4. 1
5. 3
6. 1
7. 2
8. 1
Справочный массив:
1. 1
2. 4
3. 6
4. 8
Ориентированные графы представляются в виде матриц
смежности и инциденции аналогичным образом. Отличие в том,
что требуется разным образом отмечать начало и конец дуги. К
примеру, если из i-й вершины в j-ю идет дуга, то на пересечении
i-й строки и j-го столбца матрицы смежности будет стоять 1, но
это не означает, что в симметричной относительно главной диагонали (на пересечении j-й строки и i-го столбца) ячейке матрицы
смежности тоже будет стоять единица (никто не гарантирует, что
из j-й вершины в i-ю тоже идет дуга). К примеру, для следующего
графа
матрица смежности будет выглядеть так:
Вершины
Вершины
1
2
1
0
1
0
1
2
1
0
0
0
3
0
1
0
1
4
0
0
0
0
13
3
4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Матрица инцидентности строится по уже знакомой схеме –
перечисляются дуги и отмечается, какие вершины какими дугами
связаны. Если дуга f идет от i-й вершины к j-й, то в соответствующей данной дуге строке в i-м столбце поставим –1, а в j-м
столбце поставим 1. В незаполненные ячейки вписываются нули.
Для рассмотренного выше ориентированного графа матрица инцидентности имеет следующий вид:
Ребра
Вершины
1
2
3
4
a
–1
1
0
0
b
1
–1
0
0
c
0
1
–1
0
d
–1
0
0
1
e
0
0
–1
1
Аналогично строится список дуг (вместо списка ребер), а
также список дуг с оглавлением. При этом необходимо помнить,
то дуги имеют направление, и наличие в списке, к примеру, дуги
(2, 5) не влечет наличия дуги (5, 2). В оглавлении приводятся указатели на позицию в списке дуг, начиная с которой перечисляются дуги, исходящие из конкретных вершин.
Алгоритмы нахождения путей в графе
Чаще всего при работе с графами требуется находить в них
различные пути. Если граф представляет схему дорог, то эта задача совершенно естественна. Но даже граф не является схемой
дорог, то и тогда пути могут иметь важное значение. В качестве
примера можно привести граф состояний шахматной партии, в
котором путь может означать способ достижения выигрыша.
Существуют разные алгоритмы отыскания путей в графе. Эти
алгоритмы ориентированы на конкретные задачи. Например, если
требуется просто установить наличие или отсутствие путей между вершинами (связность графа), достаточно использовать волновой алгоритм. Если же требуется искать путь с какими-то свойст14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вами, например самый короткий, то чаще используют алгоритмы
Дейкстры или Флойда.
Поиск в графе
Одной из наиболее важных задач на графах является задача
поиска. В вершинах графа можно хранить некоторые значения,
среди которых можно осуществлять поиск удовлетворяющих условию элементов. Также иногда необходимо решать задачу обхода графа, то есть перечисления всех его вершин (или значений,
записанных в этих вершинах) ровно по одному разу. Мы рассмотрим два способа обхода (поиска) вершин в графе – поиск в
глубину и поиск в ширину.
Поиск в глубину
Поиск (обход) начинаем с некоторой вершины. Сначала просматриваем первую вершину (под просмотром можно понимать
вывод номера вершины на экран или в файл, анализ содержащегося в вершине значения или какое-либо другое действие) – пусть
это вершина u. Потом просматриваем смежную с ней вершину
(v). Далее посматриваем вершину, смежную с v (вершина w), и
т. д. На каждом шаге после рассмотрения очередной вершины (t)
просматриваем произвольную из не просмотренных ранее вершин, смежных с текущей вершиной t. Если же у вершины t нет
смежных вершин, которые мы еще не рассматривали, то возвращаемся на предыдущую вершину и ищем непросмотренные
смежные (уже с ней) вершины. Если и у этой вершины нет "соседей", не просмотренных ранее, то возвращаемся еще на один шаг
назад, и т. д. Процесс заканчиваем тогда, когда на одном из шагов
алгоритма требуется сделать шаг назад относительно вершины, с
которой мы начинали просмотр.
При организации такого просмотра можно использовать стек
(для хранения номеров просматриваемых вершин) и массив (для
пометок просмотренных вершин). Считаем, что уже определены
операции помещения элемента в стек, выборки элемента с вершины стека, просмотра элемента на вершине стека, проверки, является ли стек пустым. В массив M будем записывать 1 в k-ю
ячейку, если k-я вершина просмотрена, и 0 – в противном случае.
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В начале работы стек пуст, а массив M заполнен нулями. Пусть
C – матрица смежности графа (C[i,j] = 1, если есть ребро (i,j) и 0 –
в противном случае). Обход графа начнем с вершины с номером
1. Алгоритм опишем следующим образом:
Push(1); {поместили в стек номер
1-й вершины,...}
Просмотреть(1);
{посмотрели ее...}
M[1]:=1;
{и пометили как просмотренную}
while not Empty do {пока есть вершины,
подлежащие обработке...}
begin
v:=Top;
{номер текущей вершины
берем с вершины стека}
s:=0;
{будем записывать в s
номер очередной вершины}
for k:=1 to N do
if M[k]=0 and C[v,k]=1 {нашли
непросмотренную вершину,}
then begin
{смежную с v}
s:=k;
{запоминаем ее номер}
break;
{выходим из цикла}
end;
if s<>0 then {если очередная вершина
была найдена,...}
begin
Просмотреть(s); {просматриваем ее}
M[s]:=1; {помечаем ее как просмотренную}
Push(s); {и помещаем ее в стек}
end
else
s:=Pop; {удаляем текущую вершину из стека}
end;
Алгоритм поиска в глубину можно записать и в рекурсивной
форме. В этом случае определим рекурсивную процедуру
Search(k), где k – номер вершины, начиная с которой мы осуществляем поиск в глубину:
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
procedure Search(k: integer);
begin
Просмотреть(k);
M[k]:=1;
for t:=1 to N do
if (C[k,t]=1) and (M[t]=0) then Search(t);
end;
Таким образом, при данном способе поиска граф просматриваем в глубину так, как это возможно, а когда дальнейший просмотр невозможен, возвращаемся немного назад и пытаемся продолжить просмотр уже по несколько другому пути.
Поиск в ширину
Если при поиске в глубину мы последовательно просматривали вершины графа до тех пор, пока это возможно, то при поиске в ширину вначале будут просмотрены вершины, смежные с
начальной, потом – вершины, смежные с теми, которые смежны с
начальной, и т. д., пока не будут просмотрены все вершины графа. Иначе говоря, раньше будут просмотрены те вершины, которые находятся на меньшем расстоянии от начальной вершины
(под расстоянием между вершинами понимается длина кратчайшего пути между ними).
Подлежащие рассмотрению вершины удобно хранить в очереди. В начале работы в очередь поместим номер начальной вершины. Затем в очередь добавляем номера вершин, смежных с начальной, а номер самой начальной вершины из очереди удалим.
Потом берем из очереди номер следующей вершины, помещаем в
очередь номера смежных с ней вершин, а саму вершину удаляем,
и т. д. Понятно, что при таком способе просмотра вершины, которые расположены ближе к начальной, будут рассмотрены
раньше, чем те, которые находятся от начальной вершины на
большем расстоянии (действительно, ведь они раньше помещены
в очередь просмотра вершин).
Ниже приведем алгоритм (при этом предполагаем, что определены операции работы с очередью – добавления элемента (In17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
sert), удаления элемента (Remove), проверки, является ли очередь
пустой (Empty)).
procedure Search2(k: integer);
begin
Insert(k); {помещаем в очередь номер
начальной вершины}
M[k]:=1;
while not Empty do {пока в очереди есть
подлежащие обработке вершины,}
begin
{просматриваем их}
v:=Remove;
{берем очередную
вершину из очереди,}
Просмотреть(v); {просматриваем ее}
for t:=1 to N do
if (C[v,t]=1) and (M[t]=0) {все смежные
с ней вершины,}
then begin
{которые не были
еще просмотрены,}
Insert(t);
{добавляем в}
M[t]:=1;
{очередь просмотра}
end;
end;
end;
С подобного рода алгоритмами мы встречались и ранее:
вспомните алгоритм обхода лабиринта, где мы помечали просмотренные клетки. При этом число, которое записано в клетке
лабиринта, означало длину кратчайшего маршрута от начальной
клетки до данной.
Аналогичное утверждение верно и для графа. Просмотренные вершины мы пока что помечали единицами, остальные – нулями. Способ пометки можно несколько модифицировать: будем
помечать вершины, которые еще не просмотрели, числами –1, а
просмотренные вершины – отличными от –1 числами. При этом
начальную вершину можно пометить нулем, а остальные помечать следующим способом: если вершина помечена числом k, то
смежные с ней вершины (которые мы еще не просмотрели) будем
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
помечать числом k+1 и добавлять в очередь просмотра. Алгоритм
модифицируется следующим образом:
procedure Search3(k: integer);
begin
for t:=1 to N do M[k]:=-1;
Insert(k); {помещаем в очередь
номер начальной вершины}
M[k]:=0;
{помечаем ее нулем}
while not Empty do {пока в очереди есть
подлежащие обработке вершины}
begin
{просматриваем их}
v:=Remove; {берем очередную
вершину из очереди}
Просмотреть(v); {просматриваем ее}
for t:=1 to N do
if (C[v,t]=1) and (M[t]=-1)
{все смежные с ней вершины,}
then begin
{которые не были
еще просмотрены,}
Insert(t);
{добавляем в
очередь просмотра}
M[t]:=M[v]+1; {и помечаем}
end;
end;
end;
В результате работы этого алгоритма пометки будут иметь
следующий смысл: если вершина помечена числом k, то расстояние (длина кратчайшего пути) от начальной вершины до данной
равно k. Если граф был несвязным, то некоторые вершины так и
останутся помеченными числом –1. Поэтому данный алгоритм
(да и первый алгоритм поиска в ширину тоже) можно использовать для проверки связности графа.
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поиск кратчайшего пути
между двумя вершинами
Постановка задачи
Решим следующую задачу: имеется несколько городов, некоторые из которых соединены дорогами, причем длины дорог известны. Требуется найти длину кратчайшего пути между двумя
выбранными городами.
Конечно, можно было бы предложить перебрать все возможные пути между выбранными городами, после чего выбрать из
них кратчайший. Но сразу ясно, что такой способ хорошим никак
назвать нельзя. Во-первых, сложность состоит в самом переборе
путей, а во-вторых, не стоит рассчитывать на оптимальность такого переборного алгоритма. Поэтому для решения этой задачи
мы будем использовать более эффективные алгоритмы.
Для начала сформулируем данную задачу на языке теории
графов. Итак, у нас есть связный граф с N вершинами (то есть, из
любой вершины можно попасть в любую другую). Каждое ребро
имеет определенный вес. Веса удобно записывать в матрицу
смежности – двумерный массив C (NxN), при этом элемент
C[i,j] – вес ребра, соединяющего вершины с номерами i и j.
Граф, в котором ребрам приписаны веса, называется взвешенным.
Также удобно считать, что если две вершины не соединены
ребром, то вес ребра между этими вершинами равен бесконечности. Иначе говоря, добавляем отсутствующие ребра, дополняя
граф до полного графа (в котором все вершины попарно соединены), при этом добавляемые ребра (те, которых не было в исходном графе) получают бесконечный вес. В качестве "бесконечности" можно использовать очень большое целое число (например,
такое число, которое больше суммы весов всех ребер в исходном
графе). Петлям (ребрам, идущим из вершины в саму эту вершину) можно приписать вес 0.
Так как между отмеченными вершинами существует путь, то
при добавлении таких фиктивных ребер (с бесконечными весами)
мы "не испортим" результат. Действительно: кратчайший путь не
может содержать ребро бесконечного веса, так как существует
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
путь короче (просто произвольный путь между отмеченными
вершинами по имеющимся в исходном графе ребрам).
Весом (длиной) пути будем называть сумму весов всех входящих в путь ребер. Требуется найти длину кратчайшего пути
между двумя заданными вершинами графа. Длину кратчайшего
пути между вершинами будем также называть расстоянием.
Для решения задачи нахождения длины кратчайшего пути
между вершинами обычно используют алгоритмы Дейкстры и
Форда – Беллмана.
Алгоритм Дейкстры
Рассматриваемый алгоритм (алгоритм Дейкстры) решает более общую задачу: пусть в графе выделена некоторая вершина.
Тогда найдем кратчайшие расстояния от данной вершины до всех
остальных вершин графа. Если нам нужно найти кратчайшее расстояние между двумя заданными вершинами, то можно взять
первую вершину, применить для графа с данной выделенной
вершиной алгоритм Дейкстры, после чего выбрать из полученных данных расстояние от первой вершины до второй.
Очевидна некоторая избыточность: возможно, нам и не нужно находить расстояния от данной вершины до всех остальных, а
интересует путь только лишь между двумя заданными вершинами. Однако эффективных алгоритмов, которые находят лишь
нужный нам путь (и не решают указанную выше общую задачу)
пока не известно.
Пусть выделена некоторая вершина v. В ходе работы алгоритма Дейкстры будем заполнять массив D кратчайших расстояний от вершины v до всех остальных вершин в графе. В итоге для
каждого значения k от 1 до N в элементе D[k] будет содержаться
кратчайшее расстояние между вершинами v и k.
В ходе работы алгоритма также будем помечать некоторые
вершины. В начале работы алгоритма помечена только начальная
вершина (первая), в конце работы оказываются помеченными все
вершины. При этом на каждом шаге работы алгоритма для каждой помеченной вершины хранится длина самого короткого пути
между первой вершиной и данной, причем известно, что путь
минимальной длины проходит только через помеченные города.
А для каждой непомеченной вершины хранится наименьшая
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
длина среди всех путей от первой вершины до данной, в которых
в качестве промежуточных используются помеченные города.
Иначе говоря, хранимое для непомеченной вершины число показывает, какое наименьшее расстояние нужно преодолеть от вершины 1 до данной, если в качестве промежуточных можно использовать только помеченные вершины.
Все эти числа можно хранить в массиве D. Данные хранимые
величины будем называть оценками длин кратчайших путей.
Оценки кратчайших путей для помеченных вершин являются
точными, а для непомеченных требуют корректировки при каждой пометке очередной вершины.
На каждом шаге алгоритма будем добавлять к множеству
помеченных вершин еще одну вершину, а для непомеченных
вершин будем корректировать оценки кратчайших путей. Выбор
очередной вершины осуществляется следующим образом: рассмотрим все непомеченные вершины, выберем из них ту, для которой оценка длины кратчайшего пути минимальна (пусть это
вершина z), и пометим ее. Легко убедиться в том, что данная
оценка кратчайшего пути до вершины z является точной. Действительно, если рассмотреть путь, содержащий какую-нибудь непомеченную вершину w, то уже до вершины w путь будет длиннее, чем рассматриваемая оценка кратчайшего пути, а ведь от w
нужно дойти до вершины z.
После того как вершина z будет помечена, требуется скорректировать оценки кратчайших расстояний до непомеченных
вершин. Сделать это не очень сложно: кратчайшее расстояние до
непомеченной вершины может содержать вершину z, а может и
не содержать ее. Длина кратчайшего пути, проходящего за все
помеченные вершины, кроме z, уже известны. А среди остальных
путей с промежуточными помеченными вершинами можно рассмотреть лишь те, в которых вершина z (последняя помеченная)
является последней промежуточной вершиной.
Данную операцию повторяем до тех пор, пока не будут помечены все вершины.
Учитывая все сказанное выше, алгоритм Дейкстры поиска
длины кратчайшего пути от вершины v до остальных вершин
можно описать следующим образом:
22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 1:
Для k от 1 до N: D[k]:=C[v,k]; {начальные оценки
длины путей}
M:=[1..N]-[v]; {множество непомеченных
вершин}
Пока M не пусто выполнять шаг 2.
Шаг 2:
w – непомеченная вершина оценка длины пути минимальна; {D[w] минимальна среди всех D[k] для непомеченных k}
M := M-[w]; {исключаем w из множества непомеченных вершин}
Для всех k из множества M:
D[k] := min{D[k],D[w]+C[w,k]};
После заполнения массива D достаточно выбрать из него
кратчайшее расстояние от вершины v до любой другой вершины.
Покажем работу алгоритма Дейкстры на примере. Рассмотрим следующий граф:
Рис. 8. Взвешенный граф
Матрица весов C для данного графа выглядит следующим
образом:
0
7
5
∞
∞
∞
∞
∞
7
0
9
4
∞
6
∞
∞
5
9
0
7
8
∞
∞
∞
∞
4
7
0
6
∞
9
∞
∞
∞
8
6
0
∞
8
∞
23
∞
6
∞
∞
∞
0
11
7
∞
∞
∞
9
8
11
0
6
∞
∞
∞
∞
∞
7
6
0
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Будем искать расстояния от вершины с номером 1 до всех
остальных вершин. В начале работы алгоритма массив D (массив
оценок кратчайших путей) заполняем просто длинами ребер от
первой вершины до каждой из оставшихся вершин:
D = [0, 7, 5, ∞, ∞, ∞, ∞, ∞]
Помеченной является пока только первая вершина. Заметим,
что оценка расстояния до нее является точной: она равна нулю и
меньше быть не может.
Теперь начинаем помечать и остальные вершины. Среди всех
непомеченных вершин (а ими пока являются все вершины, кроме
первой) выбираем ту, для которой оценка длины кратчайшего пути минимальна (фактически, выбираем минимальный из элементов массива D, соответствующий непомеченным вершинам).
Такой является вершина с номером 3 (а соответствующая
оценка равна 5). Помечаем эту вершину и начинаем пересчитывать оценки расстояний. Оценка либо останется прежней (пока
кратчайший путь проходит через те же вершины, что и до добавления новой вершины в список помеченных), либо изменилась
(если кратчайший путь проходит через вновь добавленную помеченную вершину). Для этого (в соответствии с алгоритмом) для
всех k, отличных от 1 и 3, в качестве элемента D[k] выбирается
минимум из D[k] (прежнее значение) и D[2]+C[3,k] (новый кратчайший путь проходит через добавленную вершину 3).
Итак, оценка расстояния до вершины 2 не изменилась (попрежнему короче путь напрямую от вершины 1, нежели "с пересадкой" в помеченной вершине 2). Не изменятся оценки длины
кратчайшего пути и до вершин 6, 7, 8: он равен "бесконечности"
как без использования промежуточной вершины 3, так и с использованием ее в качестве "перевалочного пункта".
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
А вот оценки расстояний до вершин 4 и 5 изменятся. Действительно, длина прямого пути от вершины 1 до вершины 4 была
равена "бесконечности", а теперь проще будет добраться до нее
через вершину 3 и оценка кратчайшего пути равна 5 + 7 = 12.
Иначе говоря, D[4] := min{D[4], D[3]+C[3,4]} = min{∞, 5+7} =
min{∞,12} = 12. Аналогично меняется оценка длины кратчайшего
пути до вершины 5 – она теперь равна 13 (путь через вершину 3).
После пересчета оценок расстояний (длин кратчайших путей) граф и массив D выглядят так:
D = [0, 7, 5, 12, 13, ∞, ∞, ∞]
Снова ищем вершину для того, чтобы ее пометить. Для этого
в массиве D выбираем наименьший из тех элементов, которые не
соответствуют помеченным вершинам (это все элементы, кроме
первого и третьего). Таким элементом будет второй: для него
оценка расстояния равна 7. Помечаем его и пересчитываем оценки расстояний.
Для вершин 7 и 8 они не изменятся (как были равны бесконечности, так и будут). До вершины 5 по-прежнему короче путь
через вершину 3, нежели через добавленную вершину 2. А оценки расстояний до вершин 4 и 6 необходимо скорректировать: до
вершины 4 короче оказывается путь через вершину 2 (был равен
12, стал равен 11), а до вершины 6 оценка расстояния была равна
бесконечности, а теперь в нее можно попасть через вершину 2 (и
соответствующее расстояние равно 13). После этого имеем следующий граф матрицу оценок:
D = [0, 7, 5, 11, 13, 13, ∞, ∞]
25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Продолжаем помечать вершины. Из массива D выбираем
элемент с номером 4 (для соответствующей вершины оценка расстояния оказывается наименьшей среди непомеченных). Помечаем ее, выполняем пересчет оценок расстояний:
D = [0, 7, 5, 11, 13, 13, 20, 21]
Помечать вершины продолжаем до тех пор, пока все они не
окажутся помеченными. Стоит обратить внимание на то, что
оценки для помеченных вершин являются точными и не меняются при пометке новых вершин.
Итак, на следующем шаге можно пометить либо вершину 5,
либо вершину 6 (пятый и шестой элементы массива D одинаковы
и равны 13, поэтому можно выбрать любую из данных вершин).
Пометим вершину 5. С учетом того, что была помечена новая
вершина, осуществляем пересчет оценок расстояний:
D = [0, 7, 5, 11, 13, 13, 20, 21]
Заметим, что при этом массив D не изменился. Это означает,
что пути, проходящие через вершину 5 до непомеченных вершин,
не короче рассмотренных ранее путей, которые эту вершину не
содержат. Далее осталось выбрать минимальный из элементов
массива D с номерами 6, 7, 8 (они соответствуют непомеченным
вершинам). Таким является элемент с номером 6, соответственно
шестую вершину мы и помечаем. При пересчете оценок расстояний они меняется только оценка длины пути до вершины 8 (теперь короче будет путь через вершину 6), остальные остаются без
изменений:
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
D = [0, 7, 5, 11, 13, 13, 20, 20]
Осталось две непомеченные вершины: 7 и 8. Соответствующие элементы массива оценок D равны, поэтому можно пометить любую из них. Пометим вершину 7. Это не изменит массива оценок расстояний:
D = [0, 7, 5, 11, 13, 13, 20, 20]
Теперь осталась только вершина 8, которую нужно просто
пометить. Так как непомеченных вершин после этого не остается,
то и пересчитывать оценки расстояний не нужно. В результате
получаем следующий граф и массив оценок расстояний (D):
D = [0, 7, 5, 11, 13, 13, 20, 20]
Теперь мы можем определить длину кратчайшего пути от
вершины 1 до любой другой вершины. Например, длина кратчайшего пути от вершины 1 до вершины 7 равна 20 (седьмой
элемент массива D). Однако это не дает нам самого пути, а лишь
показывает его длину.
Оценим трудоемкость алгоритма. Работу алгоритма можно
условно разделить на N шагов, на каждом из которых мы помечаем вершину. При пометке вершины мы пересчитываем оценки
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
расстояний до вершин, что требует порядка N действий на каждом шаге. Итого получается порядка N 2 действий. Таким образом, можем сделать вывод, что порядок роста трудоемкости составляет N 2.
Вообще говоря, ожидать меньшей трудоемкости не представляется возможным. Действительно, при построении кратчайшего
пути мы должны учитывать все длины (веса) ребер, что требует
просмотра матрицы весов размера NxN, что требует уже порядка
N 2 действий.
Теперь рассмотрим несколько другую ситуацию: пусть на
дорогах между городами установлено одностороннее движение.
В принципе, между двумя городами могут существовать и прямой, и обратный путь, но ничто не мешает им иметь разную длину (иначе говоря, длина дороги из города v в город w может быть
не равна длине дороги из w в v). В этом случае в матрице весов
элемент C[i,j] может быть не равен элементу C[j,i] (в случае двустороннего движения эти элементы были равны, то есть матрица
была симметричной относительно главной диагонали). Требуется
найти длины кратчайших путей от выделенной вершины до всех
остальных вершин.
Если нет ребра из вершины v до вершины w (ориентированное ребро чаще называют дугой), то удобно приписывать ему вес,
равный бесконечности.
Понятно, что для решения данной задачи можно использовать тот же самый алгоритм Дейкстры. Обратите внимание, что
при описании алгоритма Дейкстры мы нигде не опирались на
симметричность путей (то есть на равенство C[i,j] = C[j,i]), поэтому алгоритм будет давать решение и в случае однонаправленных (ориентированных) дорог.
Граф, в котором каждое из ребер имеет направление, называется ориентированным. Если каждому из ориентированных ребер
(каждой из дуг) приписан вес, то такой граф называется взвешенным ориентированным графом.
Итак, алгоритм Дейкстры предназначен для поиска длины
кратчайшего пути от выделенной вершины до всех остальных как
в неориентированном ("обычном") графе, так и в ориентированном, в том случае, если веса ребер (дуг) положительны.
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм Форда – Беллмана
Рассмотренный выше алгоритм (алгоритм Дейкстры) использовал достаточно простую идею: оценками расстояний были длины кратчайших путей с использованием в качестве промежуточных вершин только помеченных, а набор помеченных вершин постоянно расширялся до тех пор, пока не охватывал все вершины
графа (при этом все оценки расстояний оказывались точными).
Следующий алгоритм (алгоритм Форда – Беллмана) будет
также основан на достаточно простой идее: будем последовательно находить длины кратчайших путей от выделенной вершины до всех остальных вершин с количеством промежуточных
вершин не более k (последовательно для всех k от 0 до N–2). Тогда, когда будет рассмотрен случай k = N–2, мы получим точные
оценки. Действительно, кратчайший путь не может содержать
более N–1 ребер (он соответствует случаю N–2 пересадок), иначе
он содержит цикл, а поэтому не будет являться кратчайшим.
Ключевым моментом является переход от наибольшего количества промежуточных вершин k к количеству k+1. Сделаем
обозначение: пусть D[w,k] – длина кратчайшего пути от выделенной вершины v до вершины w с использованием не более k
пересадок (промежуточных вершин). Тогда каким образом можно
добраться по кратчайшему пути от v до w с использованием не
более k+1 пересадок? Очевидно, что достаточно рассмотреть
имеющийся путь от v до w с использованием не более k пересадок, а также все пути, состоящие из пути от v до вершины i (i от 1
до N) с добавлением ребра (i, w), после чего выбрать из рассмотренных путей самый короткий.
Итак, имеем:
D[w,k+1] = min{D[w,k], D[i,k]+C[i,w] для всех i от 1 до N}.
Пересчет оценок расстояний продолжаем, пока k не примет
значение N–2. После этого оценки окажутся точными. Алгоритм
можно описать так:
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 1:
k:=0;
Для всех i от 1 до N: D[i,0]:=C[v,i]
{первоначальные оценки расстояний – длины
путей без пересадок}
Пока k<N–1 выполнять шаг 2;
Шаг 2:
Для всех w от 1 до N выполняем следующие
действия:
D[w,k+1]:=min{D[w,k], D[i,k]+C[i,w]
для всех i от 1 до N};
{выполняем пересчет оценок расстояний}
k:=k+1; {увеличиваем k на 1}
Понятно, что аналогичный алгоритм можно применить и для
нахождения длины кратчайшего пути во взвешенном ориентированном графе.
Итак, алгоритм Форда – Беллмана также основан на достаточно простой идее. Однако (в отличие от алгоритма Дейкстры)
этот алгоритма имеет достаточно высокую трудоемкость: она составляет порядка N 3 (где N – количество вершин в графе), поэтому проигрывает по трудоемкости алгоритму Дейкстры.
Поиск длин кратчайших путей между
всеми вершинами. Алгоритм Флойда
Рассмотренные выше алгоритмы были предназначены для
поиска длины кратчайшего пути между двумя выделенными
вершинами. В качестве "побочного продукта" они давали длины
кратчайших путей от выделенной вершины до всех остальных
вершин графа.
Решим еще более общую задачу: найдем длины кратчайших
путей между каждой парой вершин в графе (без разницы, является он ориентированным или нет). В принципе, можно было бы,
последовательно выбирая в качестве начальной все вершины
графа, N раз применить алгоритм Дейкстры (добившись оценки
трудоемкости порядка N3). Но на практике обычно используют
30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
другой алгоритм с тем же порядком роста трудоемкости – алгоритм Флойда.
Данный алгоритм также основан на идее последовательного
пересчета оценок расстояний. Обозначим через D[i,j,k] длину
кратчайшего пути из вершины i в вершину j с использованием
промежуточных вершин из множества [1,…,k] (то есть, с номерами от 1 до k). Переход от D[i,j,k] к D[i,j,k+1] осуществляется
следующим образом: кратчайший путь с промежуточными вершинами 1, …, k+1 может не содержать вершины k (тогда он равен D[i,j,k]), а может содержать, тогда он разбивается на кратчайший путь от вершины i до вершины с номером k+1 и на кратчайший путь от вершины k+1 до вершины j. Учитывая сказанное
выше, формулу пересчета можно записать так:
D[i,j,k+1] = min{ D[i,j,k], D[i,k+1,k]+ D[k+1,j,k]}.
Алгоритм можно записать следующим образом:
Шаг 1:
Для всех i от 1 до N и для всех j от 1 до N
выполняем:
D[i,j,0] := C[i,j];
{начальные оценки расстояний}
Шаг 2:
Для всех k от 1 до N выполняем следующие
действия:
Для всех х i от 1 до N
и для всех j от 1 до N выполняем:
D[i,j,k+1]=min{D[i,j,k];D[i,k+1,k]+D[k+1,j,k]}
В результате работы данного алгоритма длины кратчайших
расстояний между вершинами i и j будут находиться в элементах
D[i,j,N]. Понятно, что можно оценки все время хранить в одном и
том же двумерном массиве D.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Деревья
Основные определения
Одним из частных случаев графов является дерево. С этим
понятием мы уже сталкивались в главе "Структуры данных", когда работали с бинарными деревьями. Действительно, приведенную тогда схему можно считать графом, в котором узлы дерева
являются вершинами графа, а узел соединяется с потомками ребрами. При этом от любого узла по таким ребрам можно добраться
до любого другого (более формально это означает, что рассматриваемый граф является связным), причем единственным способом. Однако слово "бинарное", очевидно, уже предполагает некоторое дополнительное условие, накладываемое на дерево. Дадим
определение дерева в общем виде.
Дерево – это связный граф без циклов. Несложно убедиться в
том, что бинарное дерево является деревом и по только что приведенному определению. Примерами деревьев являются и молекулы некоторых химических веществ, например предельных углеводородов, при этом атомы являются вершинами, а связи между ними – ребрами (именно с рассмотрения такого рода графов в
середине XIX века и началось активное изучение деревьев и их
свойств). Пример дерева приведен на рисунке 1.
Рис. 9. Пример дерева
Данное выше определение дерева не является единственным. Приведем еще несколько эквивалентных определений (эквивалентность в данном случае означает, что из любого приведенного определения можно получить другое):
• Дерево – это связный граф, в котором любые две вершины соединены единственным простым путем.
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
• Дерево – это связный граф, в котором количество
ребер на 1 меньше количества вершин.
• Дерево – это граф без циклов, в котором количество
ребер на 1 меньше количества вершин.
• Дерево – это граф без циклов, в котором при соединении любой пары несмежных вершин образуется цикл.
И этот список можно продолжать. С другой стороны, приведенные выше определения можно рассматривать как свойства деревьев.
Понятно, что дерево можно получить из любого связного
графа. Для этого можно выполнить следующие действия: пока
граф содержит циклы, выбираем один из них и удаляем в нем одно из ребер. Например, если есть связная сеть дорог, соединяющая несколько городов, то пока эта сеть содержит циклы, мы можем закрывать входящие в циклы дороги (по одной). Понятно,
что при этом граф остается связным. Действительно, если произвольные две вершины (два города) были соединены путем, то после удаления ребра (дороги) эти вершины все равно оказываются
связанными путем: если путь проходил через удаленное ребро,
которое входило в цикл, то из одной вершины в другую все равно
существует путь "в объезд" удаленного ребра.
Полученное дерево, очевидно, будет содержать те же самые
вершины, что и исходный граф, а ребра дерева являлись изначально ребрами исходного графа. Такого рода дерево называется
остовом (или каркасом).
Понятно, что остовов в графе может быть несколько. На рисунке 10 приведен пример графа (1) и нескольких его остовов (2,
3 и 4):
Рис. 10. Граф и его остовы
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В графе с достаточно большим количеством ребер остовов
может быть очень и очень много. Одной из задач будет нахождение среди всего множества остовов тех, которые обладают определенным свойством. Решением такого рода задач мы сейчас и
займемся.
Остов минимального веса
Рассмотрим следующую задачу. Пусть есть некоторый набор
деревень, между некоторыми из которых проложены грунтовые
дороги, образующие связную систему (то есть из любой деревни
можно добраться до любой другой, возможно, "транзитом" через
какие-то промежуточные деревни). Для того чтобы обеспечить
связь между деревнями в межсезонье (когда грунтовые дороги
становятся неприспособленными для езды), решено некоторые из
грунтовых дорог покрыть асфальтом так, чтобы из любой деревни можно было проехать до любой другой, используя только заасфальтированные дороги. При этом стоимость асфальтирования
разных дорог может быть различной (например, зависеть от длины дороги и особенностей рельефа). Наша задача: построить
связную систему асфальтированных дорог с наименьшими расходами.
Переведем условие задачи на язык теории графов. Итак, деревни можно считать вершинами, а грунтовые дороги между ними – ребрами. Так как из любой деревни можно было проехать до
любой другой, то такой граф является связным. Также мы имеем
некоторую дополнительную информацию: знаем, сколько стоит
асфальтирование каждой из дорог. В этом случае говорят, что
каждому ребру приписан определенный вес (а граф называется
взвешенным):
Рис. 11. Взвешенный граф
34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Чаще всего веса ребер заносятся в двумерный массив, который называется матрицей весов: в ячейку на пересечении i-й
строки и j-го столбца записывают вес ребра между i-й и j-й вершиной. Иногда для удобства считают, что в графе каждая вершина соединена с каждой, но вес несуществующих в исходном графе ребер равен бесконечности. Применительно к задаче об асфальтировании дорог это можно сформулировать так: постройка
асфальтированной дороги между двумя деревнями, не соединенными между собой грунтовой дорогой, требует бесконечных (или
крайне больших) затрат. Для графа, приведенного на рисунке 3,
матрица весов будет иметь следующий вид (символом "∞" обозначен бесконечный вес ребра):
0
8
6
8
∞
8
0
6
∞
∞
6
6
0
5
7
8 ∞
∞ ∞
5 7
0 10
10 0
Рис. 12. Матрица весов
Такие "несуществующие" ребра (дороги) с бесконечными весами, как легко заметить, не будут входить в искомую минимальную сеть дорог. Действительно, наличие в сети такого ребра автоматически делает ее общую стоимость бесконечной, но понятно,
что мы можем построить сеть асфальтированных дорог с меньшими затратами, просто взяв совершенно произвольный остов.
Почему же сеть дорог минимальной стоимости мы будем искать именно среди остовов? Ответ достаточно очевиден. Действительно, полученная сеть дорог должна связывать все деревни
друг с другом, поэтому мы должны найти связный граф. Также
эта сеть дорог минимальной не должна содержать циклов, иначе
мы могли бы выбросить одну из дорог (то есть не асфальтировать
одну из грунтовых дорог) в данном цикле и получить сеть дорог
меньшей стоимости. Итак, искомая сеть дорог минимальной
стоимости действительно должна быть связным графом без циклов, то есть деревом. А так как это дерево содержит все вершины
(соединяет все деревни), то это остов.
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Таким образом, задачу можно сформулировать следующим
образом: в заданном взвешенном графе найти остов минимального веса. Рассмотрим два способа решения данной задачи: алгоритм Прима и алгоритм Краскала.
Алгоритм Прима
Идея алгоритма достаточно проста. Будем строить остов, постепенно добавляя по одному ребру. Первым в остов включаем
ребро с наименьшим весом (в нашей задаче: асфальтируем ту дорогу, покрытие которой асфальтом потребует наименьших затрат). Далее на каждом шаге присоединяем к сети не рассмотренное ранее ребро минимального веса, причем выбираем минимальное среди тех ребер, добавление которых к сети не образует
цикла.
Иначе говоря, на каждом шаге мы имеем дерево, к которому
присоединяем ребро (с вершиной) так, чтобы полученная сеть оставалась деревом, причем добавляем наиболее "легкое" из таких
ребер.
Как добиться того, чтобы при добавлении ребра не образовывался цикл? Очевидно, для этого мы должны проводить ребро от
уже построенной сети к одной из тех вершин, которые мы еще не
рассматривали.
Представим себе рабочих, которые асфальтируют дороги по
данному алгоритму. В самом начале работы они заасфальтировали дорогу, затраты на покрытие асфальтом которой самые низкие
(то есть покрыли асфальтом одну из дорог, затратив на это минимум средств), соединив таким образом какие-то две деревни. А
дальше они смотрят, какую деревню из тех, до которых еще не
достроена сеть асфальтированных дорог, можно было бы присоединить к сети с наименьшими затратами. Дорога, обладающая
данными условиями, покрывается асфальтом, после чего рабочие
снова ищут новую деревню, чтобы присоединить к сети, "протянув" к ней дорогу. Эту операцию последовательно проделывают
до тех пор, пока все деревни не окажутся присоединенными к сети асфальтированных дорог.
Может возникнуть вполне естественный вопрос: находит ли
этот алгоритм действительно остов минимального веса. Да, нахо36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дит, и это можно строго доказать. Однако на этом мы останавливаться не будем.
Вместо этого уделим некоторое внимание организации поиска нового добавляемого ребра. Действительно, эту операцию
приходится проделывать на каждом шаге алгоритма. Добавляемое ребро соединяет одну из рассмотренных ранее вершин с одной из нерассмотренных. Поэтому кажется вполне естественным
ввести два множества: множество рассмотренных вершин (X) и
множество нерассмотренных вершин (Y). Перед началом работы
алгоритма множество X пусто, а Y содержит все вершины (действительно, мы ведь еще не рассмотрели ни одну из вершин). На
первом шаге (при включении в сеть первого ребра) в множество
X включаем две вершины, связанные добавляемым ребром наименьшего веса, и, соответственно, исключаем эти две вершины из
множества Y. А далее на каждом шаге мы делаем следующее:
рассматриваем все ребра, соединяющие вершины множества X с
вершинами множества Y, и выбираем из них то, которое имеет
меньший вес. Пусть оно соединяет вершину x (из множества X) с
вершиной y (из Y). Добавляем ребро (x, y) к сети, вершину y добавляем к множеству X и исключаем из множества Y. Так продолжаем делать до тех пор, пока в множестве Y не останется
вершин.
Множества X и Y можно организовать с помощью списков,
массивов или переменных множественного типа.
Как же найти ребро минимального веса среди тех, которые
соединяют множество X с множеством Y? Для решения этой задачи можно рассмотреть те элементы матрицы весов, которые
стоят на пересечении строк с номерами из X и столбцов с номерами из Y, и найти среди них наименьший. Иначе говоря, ищем
наименьший элемент в таблице, получающейся из матрицы весов
исходного графа выкидыванием всех строк с номерами, не содержащимися в X, и столбцов с номерами, не содержащимися в
Y. Если такой элемент находится в строке с номером x и столбце
с номером y, то ребро (x,y) – искомое.
Обобщая изложенное выше, алгоритм Прима можно в общих
чертах описать следующим образом:
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
X – пустое множество;
Y – содержит все вершины;
Найти в матрице весов наименьший элемент:
x = номер соответствующей строки,
y = номер столбца;
Добавить ребро (x,y) в сеть;
Добавить x и y в X;
Исключить x и y из Y;
while (Y не пусто) do
begin
Найти в матрице весов наименьший из элементов на
пересечении строк с номерами из X и столбцов с номерами из Y:
x = номер строки, y = номер столбца;
Добавить ребро (x,y) в сеть;
Добавить y в X;
Исключить y из Y;
end;
Проследим ход выполнения алгоритма Прима на примере.
Пусть имеется сеть дорог следующего вида:
Вначале множество X пусто, множество Y содержит все вершины:
X = {}; Y = {1, 2, 3, 4, 5, 6, 7}.
Начинаем построения остова минимального веса с выбора
самого "легкого" ребра. Этим свойством обладает ребро, соединяющее вершины 1 и 5 (его вес равен 5). Добавляем его к остову,
а вершины 1 и 5 добавляем к множеству X, исключив их при этом
из множества Y:
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
X = {1, 5}; Y = {2, 3, 4, 6, 7}
Теперь посмотрим, какую вершину можно было бы соединить ребром с имеющейся сетью, затратив при этом минимум
средств. Для этого рассмотрим все ребра с одной вершиной из
множества X, а второй – из множества Y. Таких ребер у нас три:
(1,2), (5, 4) и (5, 6). Из них выберем ребро наименьшего веса – это
ребро (1,2). Добавляем это ребро к остову, а вершину 2 добавляем
в множество X и исключаем из множества Y:
X = {1, 2, 5}; Y = {3, 4, 6, 7}
Снова ищем среди ребер, соединяющих вершины множества
X с вершинами множества Y, то, которое имеет наименьший вес.
Среди таких ребер ((2,3); (2,4); (5,4) и (5,6)) наименьший вес (9)
имеет ребро (2,3), которое мы и добавляем к остову. Вершина 3 в
свою очередь добавляется к X и исключается из Y:
X = {1, 2, 3, 5}; Y = {4, 6, 7}
Вершины множества X соединяют с вершинами множества Y
следующие ребра: (2,4), (3,4), (3,6), (3,7), (5,4) и (5,6). Наименьшим весом среди них (6) обладает ребро (3,7). Его включаем в
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
остов, вершину 7 включаем в множество X и удаляем из множества Y:
X = {1, 2, 3, 5, 7}; Y = {4, 6}
Ищем ребра, связывающие множества X и Y: (2,4), (3,4),
(3,6), (5,4), (5,6) и (7,6). Из них наименьший вес имеет ребро (3,4).
Добавляем это ребро к остову, переносим вершину 4 из множества X в множество Y:
X = {1, 2, 3, 4, 5, 7}; Y = {6}
Во множестве Y осталась последняя вершина – 6. Она связана с вершинами множества X такими ребрами: (3,6), (4,6), (5,6) и
(7,6). Самым "легким" из этих ребер является (4,6), оно и будет
последним включенным в остов ребром. Вершину 6 переносим в
множество X:
X = {1, 2, 3, 4, 5, 6, 7}; Y = {}
Множество Y пусто, поэтому алгоритм заканчивает свою работу. Искомый остов выглядит следующим образом:
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вес остова (суммарный вес входящих в него ребер) в нашем
случае составляет
5+7+9+6+7+6=
Упражнение.
Реализуйте алгоритм Прима в виде программы.
Алгоритм Краскала
Рассмотрим второй способ решения той же задачи – алгоритм Краскала. Мы снова будем добавлять к остову по одному
ребру, однако отличие нового алгоритма от алгоритма Прима заключается в том, что на каждом шаге уже построенная сеть будет
не деревом, а просто графом без циклов.
В основе алгоритма лежит тоже достаточно простая идея: на
каждом шаге включаем в построенный подграф ребро с наименьшим весом среди тех, добавление которых к подграфу не образует цикла. Начинаем строить остов так же, как и в алгоритме
Прима: берем все вершины исходного графа, ребер пока не проведено. Добавление ребер продолжаем до тех пор, пока их количество не станет на 1 меньше количества вершин.
Разберемся, почему мы всегда сможем довести это до конца.
Ситуация, когда ребро добавить не удается, возможна в следующих случаях:
1) больше нет ребер. Но тогда количество вершин в исходном графе превышает количество ребер более, чем на 1, а значит,
остова в нем вообще построить нельзя;
2) добавление любого ребра образует цикл. Но тогда это уже
дерево с вершинами, являющимися также вершинами исходного
графа, то есть остов.
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Итак, алгоритм действительно строит остов. Как и при рассмотрении алгоритма Прима, в данном случае мы не будем останавливаться на доказательстве утверждения, что алгоритм Краскала строит остов минимального веса (отметим только то, что оно
верно).
На каждом шаге требуется выбирать ребро, учитывая два условия (критерия):
• оно должно иметь как можно меньший вес;
• оно не должно образовывать цикла.
Решение первой задачи может упростить предварительная
сортировка набора ребер в порядке увеличения веса (для этого
можно воспользоваться любым стандартным быстрым алгоритмом сортировки). Добавление ребер можно производить следующим образом: движемся по списку ребер от начала к концу,
каждый раз проверяем, не образует ли очередное ребро цикл при
добавлении к построенному подграфу, и если не образует, то добавляем его к подграфу. Так продолжаем просматривать ребра до
тех пор, пока их не наберется достаточное количество (на 1
меньше количества вершин).
Понятно, что уже просмотренные ребра нам уже и не понадобятся в дальнейшем: если бы оказалось, что оно нам подошло
через некоторое время после того, как мы его просмотрели, то это
означало бы, что его добавление не образует цикла. Но тогда его
добавление не образовывало цикла и тогда, когда мы его ранее
просматривали, а в этом случае мы бы включили его в подграф.
Вторая промежуточная задача, которую необходимо решать
при рассмотрении очередного ребра, – проверка, не образует ли
ребро цикла при добавлении в уже построенный к настоящему
моменту подграф. Прежде чем описать алгоритм проверки, еще
раз рассмотрим вид построенного подграфа. В этом подграфе на
каждом шаге алгоритма Краскала нет циклов. Такой граф иногда
называют лесом (рис. 13).
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рис. 5. Граф без циклов (лес)
Смысл такого наименования становится понятен, если обратить внимание на то, что любой граф без циклов состоит из деревьев: каждая компонента связности является связным графом и,
как уже было сказано, не содержит циклов (поэтому по определению является деревом). Граф из одной изолированной вершины тоже можно считать деревом. Итак, на каждом шаге алгоритма построенный подграф является лесом, состоящим из некоторого количества деревьев.
На очередном шаге, очевидно, нельзя добавлять ребро, соединяющее две вершины одного дерева, иначе образуется цикл. С
другой стороны, добавление ребра между двумя вершинами,
принадлежащими разным деревьям, цикла не образует, а соответствующие деревья объединяются в одно. Поэтому нужно какимто образом выделять вершины, принадлежащие одному дереву.
Эту задачу можно решить введением массива меток вершин
графа. В роли меток будут выступать обычные натуральные числа. Вершины, принадлежащие одному дереву, должны иметь
одинаковые метки, принадлежащие разным деревьям – разные
метки.
Реализовать это можно следующим образом: заведем массив
меток (M), количество элементов в котором равно количеству
вершин, а в k-й элемент массива (M[k]) будем записывать метку kй вершины. В начале работы алгоритма (до того, как мы начали
добавлять ребра) всем вершинам присвоим разные метки (например, это можно сделать следующим образом: в качестве метки каждой вершине сопоставим номер самой этой вершины). Проверка, образует ли ребро цикл, становится совсем простой: если ребро
соединяет две вершины с одинаковыми метками, то добавление
ребра образует цикл, если же связываемые ребром вершины имеют разные метки, то добавление такого ребра цикла не образует.
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При добавлении ребра, соединяющего вершины с разными
метками, деревья, соответствующие этим меткам, объединяются
в одно. Поэтому мы должны всем вершинам нового дерева присвоить одну и ту же метку. Например, при объединении дерева,
вершины которого имеют метки, равные x, и дерева с вершинами,
имеющими метки y, образуется новое дерево. Присвоить всем
вершинам нового дерева одинаковые метки очень просто: достаточно в массиве меток заменить все метки y на метки x (а уже
имеющиеся метки x оставить без изменения).
В конце работы алгоритма, как несложно заметить, все вершины будут иметь одну и ту же метку (что как раз и будет соответствовать тому, что все вершины принадлежат одному дереву –
остову).
С учетом всего сказанного схематически опишем алгоритм
Краскала следующим образом:
Шаг 0)
Упорядочить ребра по возрастанию весов;
В начале подграф состоит просто
из вершин графа;
M – массив из N элементов;
M[k]:=k для всех k от 1 до N;
{заполнили массив меток}
Шаг 1)
Просматриваем массив ребер в направлении
возрастания весов.
Для каждого очередного ребра (x,y)
проверяем равенство меток:
Если M[x]=M[y], то смотрим следующее
по порядку ребро(продолжаем просмотр),
иначе переходим к шагу 2 (добавление
ребра (x,y)).
Шаг 2)
Добавляем ребро (x,y) к подграфу;
Пусть M[y] = t (метка вершины y);
Заменяем в массиве M все элементы,
равные t, на M[x]
(для всех k: если M[k] = t то M[k]:=M[x]).
44
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 3)
Если количество добавленных к подграфу ребер меньше
N–1,
то повторяем шаги 1-2 (при этом поиск очередного
ребра начинаем с того места, на котором на предыдущем
шаге закончили).
Продемонстрируем работу алгоритма Краскала на том же
примере, на котором показывали работу алгоритма Прима:
Упорядочим ребра по возрастанию весов:
(1,5); (3,7); (4,6); (1,2); (3,4); (6,7); (2,3); (3,6); (2,4);
(4,5); (5,6)
Создадим массив меток и заполним его просто номерами
вершин:
M = [1, 2, 3, 4, 5, 6, 7]
Начинаем работу основной части алгоритма. Берем самое
первое ребро: (1,5). Вершины 1 и 5 имеют разные метки, поэтому
добавление данного ребра не образует цикла. Добавляем ребро к
подграфу, а все метки, равные меткам вершины 5, заменяем на
метки, равные меткам вершины 1:
M = [1, 2, 3, 4, 1, 6, 7]
Продолжаем просматривать последовательность ребер. Очередным будет ребро (3,7). Метки вершин 3 и 7 различны, поэтому
45
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ребро (3,7) можно добавить к подграфу. После этого все метки,
равные меткам вершины 7 (они равны 7), заменить на метки, равные меткам вершины 3 (они равны 3).
M = [1, 2, 3, 4, 1, 6, 3]
Аналогичным образом добавляем к подграфу и ребро (4,6).
При этом метку вершины 6 заменяем на метку вершины 4:
M = [1, 2, 3, 4, 1, 4, 3]
Следующим в последовательности идет ребро (1,2). Метки
вершин 1 и 2 различны, поэтому данное ребро можем добавлять к
подграфу. Метку вершины 2 заменяем на метку вершины 1:
M = [1, 1, 3, 4, 1, 4, 3]
Всего на данном этапе насчитывается три различные метки в
массиве (1, 3 и 4), что соответствует наличию в подграфе трех составляющих его деревьев.
Далее в списке ребер следует ребро (3,4). Оно тоже не образует цикла при добавлении (это легко проверить, сравнив метки
46
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вершин 3 и 4), поэтому добавляем его к подграфу. После этого
заменяем все метки, равные метке вершины 4 (она равна 4), на
метки, равные метке вершине 3 (она равна 3):
M = [1, 1, 3, 3, 1, 3, 3]
Берем следующее ребро из списка: (6,7). Метки вершин 6 и 7
равны (они равны 3), значит, добавление ребра (6,7) приводит к
появлению цикла. Поэтому ребро (6,7) мы пропускаем и берем
следующее: (2,3). Теперь уже метки вершин 2 и 3 различны, поэтому ребро (2,3) можно добавить к подграфу. Соответствующим
образом изменяем метки, равные метке вершины 3, на метку
вершины 2:
M = [1, 1, 1, 1, 1, 1, 1]
Количество ребер в подграфе равно 6, что на 1 меньше количества вершин, поэтому на этом алгоритм заканчивает свою
работу. Искомый подграф (остов) получился таким:
Заметим, что при использовании алгоритма Краскала ребра
добавляются к остову совершенно в другом порядке (по сравнению с ходом работы алгоритма Прима).
47
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Остов получился таким же, как и в случае использования
алгоритма Прима. Но не нужно думать, что результат работы алгоритмов всегда будет одним и тем же. Ведь остов минимального
веса обладает следующим свойством: остова еще меньшего веса
просто не существует. Однако минимальных по весу остовов может быть и несколько (понятно, что они будут иметь один и тот
же вес). Но ведь в задаче и не нужно было находить все такие остовы – достаточно было ограничиться нахождением одного остова минимального веса.
Конечно, в том случае, если остов минимального веса в графе
всего один (как в нашем случае), то оба алгоритма дадут один и
тот же результат – как в случае использования алгоритма Краскала, так и в случае применения алгоритма Прима, мы получим
один и тот же остов минимального веса. Однако если минимальных остовов несколько, то разные алгоритмы их нахождения могут найти разные остовы (плохого в этом ничего нет).
Кодирование деревьев
Ранее были рассмотрены различные формы представления
графов в памяти компьютера. Например, для хранения графа
можно использовать матрицу смежности. Однако в случае дерева
это вряд ли можно назвать хорошей идеей: в дереве не так уж и
много ребер (на 1 меньше количества вершин), поэтому вводить
для хранения дерева матрицу смежности было бы не очень удобно (матрица смежности будет состоять из очень большого количества нулей и малого количества единиц).
Гораздо проще перечислить ребра дерева. Для этого можно
использовать перечень ребер. Если просто перечислять все ребра
дерева, то нужно запомнить 2(N–1) чисел (при этом N – количество вершин в дереве). Используя представление дерева в виде
списка ссылок (списка связи), объем запоминаемой информации
в данном случае не уменьшается. Однако существует способ, который позволяет хранить дерево в виде набора из N–2 чисел.
Этот способ представления (кодирования) деревьев называется
кодом Прюфера.
Опишем два алгоритма. Первый из них будет предназначаться для кодирования дерева, то есть строить по данному дереву
некоторую последовательность чисел. Второй будет выполнять
48
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
обратное преобразование: по последовательности символов восстанавливать дерево, которому она (последовательность) соответствует. Условно их будем называть алгоритмом кодирования
и алгоритмом декодирования соответственно.
В алгоритме используется тот факт, что в любом дереве обязательно найдется висячая вершина (то есть вершина, из которой
выходит только одно ребро - вершина степени 1). Факт достаточно очевиден, и мы оставим его без доказательства. Также висячую вершину еще называют листом.
Алгоритм кодирования:
Обозначения:
Пусть есть дерево, его вершины имеют
номера 1, 2, ..., N.
Будем строить по нему последовательность
чисел S. В начале работы последовательность
S пуста.
Алгоритм:
Пока в дереве больше одного ребра
выполнять следующие действия:
1) Найти в дереве висячую вершину (лист)
с наименьшим номером; пусть ее номер
равен v.
Номер вершины, с которой связана
вершина v, равен w.
2) Добавить номер вершины w
к последовательности S.
3) Удалить из дерева вершину v
вместе с ребром (v,w).
Продемонстрируем работу алгоритма на примере. Пусть дерево имеет следующий вид:
49
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Последовательность S пока пуста: S = [ ].
На первом шаге находим висячую вершину с наименьшим
номером. В приведенном выше дереве это вершина с номером 4.
С ней связана вершина с номером 2. Добавляем номер вершины 2
к последовательности S, а вершину 4 и ребро (4,2) удаляем из дерева:
S = [2]
Продолжаем выполнение алгоритма. Очередной висячей
вершиной с наименьшим номером будет вершина 2, она связана с
вершиной 1. Добавляем 1 к последовательности S, удаляем ребро
(2,1) из дерева:
S = [2, 1]
50
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Снова выбираем висячую вершину с наименьшим номером –
это вершина 6, связанная ребром с вершиной 5. Добавляем 5 к
последовательности S, удаляем из дерева вершину 6 с ребром
(6,5):
S = [2, 1, 5]
Выполняем аналогичные действия и далее. Результат работы
алгоритма:
После четвертого шага (найдена вершина 4, в последовательность добавлен номер вершины 8, вершина 4 и ребро (4,8) удалены):
S = [2, 1, 5, 8]
После пятого шага (найдена вершина 7, в последовательность
добавлен номер вершины 3, вершина 7 и ребро (7,3) удалены) результат работы такой:
S = [2, 1, 5, 8, 3]
51
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Наконец, после последнего шага (наименьший номер имеет
висячая вершина 3, в последовательность добавлен номер связанной с ней вершины 1, вершина 3 и ребро (3,1) удалены) результат работы алгоритма следующий:
S = [2, 1, 5, 8, 3, 1]
Осталось одно ребро, поэтому алгоритм заканчивает свою
работу. Построенная последовательность S = [2, 1, 5, 8, 3, 1] называется кодом Прюфера данного дерева. Теперь покажем, как
по аналогичной последовательности чисел (по коду Прюфера)
восстановить соответствующее дерево.
Итак, алгоритм декодирования:
Исходные данные:
S – код Прюфера (последовательность чисел)
Шаг 1:
Определить количество вершин:
оно на 2 больше количества чисел
в последовательности S.
Пусть это количество вершин равно N.
Шаг 2:
Создаем граф из N изолированных вершин
(то есть просто отмечаем N вершин).
Нумеруем их числами от 1, 2, ..., N.
Шаг 3:
Создаем список L, который в дальнейшем
будем называть списком висячих вершин.
Заносим в список L те числа от 1 до N,
которых нет в коде Прюфера (S).
Шаг 4:
Пусть p – первое число в последовательности S
(в коде Прюфера);
e – наименьшее число в списке висячих
вершин L;
Добавить (провести) ребро (p,e).
52
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 5:
Удалить число e из списка висячих вершин L.
Шаг 6:
Если осталось две вершины (в сумме в S и L),
то добавляем ребро, соединяющее эти две
вершины, и переходим к шагу 9,
иначе удаляем p из последовательности S.
Шаг 7:
Если p больше не встречается
в последовательности S,
то добавляем p к списку L.
Шаг 8:
Переходим к шагу 4
Шаг 9:
Заканчиваем работу алгоритма
Проследим за работой алгоритма на конкретном примере. В
качестве последовательности S возьмем построенный ранее код
Прюфера: S = [2, 1, 5, 8, 3, 1].
Начинаем последовательно выполнять шаги алгоритма. Вначале определяем количество вершин в дереве: так как последовательность S состоит из 6 чисел, то количество вершин равно
N = 6 + 2 = 8. Отмечаем 8 вершин, нумеруем их числами от 1 до
8. Создаем список L и помещаем в него те числа от 1 до 8, которых нет в последовательности S, получаем: L = [4, 6, 7]. На данном этапе имеем следующую ситуацию:
S = [2, 1, 5, 8, 3, 1]
L = [4, 6, 7]
53
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В последовательности S берем первое число: p = 2, в списке
L находим наименьшее число: e = 4. Проводим ребро (2,4), после
чего удаляем e = 4 из списка L. Осталось более 2 вершин, поэтому удаляем p = 2 из последовательности S.
Так как p = 2 больше не встречается в последовательности S,
то добавляем p = 2 к списку L, после чего снова переходим к этапу добавления ребер. Пока ситуация такая:
S = [1, 5, 8, 3, 1]
L = [6, 7, 2]
Первое число в последовательности S: p = 1. Наименьшее
число в списке L: e = 2. Добавляем ребро (1,2). Удаляем e = 2 из
списка L, а p = 1 – из последовательности S. Значение
p = 1 еще встречается в последовательности S, поэтому просто
продолжаем добавлять ребра:
S = [5, 8, 3, 1]
L = [6, 7]
Теперь берем p = 5, e = 6 (первый элемент последовательности S и наименьший элемент в списке L соответственно). Добав54
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ляем ребро (5,6) к графу, после чего удаляем элемент p = 4 из S,
e = 6 удаляем из L и снова переходим к этапу добавления ребер
(так как p = 5 больше не встречается в S):
S = [8, 3, 1]
L = [7, 5]
Обратим внимание на изменения при последующих шагах
работы алгоритма. Очередным добавляемым ребром будет (8, 5),
при этом:
S = [3, 1]
L = [7, 8]
Далее добавляем ребро (3,7):
S = [1]
L = [8, 3]
55
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Теперь первый элемент в последовательности S равен p = 1,
наименьший элемент в списке L равен e = 3. Проводим ребро
(1,3), удаляем e = 3 из списка L:
S = [1]
L = [8]
Теперь осталось всего 2 вершины: 1 и 8. Проводим ребро
(1,8) и завершаем работу алгоритма. Получилось такое дерево:
Заметим, что получилось именно то дерево, по которому
строилась последовательность S (код Прюфера). Более того: при
декодировании ребра добавлялись в той последовательности, в
которой удалялись при кодировании (построении кода Прюфера).
Итак, алгоритм кодирования дереву сопоставляет единственную последовательность из N-2 чисел (из диапазона от 1 до N), а
алгоритм декодирования сопоставляет последовательности из
N-2 чисел (от 1 до 8) единственное дерево. При этом в результате
последовательного применения сначала алгоритма кодирования
(построения кода Прюфера), а затем алгоритма декодирования по
только что построенной последовательности, получается исходное дерево.
56
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Отсюда мы получаем еще один важный результат: множеству
всех деревьев во взаимно однозначное соответствие ставится
множество всех возможных кодов Прюфера, то есть последовательностей из N-2 чисел, каждое из котороых – от 1 до N. Поэтому количество деревьев равно количеству возможных кодов
Прюфера.
Но на каждую из N-2 позиций в коде Прюфера можно поставить любое из N чисел (от 1 до N). Поэтому количество возможных кодов равно N*N*...*N (всего N-2 раз) или NN-2.
Таким образом, мы получили доказательство важного утверждения, которое также носит название теоремы Кэли: количество
различных помеченных деревьев (то есть деревьев с пронумерованными вершинами) равно N N-2.
Циклы
Эйлеровы циклы
Задача, которую мы рассмотрим ниже, принадлежит к числу
первых задач на графах. Более того, с рассмотрения этой задачи
некоторые и начинают отсчет теории графов как самостоятельной дисциплины. Речь пойдет о знаменитой задаче о кенигсбергских мостах.
В 1736 году ученый Леонард Эйлер решил задачу, которую
еще называли проблемой кенигсбергских мостов. В городе Кенигсберге (теперь Калининград) на реке Преголь располагались
два острова, соединенные с берегами реки и друг с другом семью
мостами так, как показано на рисунке.
Задача заключалась в том, чтобы определить, можно ли совершить прогулку по городу так, чтобы пройти по каждому из
57
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
мостов по одному разу (не больше и не меньше) и вернуться обратно.
Эйлер обозначил острова и берега реки точками, которые условно можно отметить буквами (A, B, C и D), а мосты – линиями.
В итоге получилась такая схема:
Иначе говоря, острова и берега реки соответствуют вершинам графа, а мосты – его ребрам (хотя схема, соответствующая
данной задаче, не является графом в том смысле, в котором мы
его определили: здесь пара вершин может соединяться несколькими ребрами, такую разновидность графа также называют мультиграфом; но решение задачи от этого не изменится). Эйлеру
удалось сформулировать очень простой критерий существования
в графе (или мультиграфе) цикла (замкнутого пути), содержащего
все ребра графа в точности по одному разу (такой цикл называется эйлеровым, а граф, содержащий эйлеров цикл, сам называется
эйлеровым).
Итак, критерий существования: в графе существует эйлеров
цикл в том и только в том случае, если из каждой вершины выходит четное количество ребер.
Если вспомнить, что количество выходящих из вершины ребер называется степенью вершины, то критерий можно сформулировать так: граф является эйлеровым тогда и только тогда, когда степени всех его вершин четны.
Понятно, что граф из задачи о кенигсбергских мостах не является эйлеровым. Действительно, степень вершины A равна 5, а
степени каждой из вершин B, C и D равны 3. Итак, все вершины в
данном графе имеют нечетную степень, что не удовлетворяет условию существования в графе эйлерова цикла. Поэтому ответ в
задаче о кенигсбергских мостах отрицательный (такого замкнутого пути не существует).
58
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Доказательство критерия Эйлера не является очень сложным.
Пусть в графе существует эйлеров цикл. Тогда для каждой вершины выполняется следующее условие: сколько раз при обходе
графа мы зайдем в вершину, столько же раз мы из нее выйдем
(иначе не будет замкнутого цикла), но тогда степень каждой вершины такого графа является четным числом. Доказательство обратного утверждения является несколько более сложным. Мы
приведем алгоритм построения эйлерова цикла в графе с четными степенями вершин. Легко убедимся, что он работает для всех
таких графов.
Начинать обход можно с любой вершины. Будем строить
путь (без повторения ребер) до тех пор, пока имеется возможность его продолжить. Закончиться такой путь может только в
той вершине, с которой мы начали обход. Действительно, пусть
мы закончили путь в некоторой вершине, отличной от начальной.
Тогда мы в нее входили на 1 раз больше, чем выходили, но в этом
случае она имеет нечетную степень, что противоречит условию
существования эйлерова цикла. Итак, получили некоторый цикл.
Понятно, что он "не обязан" быть эйлеровым: вполне возможно,
что он прошел не по всем ребрам графа. Тогда возьмем произвольную вершину (X) построенного цикла, к которой примыкает
еще не пройденное ребро. А дальше будем строить новый путь,
начиная уже с новой выбранной вершины X, до тех пор, пока это
возможно. Аналогично легко показать, что этот максимальный
путь должен закончиться там же, где и начался, то есть в вершине
X. Таким образом, получили еще один цикл, который можно добавить к построенному ранее циклу. Далее снова ищем ребра, не
входящие в цикл, и выполняем те же действия. Такие действия
выполняем до тех пор, пока все ребра не окажутся включенными
в цикл. Построенный таким образом цикл будет проходить по
всем ребрам по одному разу, то есть будет эйлеровым.
Останавливаться на доказательстве корректности алгоритма
мы не будем (при желании можно самостоятельно аккуратно доказать, что для графа с четными степенями вершин этот алгоритм
строит эйлеров цикл).
Существуют и другие алгоритмы построения эйлерова цикла.
Например, имеется алгоритм Флери, который хорош еще и тем,
что строит сразу нужный маршрут (а не добавляет к нему "про59
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
межуточные" ребра, как в предыдущем алгоритме), а также позволяет удобно занумеровать ребра полученного цикла (в порядке следования). Ниже приводится его описание.
Как и в предыдущем алгоритме, обход начинаем из любой
вершины. На каждом шаге, находясь в очередной вершине, идем
по ребру, удаление которого не нарушает связности (то есть, если
удалить это ребро, то граф не распадется на два связных графа,
такое ребро называется мостом), если это возможно. Если же
других возможностей нет, то идем по мосту. Ребро, по которому
прошли, можно пометить (например, запомнить его номер) и
удалить из графа, после чего продолжаем обход.
Гамильтоновы циклы
Ранее мы определили понятие эйлерова цикла – цикла, проходящего по всем ребрам графа ровно по одному разу. Схожим
образом можно определить цикл, проходящий по всем вершинам
графа ровно по одному разу – такой цикл называется гамильтоновым. Соответственно, граф, в котором есть хотя бы один гамильтонов цикл, называется гамильтоновым графом.
Также был приведен критерий существования эйлерова цикла в графе и алгоритм его построения (если такой цикл есть). Ситуация с гамильтоновыми циклами более сложная: в настоящее
время не известно хорошего (применимого ко всем графам) критерия существования в графе гамильтонова цикла и не найдено
эффективного алгоритма построения такого цикла.
Поэтому для нахождения гамильтонова цикла приходится
использовать достаточно неэффективные алгоритмы, например
backtracking (перебор с возвратом). Идея алгоритма: строим путь,
переходя последовательно по ребрам от вершины к вершине до
тех пор, пока это возможно (пока есть возможность перейти по
ребру к еще не пройденной вершине). Если на каком-то этапе
(находясь в какой-либо вершине) перейти в новую вершину не
удается (нет ребер, ведущих от данной вершины к не рассмотренной ранее вершине), то выполняем "откат назад" – возвращаемся в предыдущую вершину построенного к настоящему моменту пути и пытаемся перейти в другую не рассмотренную ранее
вершину (совершить переход по какому-то другому ребру). Если
и из этой вершины не удается перейти к новой (каким-то другим
60
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
способом), то возвращаемся еще на один шаг назад и пробуем совершить переход уже из этой вершины, и так далее. В том случае
если на некотором этапе путь содержит все вершины (по одному
разу), то пробуем из последней вершины перейти к исходной. Если это удается, то гамильтонов цикл построен, если же нет, то
приходится снова выполнять "откат назад". Таким образом, можно построить все гамильтоновы циклы в данном графе.
Более общей задачей является так называемая задача коммивояжера, или задача нахождения кратчайшего гамильтонова
цикла. Формулируется она следующим образом: в графе каждому
ребру приписано неотрицательное число – вес (или "длина") ребра. Требуется найти такой гамильтонов цикл, чтобы суммарный
вес ребер был минимален. Обычно эту задачу формулируют для
полного графа, все вершины которого попарно соединены (и в
котором очень много гамильтоновых циклов). Не являющийся
полным граф можно "дополнить до полного", просто добавив отсутствующие ребра, приписав им "бесконечный" вес.
Изначально задача формулировалась так: торговец (коммивояжер) должен выйти из некоторого города, посетить по одному
разу все города (общее количество городов: N, расстояния между
городами известны) и вернуться в исходный пункт, преодолев
наименьшее расстояние. Фактически, эта задача и означает поиск
в графе гамильтонова цикла наименьшего веса.
Эффективного алгоритма решения данной задачи пока не известно. Есть достаточно быстрые алгоритмы, которые не решают
точно эту задачу, но позволяют находить решение с некоторой
погрешностью – 100% (алгоритм Эйлера) или 50% (алгоритм
Кристофидеса).
Потоки в сетях
В этом разделе мы рассмотрим алгоритм нахождения максимального потока в сетях – классического алгоритма, применение
которого сначала действительно ограничивалось нахождением
максимальных потоков, например, в сети нефтепроводов, но затем с его помощью стали решать и многое другие задачи.
61
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм нахождения максимального потока
Приведем алгоритм расстановки пометок для задачи о максимальном (от s к t ) потоке.
А. Расстановка пометок.
Вершина может находиться в одном из трех состояний: вершине приписана пометка и вершина просмотрена (т.е. она имеет
пометку и все смежные с ней вершины "обработаны"), пометка
приписана, но вершина не просмотрена (т.е. она имеет пометку,
но не все смежные с ней вершины обработаны), вершина не имеет пометки. Пометка произвольной вершины x(i) состоит из двух
частей и имеет один из двух видов: (+x(j), m) или (-x(j), m). Часть
+x(j) пометки первого типа означает, что поток допускает увеличение вдоль дуги (x(j), x(i)). Часть -x(j) пометки другого типа означает, что поток может быть уменьшен вдоль дуги (x(i), x(j)). В
обоих случаях m задает максимальную величину дополнительного потока, который может протекать от s к x(i) вдоль построенной
увеличивающей цепи потока. Присвоение пометки вершине x(i)
соответствует нахождению увеличивающей цепи потока от s к
x(i). Сначала все вершины не имеют пометок.
Шаг 1.
Присвоить вершине s пометку (+s,m(s)=бесконечность).
Вершине s присвоена пометка и она просмотрена, все остальные
вершины без пометок.
Шаг 2.
Взять некоторую непросмотренную вершину с пометкой,
пусть ее пометка будет ( ± x(k),m(x(i))) ( ± обозначает, что перед
x(k) может стоять как плюс, так и минус).
(I) Каждой помеченной вершине x(j), принадлежащей Г(x(i)),
для которой c(i,j) < q(i,j), присвоить пометку (–x(i), m(x(j))),
где m(x(j)) = min[m(x(i)), q(i,j) – c(i,j)].
(II) Каждой непомеченной вершине x(j), принадлежащей Д(x),
для которой c(i,j) > 0, присвоить пометку (–x(i), m(x(j))),
где m(x(j)) = min[m(x(i)), c(j,i)]. (Теперь вершина x(i)
и помечена, и просмотрена, а вершины x(j), пометки которым присвоены в (I) и (II), являются непросмотренными.) Обозначить каким-либо способом, что вершина
x(i) просмотрена.
62
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Шаг 3.
Повторять шаг 2 до тех пор, пока либо вершина t будет помечена, и тогда перейти к шагу 4, либо t будет не помечена и никаких других пометок нельзя будет расставить; в этом случае алгоритм заканчивает работу с максимальным вектором потока c.
Здесь следует отметить, что если X(0) – множество помеченных
вершин, а X'(0) – множество непомеченных, то (X(0)-->X'(0)) является минимальным разрезом.
Б. Увеличение потока.
Шаг 4.
Положить x=t и перейти к шагу 5.
Шаг 5.
(I) Если пометка в вершине x имеет вид (+z, m(x)), то изменить
поток вдоль дуги (z,x) c c(z,x) на c(z,x) + m(t).
(II) Если пометка в вершине x имеет вид (-x, z) то изменить
поток вдоль дуги с c(x,z) на c(x, z) – m(t).
Шаг 6.
Если z = s, то стереть все пометки и вернуться к шагу 1, чтобы начать расставлять пометки, но используя уже улучшенный
поток, найденный на шаге 5. Если z ≠ s, то взять x = z и вернуть к
шагу 5.
Обозначения: Г(x(i)) – множество вершин, в которые есть дуга из вершины i; Д(x(i)) – множество вершин, из которых есть
дуга в вершину i; c(i,j) – это пропускная способность дуги (т.е.,
например, сколько груза может быть перевезено по дороге (по
дуге) (i,j) за единицу времени); q(i,j) – поток по дуге (i,j) (т.е.
сколько перевозится сейчас на самом деле).
Примеры графовых задач в олимпиадах
В этом разделе мы рассмотрим несколько задач, начиная с
простейших, которые использовались в различных олимпиадах,
начиная с городских и кончая международными.
63
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задачи
Задача 1.
Задан набор неповторяющихся пар (Ai,Aj); Ai, Aj принадлежат множеству А = {A1, A2, ..., An}. Необходимо составить
цепочку
максимальной
длины
по
правилу
(Ai,Aj) + (Aj,Ak) = (Ai,Aj,Ak). При образовании этой цепочки
любая пара может быть использована не более одного раза.
Задача 2.
Между N пунктами (N<=50) заданы дороги длиной A(i,j), где
I,J – номера пунктов. Дороги проложены на разной высоте и пересекаются только в общих пунктах. В начальный момент времени из заданных пунктов начинают двигаться с постоянной скоростью M роботов (M=2 или 3), независимо меняя направление
движения только в пунктах. Роботы управляются таким образом,
чтобы минимизировать время до встречи всех роботов в одном
месте. Скорость I-того робота может быть равна 1 или 2 . Остановка роботов запрещена.
Задание: написать программу, которая:
1) при заданных N,M и сети дорог единичной длины (все
имеющиеся A(i,j)=1) определяет минимальное время, через которое может произойти встреча всех M роботов, при этом начальное положение роботов и скорость их движения известны;
2) выполнить те же действия, что и в п. 1, но только для различных значений A(i,j).
Примечание: в случае невозможности встречи всех M роботов в одном месте ни в какой момент времени в результате выполнения программы должно быть сформировано соответствующее сообщение.
Требования к вводу – выводу:
1) все входные данные - целые неотрицательные числа;
2) при задании сети дорог должно быть указано количество
дорог – K и пункты их начала и конца в виде пар (i,j).
64
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 3.
На плоскости расположено N точек. Имеется робот, который
двигается следующим образом. Стартуя с некоторой начальной
точки и имея некоторое начальное направление, робот движется
до первой встреченной на его пути точки, изменяя в ней свое текущее направление на 90 градусов, т.е. поворачивая налево или
направо. После этого он продолжает движение аналогично. Если
робот достиг начальной точки, либо не может достичь новой точки (которую он еще не посещал), то он останавливается. Определить, может ли робот посетить все N точек, если:
1) определены начальные точка и направление робота;
2) определена начальная точка, а направление робота можно
выбирать;
3) начальную точку и направление робота можно выбирать.
Координаты точек – целые числа, угол измеряется в радианах
относительно оси ОХ.
Задача 4. "Путь"
Найти кратчайшее расстояние между двумя вершинами в
графе. Найти все возможные пути между этими двумя вершинами в графе не пересекающиеся по
а) pебpам,
б) вершинам.
Задача 5.
Лабиринт задается матрицей смежности N*N, где C(i,j)=1,
если узел i связан узлом j посредством дороги. Часть узлов назначается входами, часть - выходами. Входы и выходы задаются
последовательностями узлов X(1),.., X(p) и Y(1),.., Y(k) соответственно. Найти максимальное число людей, которых можно провести от входов до выходов таким образом, чтобы:
а) их пути не пересекались по дорогам, но могут пересекаться
по узлам;
б) их пути не пересекались по узлам.
65
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 6.
N шестеренок пронумерованы от 1 до N (N<= 10). Заданы M
(0<=M<=45) соединений пар шестеренок в виде (i,j), 1<=i<j<=N
(шестерня с номером i находится в зацеплении с шестерней j).
Можно ли повернуть шестерню с номером 1? Если да, то найти
количество шестерен, пришедших в движение. Если нет, то требуется убрать минимальное число шестерен так, чтобы в оставшейся системе при вращении шестерни 1 во вращение пришло бы
максимальное число шестерен. Указать номера убранных шестерен (если такой набор не один, то любой из них) и количество
шестерен, пришедших в движение.
Задача 7.
На фигуре 1 показана вычислительная система, содержащая
достаточное количество процессоров, использующих общую память из 26 числовых переменных A,B,C, ..., Z. Система работает
шагами. На каждом шаге, каждый процессор выполняет либо
оператор присваивания либо пустой оператор. Оператор присваивания - это конструкция вида (переменная) = (арифметическое выражение) где арифметическое выражение без скобок и содержит не более 2 переменных и арифметические операции. Процессоры вычисляют выражения и присваивают их значения переменным из левых частей операторов, а потом приступают к
следующим операторам (при том одновременно). Не допускается
одновременное выполнение 2 или больше операторов присваивания с одинаковой левой частью. Пустой оператор обозначаем
символом &. Выполняя его, процессор простаивает 1 шаг.
┌──┐
┌──┐
┌──┐
│P1│
│P2│
...
│Pn│ ...
└┬─┘
└┬─┘
└┬─┘
│
│
│
┌───┴─────────┴──────────────┴───────────┐
├───┬───┬───┬────────────────────────┬───┤
│ A │ B │ C │
│ Z │
└───┴───┴───┴────────────────────────┴───┘
Фигура 1
66
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
n-последовательности операторов (присваивания или пустых)
с одинаковой длиной L называем n-программой с длиной L (выполняется за L шагов на первых n процессоров), если на каждом
шаге имеем не более 1 оператора с заданной левой частью. nпрограммы P и Q называем эквивалентными, если начиная с одного и того же начального состояния переменных A,B, ..., Z после выполнения как P, так и Q получается одинаковый результат.
Напишите программу, которая:
Задание 1.
Вводит целое k (k<25) и 1-программу, содержащую k операторов присваивания.
Задание 2.
Проверяет правильность введенных операторов.
Задание 3.
Преобразует 1-программу в эквивалентную m-программу c
минимальной длиной (добавляя если надо пустые операторы) и
выводит полученный результат.
Задание 4.
Не увеличивая длину построенной в Задании 3 n-программы,
преобразует ее в эквивалентную m-программу (m – как можно
меньше), и выводит полученный результат.
Замечание.
На фигуре 2 показана 1-программа из 6 операторов и 3программа и 2-программа – возможные решения задач 3(б) и 4(в).
а)
D=A*D
A=B+C
A=A-E
B=C+D
D=D-E
E=A*B
б) A=B+C
A=A-E
E=A*B
в) A=B+C
A=A-E
E=A*B
B=C+D
&
D=A*D
B=C+D
D=D-E
D=A*D
Фигура 2
67
D=D-E
&
&
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 8.
Имеется N прямоугольных конвертов и N прямоугольных открыток различных размеров. Можно ли разложить все открытки
по конвертам, чтобы в каждом конверте было по одной открытке.
Замечание. Открытки нельзя складывать, сгибать и т.п., но можно
помещать в конверт под углом. Например, открытка с размерами
сторон 5:1 помещается в конверты с размерами 5:1, 6:3, 4.3:4.3,
но не входит в конверты с размерами 4:1, 10:0.5, 4.2:4.2.
Задача 9.
Составить программу для нахождения произвольного разбиения 20 студентов на 2 команды, численность которых отличается не более чем в 2 раза, если известно, что в любой команде
должны быть студенты, обязательно знакомые друг с другом.
Круг знакомств задается матрицей (20,20) с элементами
A(ij)={1,если i студент знаком с j
{0,иначе.
Задача 10.
Имеется N человек и прямоугольная таблица А[1:N,1:N];
элемент A[i,j] равен 1, если человек i знаком с человеком j,
А[i,j] =А[j,i]. Можно ли разбить людей на 2 группы, чтобы в каждой группе были только незнакомые люди.
Задача 11.
На олимпиаду прибыло N человек. Некоторые из них знакомы между собой. Можно ли опосредованно перезнакомить их
всех между собой? (Незнакомые люди могут познакомиться
только через общего знакомого.)
Задача 12.
Пусть группа состоит из N человек. В ней каждый имеет
(N/2) друзей и не больше K врагов. У одного из них есть книга,
которую все хотели бы прочитать и потом обсудить с некоторыми из остальных. Написать программу, которая:
68
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) находит способ передачи книги таким образом, чтобы она
побывала у каждого в точности один раз, переходя только от друга к другу и, наконец, возвратилась к своему владельцу;
2) разбивает людей на S групп, где будет обсуждаться книга,
таким образом, чтобы вместе с каждым человеком в ту же самую
группу вошло не более P его врагов.
Примечание: предполагается, что S*P>=K.
Задача 13.
В заданном графе необходимо определить, существует ли
цикл, проходящий по каждому ребру графа ровно один раз.
Задача 14.
Следующая фигура показывает запутанную сеть дорог района города. Представьте, что мусорная машина должна пройти по
всем дорогам хотя бы один раз, чтобы собрать мусор. Число на
каждой стороне показывает время, которое должна потратить
мусорная машина, чтобы проехать этот интервал. На перекрестках машина должна ждать время, равное числу пересекающихся
дорог. Составьте программу, показывающую как выбрать необходимый путь для сбора мусора в кратчайшее время.
│
10
│
───O┌─────────────────────┐O───
│└────┐4
8┌───┘│
8 │ 4 └─────┬──────┘ 7 │ 6
───O┌──────────O───────────O───
│└────┐ 10
│
7 │ 7 └─────┐
8
│ 8
───O───────────O───────────O───
│
11┌─────┼──────┐5
│
6 │┌────┘
4│
└───┐│ 13
───O└──────────O──────────┘O───
│
12
│
9
│
│
│
69
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Есть 11 остановок.
от 1 до 2 путь
от 1 до 3
от 1 до 4
от 2 до 3
от 2 до 5
от 3 до 4
от 3 до 5
от 4 до 7
от 4 до 6
от 4 до 8
от 8 до 6
от 8 до 10
от 10 до 6
от 6 до 9
от 10 до 9
от 6 до 11
от 6 до 4
от 5 до 4
от 4 до 11
от 9 до 11
10 мин.
4
8
8
6
4
7
7
10
7
7
6
11
4
12
5
8
8
13
5
Задача 15.
N различных станков один за другим объединены в конвейер.
Имеется N рабочих. Задана матрица C[N , N], где C[i,j] производительность i-ого рабочего на j-ом станке. Определить:
а) на каком станке должен работать каждый из рабочих, чтобы производительность была максимальной;
б) то же, но станки расположены параллельно и выполняют
однородные операции.
Задача 16.
На плоскости задан граф с N вершинами. Количество ребер,
соединенных с каждой вершиной, равно 3.
70
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример:
B┌────────────┐C
│\
/│
│ \ G
F / │
│ ┌──────┐ │
│ │
│ │
│ │
│ │
│ └──────┘ │
│ / H
E\ │
│ /
\ │
A└────────────┘D
Пусть вершины X,Y и Z являются соседями вершины Т. Будем считать, что Y – левый, а Z – правый сосед вершины Т относительно вершины X, если ориентированный угол XTZ меньше
ориентированного угла XTY (положительным будем считать направление против часовой стрелки). Например вершина Е является правым соседом вершины Н относительно А, а G – левым, поскольку ориентированный угол АНЕ меньше ориентированного
угла AHG (ребра считаются отрезками). Составьте программу,
которая:
1) вводит координаты вершин графа и его ребра и рисует
граф на экране компьютера, производя при этом подходящее
масштабирование (ребра выводятся как отрезки);
2) пусть заданы две начальные соседние вершины XO и X1 и
последовательность вида LLRRL... Тогда программа находит
путь на графе XOX1X2 ... Xn для вершин которого выполнено:
- первые два являются заданными XO и X1,
- Xi+1 является левым или правым соседом Xi относительно
Xi – 1 в зависимости от заданной последовательности, при этом L
означает левый, а R – правый.
Пример: В заданном графе пусть даны начальные вершины А
и H и последовательность LRRLLR. Тогда программа должна
найти путь AHGFEDCB;
3) рисует на экране путь, найденный в п. 2;
71
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
4) пусть даны начальная и конечная вершина. Программа
должна найти путь, проходящий через минимальное число вершин, вывести его на экран и найти 2 первые вершины и управляющую последовательность для этого пути, как определено в
п. 2.
Задача 17.
Имеется N городов. Для каждой пары городов (I,J) можно построить дорогу, соединяющую эти два города и не заходящие в
другие города. Стоимость такой дороги A(I,J). Вне городов дороги не пересекаются. Написать алгоритм для нахождения самой
дешевой системы дорог, позволяющей попасть из любого города
в любой другой. Результаты задавать таблицей B[1:N,1:N], где
B[I,J] = 1 тогда и только тогда, когда дорогу, соединяющую города I и J, следует строить.
Задача 18.
В картинной галерее каждый сторож работает в течение некоторого непрерывного отрезка времени. Расписанием стражи
называется множество пар [Т1(i), Т2(i)] – моментов начала и конца дежурства i-го сторожа из интервала [0,EndTime]. Для заданного расписания стражи требуется:
(а) проверить, в любой ли момент в галерее находится не менее двух сторожей.
Если условие (а) не выполнено, то:
(б) перечислить все интервалы времени с недостаточной охраной (менее 2 сторожей);
(в) добавить наименьшее число сторожей с заданной, одинаковой для всех длительностью дежурства, чтобы получить правильное расписание (т.е. удовлетворяющее условию (а));
(г) проверить, можно ли обойтись без добавления новых сторожей, если разрешается сдвигать времена дежурства каждого из
сторожей с сохранением длительности дежурства;
(д) если это возможно, то составить расписание с наименьшим числом сдвигов.
72
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ВХОДНЫЕ ДАННЫЕ:
(Все моменты времени задаются в целых минутах.)
EndTime – момент окончания стражи, т.е. охраняется отрезок
времени [0, EndTime].
N – число сторожей.
T1[i], T2[i], i = 1,..N – моменты начала и окончания дежурства i-го сторожа.
Length – длительность дежурства каждого дополнительного
сторожа.
ВЫХОДНЫЕ ДАННЫЕ:
(1) Ответ на пункт (а) в форме да/нет.
(2) При ответе "нет" на п. (а) – список пар (k,l) - начал и концов всех малоохраняемых интервалов с указанием числа сторожей в каждом (0 или 1).
(3) Число дополнительных сторожей и моменты начала и
окончания дежурства каждого дополнительного сторожа.
(4) Ответ на пункт (г) в форме да/нет. Если "да", то номера
сторожей, смена которых сдвигается, и значения сдвигов.
(5) В ответ на пункт (д): наименьшее число сторожей, смена
которых сдвигается, их номера и значения сдвигов.
ПРИМЕЧАНИЕ
Программа должна допускать независимое тестирование
пунктов (в), (г), (д).
Задача 19.
Вводится N – количество домов и К – количество дорог. Дома пронумерованы от 1 до N. Каждая дорога определяется тройкой чисел – двумя номерами домов – концов дороги и длиной дороги. В каждом доме живет по одному человеку. Найти точку –
место встречи всех людей, от которой суммарное расстояние до
всех домов будет минимальным. Если точка лежит на дороге, то
указать номера домов – концов этой дороги и расстояние от пер73
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вого из этих домов. Если точка совпадает с домом, то указать номер этого дома.
Примечание: длины дорог – положительные целые числа.
Задача 20.
N колец сцеплены между собой (задана матрица A(n*n),
A(i,j) = 1 в случае, если кольца i и j сцеплены друг с другом и
A(i,j) = 0 иначе). Удалить минимальное количество колец так,
чтобы получилась цепочка.
Задача 21.
Янка положил на стол N выпуклых K-гранников и N различных типов наклеек по K штук каждая. Ночью кто-то наклеил наклейки на грани, по одной на грань. Помогите Янке расставить
многогранники так, чтобы наклейка каждого типа была видна
ровно K – 1 раз.
Задача 22.
Имеется N точек и M проводков. Проводком можно соединить некоторую пару различных точек, причем пара может быть
соединена не более чем одним проводком. Все проводки должны
быть использованы. Пусть Di – количество проводков, которые
будут соединены с точкой с номером i, i = 1, ..., N. Необходимо
соединить N точек с помощью M проводков таким образом, чтобы сумма S = D1*D1 + D2*D2 + ... + Dn*Dn была максимальной.
Вывести величины Di в неубывающем порядке и по требованию
(priznak = 1), список соединений.
ВВОД:
<Введите N:> N (N<=100)
<Введите M:> M (M<=1000)
<PRIZNAK=> PRIZNAK
ВЫВОД:
<Результирующая конфигурация:> Di в неубывающем порядке.
74
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
<Сумма S> S
<Список соединений>
<Точку 1 соединить с> список точек
.....
<Точку N соединить с> список точек
Задача 23.
Задано N городов c номерами от 1 до N и сеть из M дорог с
односторонним движением между ними. Каждая дорога задается
тройкой (i, j, k), где i - номер города, в котором дорога начинается, j – номер города, в котором дорога заканчивается, а k – ее
длина (число k – натуральное). Дороги друг с другом могут пересекаться только в концевых городах. Все пути между двумя указанными городами A и B можно упорядочить в список по неубыванию их длин (если есть несколько путей одинаковой длины, то
выбираем один из них). Необходимо найти один из путей, который может быть вторым в списке. Вывести его длину L и города,
через которые он проходит.
ВВОД:
<Количество городов N:> N
<Количество дорог M:> M
<Начало, конец и длина дороги 1:> i1, j1, k1
......
<Начало, конец и длина дороги M:> iM, jM, kM
<Города A и B, между которыми надо найти путь:> A, B
ВЫВОД:
<Пути нет>
или
<Путь проходит по городам> A, i1, i2, ..., B
<Длина пути> L
75
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 24. "Задача Ларсона"
Пусть G – конечный неориентированный связный граф.
Предположим, что он представляет собой систему тоннелей, в
которых может прятаться беглец. Группа из S полицейских, двигаясь по туннелям, стремится схватить этого беглеца, который
может двигаться с любой скоростью, стремясь избежать поимки.
Требуется определить минимальное количество полицейских S,
гарантирующих поимку беглеца.
25. Колье
Ювелиру заказали изготовить колье, состоящее из сцепленных друг с другом золотых колец. Ювелир занумеровал кольца
числами от 1 до N и стал изготавливать украшение, используя
кольца по очереди – сначала первое, затем второе, и т.д. Каждый
раз он делал в тетради пометку, к какому кольцу он зацеплял
очередное кольцо. Таким образом, в тетради появилась N-1 запись: сначала там появилось число 1 (первое кольцо ни к чему не
прицеплялось, а второе – к первому), затем одно из чисел 1 или 2,
в зависимости от того, к какому кольцу прицеплялось второе
кольцо, и т.д.
Когда колье было готово, заказчик передумал его покупать и
потребовал, чтобы ювелир изготовил из него золотую цепь, отцепив некоторые кольца.
Напишите программу, которая по записям в тетради рассчитывает длину максимальной цепочки, которую можно получить
из колье.
26. Приватизация железных дорог
В государстве из каждого города выходят ровно 3 железные
дороги, ведущие в другие города. Дороги решили приватизировать две частные компании. По решению антимонопольного комитета запрещено все три дороги, выходящие из одного города,
отдавать одной компании.
Напишите программу, которая по заданной схеме железных
дорог рассчитывает одно из возможных распределений всех дорог между компаниями, или сообщает, что требование антимонопольного комитета невыполнимо.
76
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
27. Плуг
Преступники совершили ограбление банка и решили скрыться из города на тракторе, к которому был прицеплен плуг. Проезжая по дороге, преступники уничтожали (перепахивали) эту
дорогу, чтобы полицейские, которые бросятся в погоню через некоторое время, не смогли идти по той же дороге.
Напишите программу, которая по заданной схеме дорог находит множество городов, в которых преступники смогут найти
надежное убежище, т.е. таких, куда из начального города не останется ни одной неповрежденной дороги. Маршрут движения,
естественно, преступники выбирают сами.
28. Автобусные маршруты
Пришедший к власти в городе Фишбурге мэр решил реформировать движение городских автобусов. Для этого он потребовал, чтобы ему предоставили информацию, по каким маршрутам
ходят все автобусы. Информация о каждом маршруте состояла из
перечня всех остановок вдоль следования данного автобуса по
кругу.
Мэр приказал заменить все маршруты одним, но включающим в себя все переезды, какие и были раньше, причем, если между двумя остановками ходили K автобусов, то и новый маршрут
должен был проходить между этими остановками K раз.
Напишите программу, которая по заданному множеству
имеющихся в городе маршрутов находит один из возможных
требуемых маршрутов.
29. Второй по длине путь
В заданном взвешенном графе найдите второй по длине путь
между двумя заданными вершинами.
30. Выборы в Анчурии
Государство Анчурия разбито на квадратные избирательные
округа, которые в совокупности образуют прямоугольник N×M.
От каждого округа в парламент страны избирается один депутат.
Если большинство избирателей округа – сторонники действующего президента, то в парламент избирается сторонник президен77
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
та. Перед выборами был произведен социологический опрос,
точно установивший количество избирателей, настроенных за и
против президента. На основании этих данных президент хочет
максимально увеличить количество своих сторонников в парламенте. Для этого он может укрупнить некоторые из избирательных округов, слив два соседних округа в один, от которого будут
избираться два депутата в парламент.
Требуется написать программу, которая по известным данным социологического опроса предлагает вариант укрупнения
округов для достижения вышеизложенных целей.
31. Лягушка и комар
Игра ведется на поле 8×8, называемом болотом, на котором
некоторые клетки являются водной гладью, а некоторые – кочками. В начальный момент на одной из кочек сидит лягушка, а над
одной клеткой летает комар.
Лягушка и комар делают ходы по очереди (начинает лягушка).
Ход лягушки заключается в перепрыгивании на любую кочку, находящуюся в той же горизонтали или вертикали, где в данный момент находится лягушка. Лягушка, в частности, может остаться на месте.
Ход комара заключается в обязательном перелете в любую
соседнюю клетку.
Если во время хода лягушка перелетает над клеткой, где в
данный момент находится комар, она его съедает, и игра заканчивается ее победой. После победы лягушке разрешается приземлиться в любую клетку болота (не обязательно на кочку).
Требуется написать программу, которая по заданному расположению кочек на болоте и начальным положениям лягушки и
комара рассчитывает ход лягушки, ведущей ее к победе за наименьшее количество ходов, независимо от игры комара. Если у
лягушки нет выигрышной стратегии, то программа должна это
сообщить.
78
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Указания и решения
Задача 1.
Для более удобного хранения информации заведем матрицу
C[1...n,1..n] (так называемую матрицу смежности) в которой
C[i,j] = 1, если в наборе есть пара (Ai,Aj) и C[i,j] = 0 иначе. Будем
строить все возможные цепочки (по правилу, данному в условии)
и искать среди них ту, которая имеет максимальную длину. В качестве начального символа цепочки можно взять любой символ
из A. Пусть это символ Ai. Ищем, просматривая строку i матрицы
C слева направо элемент C[i,j] = 1 (другими словами, ищем пару с
первым элементом Ai). Если такого элемента не существует, то
берем в качестве начала строки другой элемент множества A. Если элемент C[i,j] = 1 найден, то ему соответствует пара (Ai, Aj).
Помечаем ее как уже использованную, полагая, например,
C[i,j] = –1. Далее просматриваем слева направо строку j матрицы
C в поисках еще не использованной пары (Aj, Ak) (C[j,k] = 1).
Присоединяем элемент Ak к имеющейся цепочке, полагаем
C[j,k] = –1, ищем единичный элемент в строке k и т.д. Предположим, на некотором шаге мы получили цепочку Ai Aj Ak ... As Al
Ap и в строке p матрицы больше нет ни одного единичного элемента. Это означает, что при таком подборе предыдущих элементов мы нашли максимальную по длине строку. Если ее длина
больше длин всех найденных ранее строк, запоминаем эту строку
как рекорд. После этого "отщепляем" от строки последний элемент Ap и смотрим, есть ли еще в строке l единичный элемент с
индексом, большим p. Если да, то приписываем уже этот элемент
к строке и пытаемся затем снова увеличить длину полученной
строки, если же нет, то "отщепляем" от строки элемент Al, в
строке S ищем единичный элемент с индексом, большим l и т.д.
Останов осуществляется тогда, когда мы должны "отщепить" от
строки Ai. Перебираем цепочки, начинающиеся со всех возможных элементов множества A. Находим строку максимальной
длины:
const M=10;
{ максимально число элементов в A }
{ будем считать, что A состоит из чисел от 1 до N }
var c:array[1..M,1..M] of integer;
79
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
curstr, maxstr: array[0..M] of integer;
{ в этих переменных хранятся текущая цепочка и }
{ цепочка максимальной длины. }
{ В нулевом элементе хранится длина цепочки }
N,E : integer; { N - число элементов в A }
i,j,k : integer; { E - число пар в наборе }
procedure find;
var l,j : integer;
begin
l:=curstr[curstr[0]]; { l = последний элемент цепочки }
for j:=1 to N do { просмотр строки l }
if C[l,j]=1
then begin
curstr[0]:=curstr[0]+1;
curstr[curstr[0]]:=j; { j -> в цепочку }
c[l,j]:=-1;
{ пара использована }
find;
c[l,j]:=1; { пару снова разрешено }
{
использовать }
curstr[0]:=curstr[0]-1;
end;
if curstr[0]>maxstr[0] { если нашли более }
then maxstr:=curstr
{ длинную строку }
end;
begin
readln(N); readln(E);
for i:=1 to N do
for j:=1 to N do
C[i,j]:=0;
for k:=1 to E do begin
write('очередная пара: ',i,j);
c[i,j]:=1
end;
80
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
for i:=1 to N do begin
curr[0]:=1;
{ поиск цепочки }
curr[1]:=i; { начинающейся элементом i }
find;
end;
for i:=1 to maxstr[0] do
write(maxstr[i]); { печать максимальной строки }
end.
Задача 2.
Для решения задачи важно понять, что встреча роботов может произойти либо в пункте, либо на дороге. В первом случае
задача решается просто: необходимо последовательно строить
множества пунктов для каждого робота, в которых они могут
оказаться через время, равное 0.5,1,1.5,2,...Т. Это можно делать,
используя очереди. В случае же встречи роботов на дороге легко
понять, что непосредственно перед встречей все они должны были находится в следующих пунктах:
1) либо в двух пунктах, связанных дорогой;
2) либо в пунктах, из которых есть дороги в один и тот же
пункт;
3) либо в трех пунктах, образующих треугольник.
Поэтому, после каждого целого такта времени, достаточно
проверять, находятся ли роботы в одной из описанных 3 ситуаций. При этом время подсчитывается очевидным способом.
Задача 3.
Рассмотрим только случай, когда роботы двигаются только
параллельно координатным осям, в других случаях можно сделать преобразование координат. Легко понять, что если рассмотреть точку, имеющую наибольшую координату Y, причем самую
левую (т.е. наименьшую координату Х, если таких несколько), то
для нее существует только 2 возможности быть пройденной роботом: робот должен прийти из ближайшей точки А снизу и пойти в ближайшую точку Б справа или наоборот. В любом случае
эти 2 отрезка фиксированы для робота. Теперь те же рассуждения можно провести и для точек Б и точки, находящейся правее
81
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Б, а также для самых нижних, левых и правых точек. Окончательно получается, что возможный проход робота строго фиксирован. Если упорядочить точки по горизонталям (вертикалям), то
первая точка горизонтали (вертикали) должна соединятся со второй, третья с четвертой и т.д. Понятно, что если получившаяся
фигура связна (цикл), то решение существует для случаев 2. и 3.,
а для случая 1. нужно проверить, в нужном ли направлении стоит
робот. Однако есть одна трудность в случае, когда существуют
горизонталь и вертикаль, содержащие нечетное число точек, а
обход существует. Это возможно только в случае, когда это стартовая точка обхода, причем она находится в 'нечетной' горизонтали и вертикали. Удалив ее, можно воспользоваться предыдущей процедурой, при этом фиксированные отрезки не должны
пересекаться в удаленной точке.
Задача 4.
Для решения задачи достаточно воспользоваться алгоритмом
нахождения потока между двумя заданными вершинами, преобразуя в случае а) граф по следующему правилу: каждую вершину
исходного графа превращаем в ребро с пропускной способностью 1.
Задача 5.
Решается аналогично задаче 4.
Задача 6.
Будем обозначать вращение по часовой стрелке нулем, против
– единицей. Сначала припишем шестерне с номером 1 число
нуль. На следующем шаге всем шестерням, сцепленным с первой,
будут приписаны числа 1 (они будут вращаться в противоположную шестерне 1 сторону). Далее всем шестерням, находящимся в
зацеплении с занумерованными на предыдущем шаге, припишем
значения 0 и т.д. Процесс будем повторять до тех пор, пока либо
на очередном шаге ни одной шестерне не будет приписано новое
значение, и тогда шестерню с номером 1 удастся повернуть, и
число рассмотренных шестеренок и есть искомое число пришедших в движение, либо на каком-то шаге пометка шестерни изменяется с 1 на 0 или с 0 на 1, и тогда система в движение не придет.
82
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Перебирая сначала все возможные варианты выбрасывания
по одной, затем, в случае неудачи по две, три, ... , N-1 шестерни и
проводя аналогичные рассуждения мы получаем максимальное
число шестерен, которое могло бы прийти в движение. О генерации вариантов выбрасывания шестерен см. Задачу 2 (перебор).
Задача 8.
Можно сформировать граф, состоящий из 2*N вершин, соответствующих открыткам и конвертам, причем две вершины соединены ребром, если одна соответствует открытке, а другая –
конверту, при этом соответствующая открытка входит в соответствующий конверт. Добавив в этом графе 2 новые вершины, одна
из которых смежна всем вершинам, соответствующим открыткам, а другая – всем вершинам, соответствующим конвертам,
сведем задачу к задаче нахождения максимального потока между
этими вершинами.
Задача 9.
Разбиение на группы осуществляется аналогично, как и в Задаче 10, за тем исключением, что в ситуации 3. организуются две
новые группы (пара групп, одна из них может оказаться в результате пустой). После разбиения всех людей будем использовать
принцип формирования двух результирующих групп, учитывая
возможности объединения двух пар групп в одну пару групп
произвольным слиянием двух групп из различных пар.
Задача 10.
Задача решается следующим образом. Выбирается произвольный человек и помещается в первую группу. Затем находятся
люди, ему знакомые. Понятно, что они не могут находиться в
первой группе, поэтому их необходимо поместить во вторую. Затем находятся люди, знакомые людям из второй группы. Понятно, что они не могут находиться во второй группе, поэтому их
необходимо поместить в первую. Повторяя так поочередно для
каждой из групп, мы придем к одной из ситуаций:
1. Какой-то человек сначала был помещен в одну группу, а
потом должен быть помещен в другую. Понятно, что в этом случае задача не имеет решения.
83
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Каждый человек помещен в одну из групп. В этом случае
задача решена.
3. Не каждый человек помещен в одну из групп. Это означает, что оставшиеся не помещенные в группы люди не знакомы
людям в группах (иначе они были бы куда-нибудь помещены).
Следовательно, одного из них безразлично куда помещать, например в первую группу. Затем описанный выше процесс продолжается, пока не придем к ситуации 1 или 2.
Задача 11.
Для решения задачи достаточно определить, является ли
связным граф, определяемый матрицей смежности, элементы которой а[i,j] равны 1, если люди с номерами i и j знакомы и равны
0 иначе. Граф называется связным, если существует путь между
любыми парами его вершин. Понятно, что путь между вершинами i и j в таком графе и определяет возможную последовательность знакомств, позволяющих познакомить людей с номерами
i и j. Для определения связности графа можно воспользоваться
методом поиска в ширину, который состоит в следующем.
На начальном этапе в очередь помещается некоторая начальная вершина, например вершина с номером 1.
На каждой из следующих итераций (пока очередь не пуста)
выполняются следующие действия:
– извлекается вершина из очереди;
– определяются вершины, ей смежные и которые в очереди
еще не были, и помещаются в очередь.
Если в результате таких действий все вершины побывали в
очереди (а для этого удобнее подсчитывать количество вершин,
там побывавших), то граф связен, иначе не связен. Для маркировки вершин, побывавших в очереди, можно использовать массив
размера N с элементами 0 и 1.
Задача 12.
Задача может быть сформулирована в графовой постановке
следующим образом: найти простой цикл в графе (т.е. без повторяющихся вершин), проходящий через все вершины графа. В общем случае не существует эффективного алгоритма решения этой
задачи. Однако в данном случае задачу можно решить эффективно.
84
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Предположим, что уже построен некоторый простой путь
(x[1], x[2], ... x[k]) Множество вершин, вошедших в путь, будем
считать пройденными, остальные не пройденные. Возможны 3
ситуации.
1. Одна из вершин x[1], x[k] смежна одной из не пройденных
еще вершин. В этом случае путь можно очевидным образом удлинить на одну вершину.
2. Ни одна из вершин x[1], x[k] не смежна одной из не пройденных еще вершин, а вершины x[1] и x[k] смежны. В этом случае понятно, что k > N/2, так как вершины x[1] и x[k] смежны N/2
вершинам.
Следовательно, количество не пройденных вершин не больше N/2. Следовательно, любая вершина у из них смежна одной из
пройденных вершин, например x[i]. Но тогда можно получить
более длинный путь (у,x[i], x[i+1], ..., x[k], x[1], x[2], ... x[i-1]).
3. В этом случае степеней вершин нетрудно показать, что в
пути (x[1], x[2], ... x[k]) существует такой индекс i, что x[1] смежна x[i], а x[i-1] смежна x[k]. Следовательно, рассмотрев путь
(x[i], x[i+1], ..., x[k], x[i-1], x[i-2], ... x[1]), мы имеем ситуацию 2,
поэтому можно получить более длинный путь.
Применяя описанный выше способ начиная с пути длины 1,
построим простой цикл, включающий все вершины.
Задача 13.
В заданном графе необходимо определить, существует ли
цикл, проходящий по каждому ребру графа ровно один раз. Для
существования такого цикла необходимо и достаточно наличия
двух условий:
1) граф является связным;
2) степень любой вершины графа четна.
Первое условие очевидно. Второе следует из факта, что если
такой цикл существует и заходит в некоторую вершину графа, то
он должен и выйти из нее. Проверим эти условия (для проверки
связности можно воспользоваться алгоритмом для задачи 11).
Предположим, что некоторый цикл А (не обязательно проходящий через все ребра графа) уже построен и из графа выброшены
ребра цикла (их можно просто отметить как пройденные). Найдем вершину (пусть это вершина к), через которую этот цикл
85
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
проходил, но которой инцидентны некоторые ребра (непройденные). Построим новый цикл В, который начинается в вершине к,
по следующему правилу.
Находясь в текущей вершине цикла (вначале это вершина к),
находим непройденное еще ребро, инцидентное текущей вершине. Это ребро и определяет новую текущую вершину цикла, а
ребро считается пройденным. Построение цикла В продолжается
до тех пор, пока это возможно. Легко понять, что это будет цикл,
так как степень любой вершины четна. Предположим, что построение цикла В завершено. Склеиваем теперь циклы А и В следующим образом. Находим в цикле А (последовательности вершин) вершину к и заменяем ее последовательностью вершин
цикла В. Такой процесс повторяется до тех пор, пока все ребра не
будут пройдены. Описанный процесс можно начинать с пустого
цикла А (пустой последовательности).
Задача 14.
Так как сеть дорог определяет некоторый граф, то определим
в этом графе множество вершин с нечетной степенью. Понятно,
что количество таких вершин четно (так как сумма степеней
вершин графа четна). Определим на этом множестве взвешенный
граф (граф, на ребрах которого определены веса или расстояния)
по следующему правилу. Вес ребра (i,j) равен кратчайшему расстоянию между вершинами, соответствующими i и j в исходном
графе. Построим в этом графе совершенное сочетание минимального веса. Паросочетанием называется множество попарно несмежных ребер (не имеющих общих вершин). Паросочетание называется совершенным, если оно покрывает все вершины. Весом
паросочетания называется суммарный вес входящих в него ребер.
Существуют эффективные алгоритмы поиска совершенного сочетания минимального веса. Однако они очень трудны. Поэтому
при малом количестве вершин в графе можно воспользоваться
перебором всех возможных совершенных паросочетаний. При
добавлении к исходному графу ребер совершенного паросочетания получится граф, у которого все степени вершин четны. Найдем в нем цикл, проходящий по каждому ребру графа ровно один
раз. Этот цикл и является решением задачи. Заметим при этом,
что каждое ребро (i,j) паросочетания должно быть заменено по86
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
следовательностью дорог исходного графа, которая определяет
кратчайшее расстояние между вершинами i и j в исходном графе.
Задача 15.
Производительность конвейера определяется минимальной
производительностью рабочего на конвейере. Поэтому для решения задачи нам достаточно определить максимальную производительность Р, при которой возможно распределить по станкам
всех рабочих, когда для каждого рабочего определен набор станков, на которые он может быть поставлен (понятно, что это те
станки, производительность на которых у рабочего не ниже производительности Р). Легко понять, что для выбранной производительности Х задача определения – возможно ли распределение по
станкам для каждого рабочего – аналогична решению Задачи 4.
Для определения максимальной производительности Р, при которой возможно распределить по станкам всех рабочих, можно
воспользоваться методом дихотомии следующим образом. Отсортируем в одномерном A массиве размера N*N все элементы
C[i,j], 1 <= i,j <= N. Определим левую границу ЛГ = 1 и правую
границу ПГ = N. Для элемента массива А с индексом
СГ = (ЛГ + ПГ)/2, рассматриваемого в качестве возможной максимальной производительности Р, определяем, можно ли распределить по станкам всех рабочих. Если да, то величина возможной
максимальной производительности Р увеличивается. Для этого
пересчитывается значение левой границы по правилу ЛГ:= СГ+1.
Если нет, то величина возможной максимальной производительности Р уменьшается. Для этого пересчитывается значение правой границы по правилу ПГ:= СГ-1. Процесс заканчивается, когда ЛГ >= ПГ. Значение А[ПГ-1] и является максимальной производительностью Р, а конкретное распределение рабочих определяется структурой максимального потока.
Задача 17.
Легко понять, что сеть дорог будет реализовывать некоторый
связный (так как можно проехать из любого города в любой)
граф без циклов (так как одно ребро из цикла можно выбросить, а
связный граф останется связным). Поэтому алгоритм построения
сети дорог минимальной суммарной стоимости очень прост. На
87
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
каждой итерации необходимо находить дорогу минимальной
стоимости, которая не образует цикла с уже выбранными дорогами на предыдущих итерациях. Основную трудность такого решения составляет проверка условия, образуют ли ребра цикл. Однако решение существенно упрощается, если рассматривать только
минимальные ребра только между двумя множествами: множеством помеченных вершин и множеством непомеченных вершин.
Понятно, что эти множества должно соединять хотя бы одно ребро, чтобы граф был связным. Ясно, что оно должно быть минимальным по длине. В описываемом ниже алгоритме это делается
следующим образом.
Для каждой вершины k из множества непомеченных вершин
(а на начальном этапе это все вершины, кроме первой) определяется ближайшая вершина из множества помеченных вершин
БЛИЖ[k]. На каждой итерации определяется кратчайшее ребро
(i,j) между множеством помеченных вершин и множеством непомеченных вершин, используя массив БЛИЖ. Найденное ребро
выбирается для системы дорог, а соответствующая вершина j
считается помеченной. После этого пересчитывается массив
БЛИЖ. При этом учитывается, что изменение некоторой величины БЛИЖ[k] может произойти только тогда, когда расстояние от
k до j меньше, чем от k до БЛИЖ[k].
Алгоритм
для i от 1 до N выполнять
нц
флаг[i]:=0;
БЛИЖ[i]:=1
кц
флаг[1]:=1;
для k от 1 до N-1 выполнять
нц
минрас:=бесконечность;
для i от 2 до N выполнять
если флаг[i]=0 и минрас > C[БЛИЖ[i],i]
то минрас:=C[БЛИЖ[i],i];
j:=i;
все
88
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Вывод ребра (БЛИЖ[j],j)
флаг[j]:=1;
для i от 2 до N выполнять
если флаг[i]=0 и C[БЛИЖ[i],i]>C[i,j]
то БЛИЖ[i]:=j;
все
кц
Задача 19.
Предположим, что мы нашли точку встречи z, и пусть она
лежит на дороге (u,v) длины l на расстоянии d > 0 от дома u и на
расстоянии (l-d) > 0 от дома v. Все множество домов разделим на
два непересекающихся подмножества V и U. В подмножество U
входят те дома, расстояние от которых до дома v меньше, чем
расстояние до дома u. Все остальные дома отнесем к подмножеству U.
Пусть B подмножестве V домов Kv, а в U – Ku, и пусть
Kv > Ku. Обозначим суммарное расстояние от точки z (находящейся на расстоянии d от дома u) до всех N домов через R(z,d).
Очевидно, что R(z,d) = сумма расстояний от v до домов множества V + сумма расстояний от u до домов множества U + Ku*d +
Kv*(L–d). Если мы сдвинем z на расстояние p, p<(L–d) по направлению к дому v, то R(z,d + p) = R(z,d) + Ku*p + Kv*(–p) =
R(z,d) + (Ku – Kv)p < R(z,d), т.е. первоначальная установка точки
z была неверной. Случай Kv<Ku рассматривается аналогично.
Если же Kv = Ku, то точка z может быть на дороге в любом месте, в том числе и в концевых домах. Итак, из всего вышесказанного следует, что искомая точка совпадает с одним из N домов, и
что нам достаточно для каждого из домов i вычислить (например,
по алгоритму Дейкстры) кратчайшее расстояние от него до каждого из оставшихся домов, затем найти сумму этих кратчайших
расстояний (т.е. минимальное суммарное расстояние до всех домов от i). Минимальное из суммарных расстояний по всем i и
даст решение задачи.
Задача 20.
Предполагаемый вариант решения использует полный перебор всех вариантов. В качестве первого звена цепочки берем по89
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
следовательно каждое из N колец. Ищем сцепленные с этим
кольцом, выбираем среди них одно (все остальные кольца будут
считаться удаленными, т.е. строки и столбцы с номерами этих
колец должны обнуляться). С этим изменением задача сводится к
Задаче 1 (Графы). Действительно, если мы найдем максимальный
путь в графе (в данном случае – максимальную длину цепочки в
начальной конструкции), то мы минимизируем количество выброшенных колец.
Задача 21.
Можно сформировать граф, состоящий из 2*N вершин, соответствующих К-гранникам и типу наклеек, причем две вершины
соединены ребром, если одна соответствует наклейке, а другая –
К-граннику, при этом наклейка соответствующего типа находится на соответствующем К-граннике. Добавив в этом графе 2 новые вершины, одна из которых смежна всем вершинам, соответствующим типам наклеек, а другая – всем вершинам, соответствующим К-гранникам, сведем задачу к задаче нахождения максимального потока между этими вершинами.
Задача 22.
Показывается, что точное решение есть максимум из двух
решений, полученных при помощи следующих эвристик:
1) Вершину 1 соединяем последовательно с вершинами 2, 3, ..., N.
Вершину 2 соединяем последовательно с вершинами 3,4,...,N.
......
Вершину i соединяем последовательно с вершинами i+1, i+2,...,N.
......
и так до тех пор, пока хватит проводков.
2) Вершину 2 соединяем с вершиной 1.
Вершину 3 соединяем последовательно с вершинами 1,2.
......
Вершину i соединяем последовательно с вершинами i-1, i-2, ...,1.
......
и так до тех пор, пока хватит проводков.
90
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 23.
Алгоритм нахождения второго минимального расстояния
между двумя вершинами:
По алгоритму Дейкстры находим кратчайший путь между
начальной вершиной N и конечной K, состоящий из дуг a1, ..., as.
Во втором по длине кратчайшем пути из N в K не будет по крайней мере одного из ребер ai. Поэтому алгоритм нахождения этого
второго пути будет следующим:
Для i от 1 до s повторять
удалить из графа ребро (дорогу) ai;
найти кратчайший путь из N в K в новом графе;
если его длина меньше рекордной минимальной длины,
полученной ранее,
то запомнить текущий путь и его длину как рекорд;
восстановить в графе ребро (дорогу) ai;
конец_для;
Этот алгоритм можно найти в книге Кристофидеса "Теория графов. Алгоритмический подход". Но в нем не рассматривается
следующий случай:
D_____E
\
/
\ /
----->----->
A
B
C
Кратчайший путь – ABC, второй – ABDEBC.
Для того чтобы его обработать, достаточно найти кратчайший нетривиальный путь из каждой вершины в нее же. Для этого
в алгоритме Дейкстры достаточно на нулевом шаге не выставлять
пометку "Просмотрено" на начальной вершине.
Задача 24.
Задача для произвольного графа является переборной, для
дерева решается за линейное время. Основная проблема – организовать полный перебор на графе, моделируя движение полицейских по ребрам графа.
91
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Задача 25.
Задача сводится к отысканию самого длинного пути в дереве.
Задача 26.
Поиск чередующихся путей и последовательное увеличение
количества "немонопольных" городов
Задача 27.
Развитие идеи эйлеровости.
Задача 28.
Нахождение эйлерового цикла.
Задача 29.
Нахождение кратчайшего пути и последовательное исключения его ребер.
Задача 30.
Чередующиеся пути.
Задача 31.
Граф позиций и его разметка.
92
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 2
Сортировка и поиск
Оценка трудоемкости алгоритмов
Для решения любой задачи по информатике (олимпиадной
или "обычной") можно использовать разные алгоритмы. Даже у
одного и того же человека, который думает над задачей, в голове
могут возникнуть сразу несколько различных способов ее решения. В данной ситуации появляется вполне естественный вопрос:
а какой же способ лучше?
Слово "лучше" можно понимать по-разному. Под этим чаще
подразумевают простоту реализации на компьютере (на одном из
языков программирования), скорость работы, оптимальность использования оперативной памяти при программной реализации
алгоритма. Чаще всего выбирают тот алгоритм, который "быстрее работает"; иначе говоря, выбирается алгоритм с наименьшей
трудоемкостью. Под трудоемкостью понимают количество простых (элементарных) операций, необходимых для решения задачи с помощью данного алгоритма. Часто нас интересует зависимость трудоемкости алгоритма от объема обрабатываемых данных (например, зависимость трудоемкости алгоритма сортировки
числового массива от количества элементов в нем).
Конечно, в том случае, когда объем обрабатываемых данных
не очень большой, выбор в пользу того или иного алгоритма не
окажет большого влияния на скорость работы (например, то, что
алгоритм будет работать одну миллисекунду, а не десять миллисекунд, вряд ли заметно). Но когда обрабатывается большое количество информации, разница между временем работы различных алгоритмов может быть весьма ощутимой.
Как же сравнить трудоемкость различность алгоритмов? Казалось бы, что может быть проще: запустим разные алгоритмы на
одних и тех же входных данных и сравним время работы! Но
данный способ оценки имеет ряд серьезных недостатков. Во-первых, для того чтобы сравнить трудоемкость алгоритмов, необходимо реализовать их, что не совсем удобно. Во-вторых, сложно
оценить, как будет изменяться время работы алгоритма, если из93
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
менить объем входных данных (можем только проверить опытным путем); на это также уходит достаточно много времени
(время работы даже достаточно эффективного алгоритма при
очень большом объеме обрабатываемых данных может измеряться часами).
Другим способом выяснения трудоемкости является анализ
алгоритма с подсчетом количества операций. Конечно, сделать
это бывает не очень просто (особенно в алгоритмах с большим
количеством вложенных циклов и рекурсивных вызовов процедур). Но в результате мы можем получить зависимость трудоемкости алгоритма от объема входных данных, что позволяет проанализировать, как меняется время работы алгоритма при увеличении объема обрабатываемой информации, можем сравнить
производительность нескольких алгоритмов (причем для этого не
выполнять их программную реализацию).
Чтобы получить некоторое представление о трудоемкости
алгоритма, не обязательно определять точное количество производимых операций, достаточно грубой оценки. Чаще всего оценивают трудоемкость алгоритма с точностью до некоторого постоянного множителя. Действительно, если трудоемкость алгоритма (T(n)) при увеличении объема входных данных (n) в несколько раз возрастает в определенное количество раз, то эта
скорость роста не изменится при умножении T(n) на какое-либо
постоянное число. Например, время работы двух алгоритмов с
трудоемкостью N2 и 5N2 соответственно (где N - объем входных
данных) увеличится в X2 раз при увеличении объема входных
данных в X раз (то есть множитель 5 в оценке трудоемкости второго алгоритма не влияет на порядок роста времени работы).
Также постоянный множитель не играет большой роли при
сравнении трудоемкости двух алгоритмов. Покажем это на простом примере.
Пусть при обработке данных объема N (например, при сортировке массива из N чисел) первый алгоритм совершает 10N2
операций, а второй алгоритм - N3 операций. При небольших значениях N (меньше 10) второй алгоритм будет работать быстрее.
Но при увеличении объема входных данных в X раз трудоемкость первого алгоритма вырастет в X2 раз, а второго - в X3 раз
(то есть гораздо быстрее). Поэтому при N=10 трудоемкость алго94
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ритмов будет одинаковой, при N=1000 трудоемкость первого алгоритма будет в 100 раз меньше (то есть он будет работать в 100
раз быстрее, нежели второй алгоритм), а при N=1 000 000 первый
алгоритм будет работать в 100 000 раз быстрее! При этом увеличение трудоемкости первого алгоритма в несколько раз (сделать
это можно так: вместо коэффициента 10 в оценке трудоемкости
первого алгоритма записать другое, большее число, например,
число 1000) не скажется на порядке скорости роста трудоемкости
(при больших значениях N первый алгоритм будет работать значительно быстрее второго).
По этим причинам часто говорят просто о порядке роста трудоемкости. Например, утверждение, что алгоритм имеет "скорость роста порядка N2" означает, что его трудоемкость может
быть, к примеру, 5N2 или 0,5N2. Также не пишут основание логарифма, так как при переходе к другому основанию появится просто постоянный множитель, на который мы не обращаем внимания (например, log 2 N = (1/log 3 2) log 3 N; то есть, появился постоянный множитель 1/log 3 2).
При оценке трудоемкости обычно оставляют те слагаемые
(чаще всего, одно слагаемое), которые растут быстрее всего при
возрастании объема входных данных. Например, если количество
операций равно 5N2+3N, то также говорят о порядке роста N2, так
как основной "вклад" в скорость роста имеет слагаемое порядка
N2 (которое растет быстрее, чем N).
Сортировка числового массива
Возможности вычислительной техники особенно ярко проявляются в тех задачах, где требуется обработать большое количество информации. Такими, например, являются задачи сортировки
большого объема однотипных данных и поиск информации в них.
В данной главе мы разберем некоторые алгоритмы сортировки одномерного числового массива.
Квадратичные алгоритмы
1. Сортировка выбором
Пусть у нас есть одномерный массив A из N элементов. Нужно отсортировать его по возрастанию.
95
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Идея алгоритма сортировки выбором достаточно проста.
Найдем в массиве наименьший элемент (посмотрев его от начала
до конца) и поменяем его с первым элементом (A[1]). Таким образом, наименьший элемент массива окажется там, где и должен
быть (на первом месте). После этого в оставшейся части массива
(начиная со второго элемента) также найдем наименьший элемент и поменяем его со вторым элементом массива, и так далее.
На шаге с номером k ищем наименьший элемент в части массива,
начиная с k-го элемента, и меняем его с A[k]. После того как будет выполнен N-1 шаг данного алгоритма, массив окажется отсортированным.
Искомая последовательность элементов выстраивается в том
же массиве слева направо, начиная с его начала. Таким образом,
алгоритм не требует дополнительной памяти (требуется лишь завести несколько переменных-счетчиков, причем их количество не
зависит от размера массива).
Реализовать данный алгоритм не составляет большого труда:
…
for k:=1 to N-1 do
begin
m:=k;
for t:=k+1 to N do
if A[t]<A[k] then m:=t;
c:=A[k]; A[k]:=A[m]; A[m]:=c;
end;
…
Оценим трудоемкость алгоритма. Для этого выясним количество сравнений (мы меняем местами элементы реже, чем сравниваем их, поэтому количество операций сравнения позволит выявить порядок роста трудоемкости достаточно точно).
Алгоритм состоит из N-1 шага. На первом шаге выполняется
N-1 операция сравнения. На втором шаге количество обрабатываемых элементов уменьшается на 1, поэтому количество сравнений равно N-2. Аналогично подсчитываем количество сравнений
и на последующих шагах. Итак, общее количество операций
сравнения равно:
T(N) = (N-1) + (N-2) + … + 2 + 1 = N(N-1)/2.
96
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Очевидно, что трудоемкость алгоритма имеет скорость роста
порядка N2 (для того чтобы в этом убедиться, представим найденную оценку трудоемкости в следующем виде: T(N) = 0,5N2 –
0,5N и оставим только первое слагаемое, так как при росте N оно
растет наиболее быстро). Такие алгоритмы со скоростью роста
трудоемкости порядка N2 также называют квадратичными.
Алгоритм также очевидным образом модифицируется для
сортировки алгоритма по убыванию.
2. Сортировка пузырьком
Решим ту же задачу: отсортировать по возрастанию числовой
массив A из N элементов.
При использовании сортировки пузырьком также придется
несколько раз просмотреть массив. Элементы массива A просматривается слева направо (точнее, от начала массива к его концу; в
дальнейшем словами "слева направо" будем обозначать просмотр
элементов массива в порядке роста индексов). При этом просматриваем пары соседних элементов и, если они стоят в порядке убывания (в "неправильном порядке"), меняем их местами.
После просмотра массива оказывается, что самый большой
элемент массива перемещается к концу массива; еще говорят, что
он "всплывает" к концу массива. Для более яркой иллюстрации
"всплывания" массив иногда графически изображают вертикально (внизу – элемент A[1], вверху – A[N]).
Таким образом, после первого прохода самый большой элемент оказывается в конце массива. Осталось отсортировать оставшуюся часть числового массива A. Для этого выполним аналогичный проход по массиву меньшей длины (массив A без последнего элемента), после чего на предпоследнем месте массива
A окажется второй по величине элемент.
Продолжаем выполнять указанные действия. На K-м шаге
просматриваем массив A, за исключением последних K–1 элементов. Для этого мы должны последовательно сравнить каждый
элемент массива A с индексом от 1 до N–K со следующим за ним
элементом.
Просмотр массива совершаем до тех пор, пока размер просматриваемой части массива не окажется равной 1 (общее коли97
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чество проходов будет N–1). Легко заметить, что после этого
массив A окажется отсортированным по возрастанию.
Реализуем данный алгоритм сортировки:
…
for k:=1 to N-1 do
begin
for t:=1 to N-K do
if A[t]>A[t+1] then
begin
c:=A[k];
A[k]:=A[m];
A[m]:=c;
end;
end;
…
Теперь осталось оценить трудоемкость описанного алгоритма. Так же, как и при оценке трудоемкости алгоритма сортировки
выбором, определим количество операций сравнения. Заметим,
что при первом проходе массива выполняется N–1 сравнение,
при втором – N-2 сравнения, и так далее, при последнем – 1 сравнение. Общее количество сравнений равно
T(N) = (N–1) + (N–2) + … + 1 = N(N–1)/2.
Как предыдущий рассмотренный алгоритм (сортировка выбором), алгоритм сортировки пузырьком имеет квадратичную
трудоемкость.
3. Сортировка вставками
При сортировке выбором каждый раз находился элемент для
того, чтобы поместить на определенное место. Иначе говоря,
сначала находили элемент, который должен стоять на последнем
месте, потом – элемент, который должен стоять на предпоследнем месте, и так далее.
Следующий алгоритм сортировки будет выполнять обратные
действия: выбирается не элемент массива, который нужно поставить на данное место, а находится место, куда нужно вставить текущий элемент.
98
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
При сортировке вставками массив условно можно разделить
на две половины: в первой из них элементы упорядочены по возрастанию, во второй – находятся еще не обработанные элементы
массива.
обработанные
элементы
необработанные
элементы
Работу алгоритма можно условно разделить на N–1 шагов
(где N – количество элементов в массиве). На K-м шаге (K меняется от 2 до N; первый элемент обрабатывать не нужно, так как
подлежащая сортировке на первом шаге часть массива состоит из
единственного элемента A[1], поэтому сортировка в этом случае
не требуется) алгоритм находит место для элемента A[K] и помещает его на выбранную позицию.
Поиск нужного места для вставки элемента A[K] происходит
следующим образом: просматриваем элементы с первого до (K–
1)-го до тех пор, пока не встретится первый элемент, больше
A[K] (пусть он имеет индекс M). Если такого элемента не нашлось, то это означает, что элемент A[K] максимальный среди
первых K элементов массива A, поэтому он просто остается на
своем месте.
При вставке элемента A[K] необходимо его запомнить (в некоторой переменной), после этого сместить все элементы с индексами от M до K–1 на одну позицию вправо. Таким образом, в
процессе работы алгоритма сортировки вставками элементы массива не помещаются сразу на нужное место, а могут перемещаться в процессе добавления новых элементов в отсортированную
последовательность.
Реализовать алгоритм решения задачи сортировки массива
вставками можно следующим образом:
99
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
…
for K:=2 to N do
begin
x:=A[K];
M:=1;
while (A[M]<x) and (M<N) do M:=M+1;
if M<N do
for t:=N downto M+1 do A[t]:=A[t-1];
A[M]:=x;
end;
…
Оценим трудоемкость алгоритма. На K-м шаге алгоритма
выполняется порядка M сравнений (при поиске места для вставки) и порядка K–M–1 перемещений элементов, всего порядка K–1
операций на K-м шаге.
Общее количество таких операций:
T(N) = 1 + 2 + … + (N–2) + (N–1) = N(N–1)/2.
Таким образом, и этот алгоритм сортировки имеет квадратичную трудоемкость.
4. Сортировка Шелла
Итак, рассмотренные к данному моменту алгоритмы имеют
трудоемкость порядка N2. Таким образом, порядок роста трудоемкости у этих алгоритмов практически один и тот же, поэтому
особой разницы, какой из этих алгоритмов использовать, нет
(обычно выбирают более простой для реализации алгоритм). Но
стоит еще раз отметить, что приведенные выше алгоритмы сортировки имеет смысл использовать при относительно небольшом
объеме сортируемых данных. В том случае, если объем данных,
подлежащих сортировке, достаточно велик, желательно использовать более эффективные алгоритмы, к рассмотрению которых
мы и переходим.
100
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Быстрые алгоритмы
1. Быстрая сортировка
Алгоритм быстрой сортировки (QuickSort) основан на идее
разделения. При этом некоторым образом (случайно) выбирается
элемент с индексом K, который условно будем называть опорным. После этого просматриваем массив слева направо до тех
пор, пока не найдем элемент A[M] > A[K], а затем просмотрим
массив справа налево, пока не найдется элемент A[R] < A[K].
Меняем их местами и продолжаем такого рода просмотр с обменом до тех пор, пока просматриваемые слева и справа элементы
не "встретятся". В результате слева от A[K] окажутся элементы,
меньшие A[K], а справа – больше A[K]. Этот процесс и называется разделением, а элемент A[K] – центром разделения.
Дальнейшие действия также достаточно очевидны: выполняем процедуру разделения по отношению к полученным двум частям массива. Далее снова проводим разделение полученных частей, и т. д. до тех пор, пока подлежащие сортировке фрагменты
массива не станут достаточно малы (состоять из одного элемента). Легко видеть, что после того как данный алгоритм закончит
свою работу, исходный массив окажется отсортированным по
возрастанию элементов.
Алгоритм достаточно прост и эффективен, поэтому и является стандартной процедурой сортировки в некоторых языках программирования. Порядок роста трудоемкости алгоритма в среднем составляет N*logN.
Точное значение трудоемкости привести не представляется
возможным, так как время работы алгоритма зависит от входных
данных. В самом деле, возможна такая ситуация, когда на каждом
шаге работы алгоритма (при каждом выполнении процедуры разделения) в качестве центра разделения будет выбираться наибольший или наименьший элемент сортируемого фрагмента массива. Конечно, такая ситуация маловероятна, но возможна. В
этом случае алгоритм работает несколько хуже – его трудоемкость можно оценить как N2 (где N – количество элементов в сортируемом массиве). Таким образом, даже в такой неблагоприятной ситуации алгоритм быстрой сортировки работает не хуже
рассмотренных ранее алгоритмов.
101
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Однако рассмотренный алгоритм использует рекурсию. Соответственно, в некоторых случаях большое количество рекурсивных вызовов сведут к минимуму выигрыш от эффективности
алгоритма. Поэтому используют комбинированный алгоритм
сортировки: при сортировке больших фрагментов массива применяется быстрая сортировка, а когда дело доходит до необходимости упорядочить относительно небольшие фрагменты массива,
то применяют менее эффективные, но более простые и не использующие рекурсии алгоритмы (например, сортировку вставками). Это позволяет сделать работу алгоритма более эффективной.
В качестве центра разделения на каждом шаге можно выбирать центральный элемент фрагмента массива. С другой стороны,
для большей устойчивости к "неудобным" входным данным,
центр разделения можно выбирать случайным образом.
Также возможны и другие улучшения работы алгоритма.
Можно заметить, что алгоритм работает тем лучше, чем на более
равные части делится очередной фрагмент центром разделения.
Поэтому центр разделения иногда выбирают следующим образом: случайно выбирается некоторое нечетное количество элементов, из которых выбирается средний. Это позволяет несколько сгладить разницу между размерами фрагментов массива.
2. Сортировка бинарным деревом
В главе "Структуры данных" в качестве одного из примеров
использования деревьев и был приведен алгоритм построения
бинарного дерева поиска. Напомним основные его идеи.
Дерево называется бинарным деревом поиска, если во всех
узлах его левого поддерева записаны числа меньше, чем в корне,
а во всех узлах правого поддерева – больше, чем в корне. То же
самое свойство остается верным для любого его поддерева.
Построение бинарного дерева поиска начинается с того, что
первый из подлежащих сортировке элементов помещается в корень дерева. Далее процедура вставки очередного элемента в дерево такова: если очередной добавляемый элемент меньше, чем
элемент, находящийся в корне, то если у корневого элемента нет
левого сына (пусто левое поддерево), то добавляем этот очередной элемент в качестве левого сына корневого элемента, если же
102
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
левое поддерево не пусто, то проделываем данную процедуру для
левого поддерева. Аналогичные действия выполняем и в том случае, если очередной элемент больше, чем находящийся в корне (в
этой ситуации работаем с правым поддеревом).
При этом предполагали, что дубликатов входная последовательность не содержит. Наличие дубликатов, конечно, ничему не
противоречит: просто очередной элемент добавляем в левое поддерево тогда, когда он меньше либо равен корневому элементу (а
не строго меньше, как раньше).
Очевидно, что описанное ранее бинарное дерево поиска
можно использовать и для сортировки числового массива. Для
этого достаточно последовательно добавить элементы, подлежащие сортировке, в дерево указанного вида (в соответствии с рассмотренным алгоритмом добавления очередного элемента), после
чего обойти дерево в прямом порядке, выписывая каждый раз
очередной просматриваемый элемент.
Данный алгоритм имеет среднюю трудоемкость порядка
N*logN. Но так же, как и алгоритм быстрой сортировки, время
сортировки бинарным деревом зависит от самих сортируемых
данных. Несложно убедиться, что если данные уже были упорядочены, то при добавлении каждого очередного элемента в бинарное дерево поиска (точнее, его уже можно называть бинарным
деревом сортировки) его придется сравнить последовательно со
всеми элементами дерева, при этом трудоемкость алгоритма будет порядка N2. Итак, алгоритм работает медленнее всего тогда,
когда данные уже упорядочены! Такого рода поведение алгоритма сортировки называют неестественным. Соответственно, алгоритм будет работать быстрее тогда, когда в процессе его работы
дерево получается сбалансированным.
Также недостатком алгоритма является то, что для его работы требуется сравнительно много дополнительной памяти.
3. Пирамидальная сортировка
Ранее были рассмотрены алгоритмы сортировки, трудоемкость которых зависит от взаимного расположения входных данных. При этом существовали такие наборы данных, подлежащих
сортировке, при которых алгоритмы работали очень неэффективно.
103
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ниже приведем алгоритм сортировки, который сохраняет
низкую трудоемкость на любых наборах входных данных (то есть
алгоритм, для которого нет "плохих случаев"). Это алгоритм пирамидальной сортировки. Для того чтобы понять, как он работает, необходимо ввести понятие пирамиды.
Итак, пирамидой называется бинарное дерево высоты K, для
которого выполнены следующие условия:
1) дерево является почти полным (то есть все его листья расположены на уровнях K и K–1, причем уровень K–1 заполнен
полностью);
2) уровень K заполнен "слева направо" (если рассматривать
графическое изображение дерева);
3) любой элемент больше, либо равен своим детям (или, иначе говоря, любой элемент меньше либо равен своему родителю).
Легко заметить, что в пирамиде корень не меньше остальных
элементов пирамиды (дерева). То же самое выполняется и для
любого поддерева пирамиды.
Организовать пирамиду можно так же, как и любое другое
бинарное дерево. Например, это можно выполнить в виде списка
(об этом шла речь в главе "Структуры данных"). Однако, учитывая особую структуру рассматриваемого дерева (пирамида является почти полным бинарным деревом), можно предложить более
удобный и оптимальный способ хранения пирамиды в памяти
компьютера – с помощью массива. Элементы дерева (узлы) будут
храниться в массиве A в следующем порядке:
- корень будем хранить в первом элементе массива (P[1]);
- если некоторый узел хранится в P[k], то его левый и правый
сыновья будут храниться в P[2k–1] и P[2k] соответственно.
Данный способ хранения дерева обладает некоторыми преимуществами по сравнению с "универсальным" способом организации деревьев. Легко видеть, что при описанном выше способе в массиве P сначала (в первом элементе) хранится корень, далее – элементы первого уровня, после них – элементы второго
уровня, и так далее. Причем узлы каждого уровня хранятся в массиве P по порядку, слева направо (в порядке возрастания индексов).
104
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Третье условие, накладываемое на пирамиду (в ее определении) выглядит следующим образом: P[k]≥P[2k–1], P[k] ≥P[2k]
(это и означает, что узел не меньше своих детей).
Также стоит отметить, что при данном способе хранения пирамиды нет необходимости отводить дополнительную память
под хранение указателей.
Алгоритм пирамидальной сортировки разбивается на два
этапа. На первом этапе построим пирамиду. Пусть сортировке
подлежит некоторый набор из N чисел (для определенности, будем считать, что они находятся в массиве A). Построение пирамиды будем производить "снизу вверх": вначале заполним в соответствующем массиве элементы с индексами от m+1 до N
(здесь m – целая часть от N/2) подлежащими сортировке элементами. Таким образом, в массив P занесем примерно половину
элементов числового массива, подлежащего сортировке. Заметим, что при этом третье свойство пирамиды не нарушается, так
как для элементов с индексами K от m+1 до N элементов с индексами 2K–1 и 2K не существует (поэтому необходимость в проверке третьего свойства пирамиды отпадает).
Далее последовательно добавляем подлежащие сортировке
элементы к пирамиде, при этом соответствующий массив P будем
заполнять справа налево ("от конца к началу"). При добавлении
элементов будем добиваться того, чтобы свойство пирамиды сохранялось.
Предположим, что добавляем новый элемент в ячейку массива с номером K (то есть, он будет находиться в ячейке P[K]).
Проверяем его сыновей (элементы P[2K–1] и P[2K]) и выбираем
из них наибольшего. После этого сравниваем выбранного сына с
P[K] (с родителем) и, если он не больше P[K], то оставляем все
без изменений (свойство пирамиды не нарушено). Если же выбранный сын оказался больше своего отца, то меняем их местами
и повторяем ту же процедуру (то есть добавленный элемент встал
на место своего сына, с учетом нового положения элемента снова
сравниваем его со своими сыновьями, по необходимости меняем
добавленный элемент с сыном, и так далее). Таким образом, добавленный элемент спускается вниз по пирамиде от уровня к
уровню до тех пор, пока для него не выполнится свойство пира105
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
миды (до тех пор, пока он не станет либо не меньше своих сыновей, либо вообще не будет иметь сыновей).
Затем берем следующий элемент и добавляем его к пирамиде
по описанному выше алгоритму. Так продолжаем действовать до
тех пор, пока все подлежащие сортировке числа не будут добавлены к пирамиде. На этом первый этап алгоритма (построение
пирамиды) можно считать завершенным.
Вообще говоря, для построения пирамиды можно использовать сам подлежащий сортировке массив A. При этом в начале
считаем, что в начале работы элементы с номерами от m+1 до N
уже находятся в пирамиде и остается лишь последовательно обработать остальные элементы массива (справа налево) по указанному выше алгоритму (то есть каждый элемент массива спускается по пирамиде вниз от уровня к уровню до тех пор, пока для
него не будет выполняться третье свойство пирамиды).
После этого переходим ко второму этапу алгоритма (сортировке). Пусть имеется пирамида P (точнее P – это соответствующей пирамиде массив). Далее на этом этапе последовательно выполняем следующие действия:
1) меняем местами первый элемент массива P с последним
(в результате на последнем месте в массиве оказывается
самый большой элемент);
2) рассматриваем в массиве P первые N–1 элементов.
Превращаем данную часть в пирамиду. Для этого (так же,
как и на первом этапе работы алгоритма) первый элемент
массива спускается вниз от уровня к уровню, пока не
будет удовлетворять требуемому третьему условию из
определения пирамиды;
3) первый и второй шаг повторяем последовательно до тех
пор, пока рассматриваемая часть массива P не будет
представлять собой один элемент.
Легко заметить, что после того как будет завершен второй
этап алгоритма, в массиве P будет находиться неубывающая последовательность чисел. Снова стоит отметить, что для выполнения обоих этапов работы алгоритма вспомогательного массива P
можно не заводить, а все указанные выше операции проводить
непосредственно в подлежащем сортировке массиве.
106
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оценим время работы алгоритма. На первом этапе работы
алгоритма строим почти полное бинарное дерево, высота которого будет порядка log2N (более точно: не более [log2N]+1), где N –
количество обрабатываемых элементов. При построении пирамиды очередной элемент может спускаться от уровня к уровню, при
этом операций сравнения и обмена при обработке очередного
элемента будет порядка высоты пирамиды (более того, можно
заметить, что в начале работы высота алгоритма мала, поэтому
время такого "спуска" большинства элементов будет еще меньше,
так что оценка может быть улучшена). Таким образом, выполнение первого этапа работы алгоритма требует порядка N log2N
операций.
На втором этапе работы алгоритма N раз выполняем обмен
первого и последнего элемента и "спуск" первого элемента (корня пирамиды) не более чем на log2N уровней вниз. Поэтому и
второй этап работы алгоритма имеет трудоемкость порядка N
log2N. Итак, общая трудоемкость алгоритма составляет порядка N
log2N.
Данная оценка не зависит от взаимного расположения элементов в исходном массиве, поэтому алгоритм работает эффективно при любых входных данных (в отличие от рассмотренных
раннее алгоритмов, для которых можно было подобрать "неудобные" входные данные, на которых алгоритм работает неэффективно).
4. Поразрядная сортировка
В некоторых случаях для более эффективной сортировки
можно использовать особенности данных, подлежащих сортировке. Следующий алгоритм можно использовать для того, чтобы
упорядочить по возрастанию набор положительных целых чисел.
Для работы алгоритма существенно, чтобы имелось ограничение на количество цифр в числе. Пусть все подлежащие сортировке целые числа имеют не более K цифр. Обозначим общее количество чисел через N, пусть они находятся в массиве A. Для
удобства будем считать, что все числа K-значные (если число
имеет меньше K знаков, то недостающие старшие разряды можно
положить равными нулю; например, если K=5, то число 253
можно записать следующим образом: 00253).
107
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Введем 10 вспомогательных массивов или списков, обозначим их B0, B1, …, B9 (если используются массивы, то пригодятся
также 10 счетчиков количества элементов в соответствующих
массивах). Далее выполним такую последовательность действий:
• Просмотрим массив A от начала до конца и занесем последовательно все числа с последней цифрой 0 в массив
B0 (при этом не меняем их взаимного расположения; то
есть, если элемент X шел раньше элемента Y в массиве A,
то в том случае, если они оба попадут в A0, элемент X
тоже будет идти раньше элемента Y и в новом массиве),
числа с последней цифрой 1 – в массив B1, и так далее,
числа с последней цифрой 9 – в массив B9.
• "Перезапишем" массив A: сначала в него последовательно запишем все элементы массива B0, потом – элементы
массива B1, и т. д., в конце запишем элементы массива
B9. В итоге в массиве A сначала будут идти элементы,
оканчивающиеся на 0, потом – на 1, и так далее, в конце
массива будут идти элементы, оканчивающиеся на 9.
• Потом выполним действия 1-2 для предпоследней цифры
(то есть заносим в массив B0 элементы с предпоследней
цифрой 0, в B1 – с предпоследней цифрой 1, и т. д.),
затем – для второй с конца цифры, и т. д. для всех цифр
(разрядов) с последней до первой.
Несложно убедиться в том, что после окончания работы алгоритма элементы массива A будут располагаться в порядке возрастания (или, если в массиве есть равные элементы, неубывания).
Трудоемкость данного алгоритма линейна по количеству
элементов массива (то есть пропорциональна N). Также трудоемкость алгоритма линейна и по количеству разрядов (K). Таким
образом, при фиксированном значении K алгоритм является достаточно эффективным для сортировки большого количества целочисленных элементов.
Но при сортировке массивов из целых чисел мы как раз и
сталкиваемся с такого рода ситуацией. Чаще всего в распространенных языках программирования под хранение целых чисел отводится 2 или 4 байта, и количество цифр в числах, хранимых
108
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
указанным образом, не превосходит 5 и 10 соответственно. Поэтому при поразрядной сортировке целочисленных массива можно рассматривать каждый элемент как пятизначное (или десятизначное - в зависимости от количества отводимых по целое число
разрядов) число, записанное в десятичной системе счисления.
С другой стороны, можно считать, что числа представлены в
двоичной системе счисления, и организовывать сортировку с
учетом такой формы их представления в памяти компьютера. Таким образом, будем иметь дело с 16-разрядными (или 32-разрядными) двоичными числами. При этом количество вспомогательных массивов сокращается: если раньше использовались массивы
B0, B1, ..., B9 для чисел, имеющих цифру 0, 1, ..., 9 в соответствующем разряде, то сейчас этих массивов будет 2 – B0 и B1 (при
рассмотрении i-го разряда в массив B0 будем записывать числа,
имеющие в данном разряде цифру 0, а в B1 – числа, имеющие в
этом разряде цифру 1). Это позволит несколько сократить объем
используемой дополнительной памяти.
Таким образом, выбор формы представления чисел (десятичная, двоичная или какая-либо другая система счисления) и, соответственно, выбор способа реализации алгоритма поразрядной
сортировки, согласуется с выбором того ресурса, который желательно сэкономить, – времени работы или же объема дополнительной памяти.
Понятно, что алгоритм поразрядной сортировки можно также
использовать и для сортировки наборов строк (слов), только в качестве цифр будут фигурировать буквы некоторого алфавита.
Количество вспомогательных массивов (B0, B1, ...) будет зависеть от того, какова мощность алфавита (количество букв в нем).
5. Сортировка слиянием
Последний из рассматриваемых нами алгоритмов сортировки
основан также на достаточно простой идее. Рассмотрим для начала вспомогательную задачу.
Пусть
есть
два
упорядоченных
набора
чисел:
A1 ≤ A2 ≤ ... ≤ Am (пусть это набор A из m элементов) и
B1 ≤ B2 ≤ ... ≤Bn (набор B из n элементов). Задача: объединить
эти два набора в упорядоченный набор C (из m + n элементов).
109
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Алгоритм решения данной задачи очевиден: на первом шаге
в набор C запишем наименьшее из чисел A1 и B1, после чего это
число удалим из соответствующего набора (если число A1 ≤ B1,
то записываем его в набор C и удаляем из набора A, иначе выбирается число B1, записывается в массив C и удаляется из массива
B). Далее проделываем ту же самую операцию: берем наименьший из первых элементов наборов A и B (к тому времени это уже
не первоначальные наборы – ведь из одного из них мы уже удалили первый элемент), помещаем его в набор C и удаляем из исходного набора (A или B). Эту операцию повторяем до тех пор,
пока не будет заполнен набор C.
Например, есть такие наборы:
A = {3, 4, 12, 16} и B = {5, 13, 14}.
Набор C в начале работы пуст (C = {}). На первом шаге выбираем наименьший из первых элементов наборов A и B (из чисел 3 и 5). Это число 3 - первый элемент набора A. Помещаем его
в набор C и удаляем его из A. Получаем:
A = {4, 12, 16}, B = {5, 13, 14}, C = {3}.
Далее проделываем ту же операцию: снова берем наименьший из первых элементов исходных наборов, это снова первый
элемент набора A (число 4), удаляем его из исходного набора (A),
предварительно поместив в C:
A = {12, 16}, B = {5, 13, 14}, C = {3, 4}.
Потом таким же образом помещаем в набор C число 5 (первый элемент набора B – он больше первого элемента набора A) и
удаляем его из B:
A = {12, 16}, B = {13, 14}, C = {3, 4, 5}.
После этого в набор C перемещается число 12 из набора A:
A = {16}, B = {13, 14}, C = {3, 4, 5, 12}.
Затем помещаем в C число 13 из набора B:
A = {16}, B = {14}, C = {3, 4, 5, 12, 13}.
110
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Потом число 14 из того же набора B:
A = {16}, B = {}, C = {3, 4, 5, 12, 13, 14}.
И на последнем шаге перемещаем в C последний элемент из
набора A (число 16):
A = {}, B = {}, C = {3, 4, 5, 12, 13, 14, 16}.
Как мы видим, именно такой набор C нам и нужно было получить.
Оценим общее количество произведенных операций сравнения. Понятно, что одно сравнение мы делаем на каждом шаге, а
всего таких шагов m+n (столько элементов в наборе C, и столько
элементов было в наборах A и B в сумме). Другими словами, количество операций сравнения равно общему количеству элементов в объединяемых наборах. Общее количество операций будет
"примерно пропорционально" этому количеству.
Теперь перейдем непосредственно к самому алгоритму сортировки слиянием. Идея алгоритма: разобьем массив на упорядоченные наборы, а потом будем сливать их в более крупные. В
итоге получим большой упорядоченный набор чисел (отсортированный массив).
Итак, в начале разобьем исходный массив A на наборы по
одному элементу (понятно, что эти наборы будут упорядоченными). После этого разобьем их на пары и начнем попарно объединять их в более крупные упорядоченные наборы по описанному
выше алгоритму. Полученные наборы снова разобьем на пары и
проделаем ту же операцию слияния наборов и так далее, пока не
получим один набор. Например, для массива
A = [12, 7, 14, 19, 23, 5, 2, 6]
наборы на разных шагах работы алгоритма будут выглядеть следующим образом:
Шаг 0 (начало): {12}; {7}; {14}; {19}; {23}; {5}; {2}; {6}
Шаг 1: {7, 12}; {14, 19}; {5, 23}; {2, 6}
Шаг 2: {7, 12, 14, 19}; {2, 5, 6, 23}
Шаг 3: {2, 5, 6, 7, 12, 14, 19, 23}
111
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Если на каком-то шаге алгоритма последнему набору не находится пары, то просто оставляем его без изменений (не сливаем
ни с каким другим). Серьезно на производительности алгоритма
это не сказывается.
Оценим общее количество операций сравнения. Если в массиве N элементов, то и во всех наборах в сумме на каждом шаге
работы алгоритма будет N элементов. Поэтому на каждом шаге
будет производиться N сравнений. А общее количество шагов
будет порядка log2N. Таким образом, общее количество операций
сравнения будет порядка N∙log2N.
Алгоритм сортировки слиянием используется также для сортировки связных списков (при этом слияние списков и сортировка списка производится абсолютно аналогично), а также для сортировки данных, находящихся в файлах.
Итак, трудоемкость алгоритма сортировки слиянием оказывается примерно такой же, что и у рассмотренных ранее эффективных алгоритмов сортировки числовых массивов (порядка
N∙log2N). Имеет место теорема о том, что это наименьший возможный порядок трудоемкости алгоритмов сортировки сравнениями.
6. Топологическая сортировка
В рассмотренных ранее алгоритмах сортировке подлежал набор чисел. При этом в ходе их работы мы использовали операцию
сравнения, то есть производили определенные действия в зависимости от того, какое из сравниваемых чисел больше. Становится понятно, что те же самые алгоритмы применимы и для сортировки любых других наборов элементов, лишь бы каждые из них
можно было сравнить между собой. Иначе говоря, для осуществления сортировки указанными способами требовалось, чтобы для
каждых двух элементов X и Y из подлежащего сортировке набора
можно было однозначно ответить на вопрос: "Верно ли, что X
меньше либо равен Y?" При этом также говорят, что введено отношение упорядочения.
Таким свойством удовлетворяют не только наборы чисел. К
примеру, между словами (последовательностями букв) также
можно ввести операцию сравнения, для чего достаточно проверять, какое слово стоит раньше по алфавиту (более строго можно
112
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
сказать, что в данном случае используется операция лексикографического сравнения). Это означает, что и для сортировки наборов слов также можно применять описанные ранее алгоритмы,
используя в ходе их работы свойственную им операцию сравнения.
С другой стороны, порой мы встречаемся с задачами, в которых в явном виде для каждой пары элементов не указано, какой
из них какому предшествует. К примеру, есть набор математических утверждений и в доказательстве некоторых из них используются другие утверждения. Задачу сортировки можно в этом
случае поставить следующим образом: расположить утверждения
в такой последовательности, чтобы никакое утверждение не располагалось раньше, чем используемое в его доказательстве. Конечно, такая последовательность может быть не единственной,
поэтому потребуем в задаче нахождение хотя бы одной такой последовательности.
Очевидно, что задач с подобной постановкой существует
достаточно много. Это может быть, к примеру, составление расписания работ, если некоторые виды работ требуют выполнения
других видов перед ними, или выработка последовательности
оформления сложного набора документов в ситуации, когда
оформление некоторых из них уже требует наличия определенной подборки других документов. Поэтому рассмотрим общую
постановку задачи и алгоритм для ее решения.
Определим ориентированный граф, в котором подлежащие
сортировке объекты представляются в виде вершин, некоторые
из которых соединены дугами (стрелками). Например, в задаче
составления расписания работ дуга (стрелка) от A к B будет означать, что для выполнения работы B требуется предварительное
выполнение работы A, а в задаче об упорядочении набора утверждений будем проводить дугу от вершины A к вершине B в том
случае, если утверждение A используется для доказательства утверждения B. Тогда общая формулировка задача выглядит следующим образом: расположить вершины ориентированного графа (орграфа) в такой последовательности, чтобы начало любой
дуги (стрелки) предшествовало ее концу. В такой постановке
данную задачу также называют топологической сортировкой
орграфа.
113
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В общей постановке (если задан произвольный орграф) задача может оказаться неразрешимой. Это происходит, если подлежащий сортировке ориентированный граф имеет цикл. Например,
в задаче об упорядочении набора утверждений наличие цикла означает, что какое-то утверждение косвенно использует себя в
своем же доказательстве, что не позволяет построить требуемую
последовательность. В противном случае, если дан орграф без
циклов (ациклический граф), задача разрешима.
Для доказательства разрешимости задачи для ациклического
орграфа предварительно докажем следующее утверждение: в
ориентированном графе без циклов существует хотя бы одна
вершина, в которую не входит ни одна дуга (стрелка). Доказательство проведем от противного. Предположим, что в каждую
вершину орграфа входит хотя бы одна дуга. Тогда начнем рассмотрение вершин графа с произвольной вершины (A). Так как в
нее входит по крайней мере одна дуга, то рассмотрим произвольную вершину (B), из которой можно по дуге попасть в A. Но в
вершину B по предположению также входит хотя бы одна дуга
(из некоторой вершины C), поэтому перейдем к рассмотрению
вершины C, в которую также входит дуга, и так далее. Таким образом, в силу сделанного предположения о наличии у каждой из
вершин входящей дуги, переход к рассмотрению новой вершины
всегда возможен. Но так как количество вершин конечно, то рано
или поздно мы перейдем к рассмотрению вершины, которую уже
рассматривали на одном из предыдущих шагов, а это свидетельствует о наличии цикла, что противоречит требованию ацикличности орграфа. Полученное противоречие показывает, что первоначальное предположение о наличии хотя бы одной входящей
дуги у каждой из вершин было ложным. Поэтому существует
вершина, не имеющая входящих дуг.
Так как есть вершина, в которую не входит ни одной дуги, то
ее можно смело ставить на первое место в списке подлежащих
сортировке вершин. Действительно, при этом накладываемое при
сортировке на вершины ограничение (нет "обратных дуг" из какой-то последующей вершины в одну из предыдущих) не нарушается и можно перейти к рассмотрению оставшихся вершин.
114
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Это соображение дает нам практически готовый алгоритм
топологической сортировки. Опишем более строго предпринимаемые шаги.
Шаг 1. Найти вершину, в которую
не входит ни одной дуги.
Шаг 2. Добавить ее в качестве очередной
вершины в последовательность
Шаг 3. Удалить из графа данную вершину
со всеми выходящими из нее дугами
Шаг 4. Если в графе не осталось вершин,
то завершить работу алгоритма,
иначе перейти к шагу 1.
Остается только заметить, что при на каждом этапе работы
алгоритма граф остается ациклическим (если бы в полученном
после удалении некоторых вершин и дуг графе был цикл, то он
должен был присутствовать и в исходном графе, что противоречит условию). Поэтому алгоритм работает, а с учетом того обстоятельства, что на каждом шаге ни в какую вершину не ведет
дуга из следующих за ней вершин, последовательность вершин
полностью удовлетворяет условиям поставленной задачи сортировки, значит, алгоритм работает корректно.
Проиллюстрируем работу алгоритма на примере. Рассмотрим
ориентированный граф:
Легко видеть, что в данном графе нет циклов, поэтому топологическая сортировка возможна. В соответствии с алгоритмом,
выберем вершину, в которую не входит ни одна дуга. В приве115
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
денном графе такая вершина единственная (вершина 2). Она и
будет первой вершиной последовательности: S = [2].
Удалим эту вершину вместе со всеми выходящими из нее дугами. Получим следующий граф:
Вершины еще остались, поэтому повторяем данные шаги.
Снова выберем вершину, в которую не входят дуги. В полученном графе таких вершин уже несколько, поэтому можно выбрать
любую из них (например, вершину 3). Добавим ее в последовательность (S = [2, 3]) и удалим вместе с выходящими дугами:
На следующем шаге можно выбрать вершину 4 (в нее не входит ни одной дуги), добавить ее в последовательность (S = [2, 3,
4]) и удалить (дуг из нее не выходит, поэтому просто удаляем
вершину):
В полученном графе есть единственная вершина, у которой
нет входящих дуг (вершина 6), поэтому в последовательность на
данном шаге можно включить только ее: S = [2, 3, 4, 6]. Удаляем
116
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
данную вершину вместе с исходящими дугами, в результате чего
остается граф на двух вершинах:
Теперь осталось добавить к последовательности вершину 1
(S = [2, 3, 4, 6, 1]), удалить ее из графа вместе с исходящим ребром, и в графе остается единственная вершина с номером 5. Остается добавить ее в последовательность (на последнее место) и
удалить, после чего вершин в графе не остается, и алгоритм заканчивает свою работу. Результирующая последовательность
вершин:
S = [2, 3, 4, 6, 1, 5]
Очевидно, такая последовательность в данном случае не
единственная. Выбирая вершины в несколько другом порядке,
можно было получить, к примеру, следующую отсортированную
последовательность: S = [2, 6, 1, 5, 3, 4]. Однако от нас не требовалось находить все возможные упорядоченные последовательности, поэтому задача топологической сортировки полностью
решена.
Осталось рассмотреть детали практической реализации алгоритма. Если граф представлен в виде матрицы инцидентности, то
поиск для поиска вершины без входящих дуг нужно найти столбец, в котором нет ни одной единицы. Очевидно, этот способ не
отличается оптимальностью – для поиска такой вершины порой
приходится просматривать достаточно много столбцов, что требует значительных затрат времени для графов с большим количеством вершин. Для сокращения времени поиска можно завести
дополнительный справочный массив или список, в который будем записывать количество входящих в каждую вершину дуг. Тогда для нахождения вершины, в которую не входят дуги, можно
просмотреть данный справочный массив и найти вершину, для
которой количество входящих дуг равно нулю.
117
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для удаления дуг можно просто удалить соответствующую
строку в матрице инцидентности или пометить ее как удаленную
(и в дальнейшем не рассматривать). Также при удалении дуг следует корректировать массив, в который записывается количество
входящих дуг (достаточно уменьшить на 1 элементы массива, соответствующие вершинам, в которые входят подлежащие удалению дуги). Однако все эти операции (удаление строки из двумерной матрицы инцидентности со смещением, обработка списка
подлежащих рассмотрению дуг) достаточно трудоемкие, так как
ребер может быть достаточно много, в несколько раз больше общего количества вершин.
Непосредственно удалять сами вершины сложнее (для этого
потребуется удалить столбец в матрице инцидентности), поэтому
зачастую проще помечать вершины как удаленные и при дальнейшем поиске вершин без входящих дуг уже не учитывать (например, можно завести список подлежащих рассмотрению вершин, из которого номера удаляемых вершин будут по ходу работы алгоритма исключаться).
Другим вариантом представления граф является матрица
смежности. Рассмотрим, как в данном способе реализуются шаги
алгоритма топологической сортировки. Для поиска вершины, в
которую не входит ни одной вершины, достаточно найти столбец,
в котором нет ни одной единицы. Опять же, для сокращения времени поиска можно ввести дополнительно справочный массив и
хранить в нем количество входящих в каждую вершину дуг.
Удаление дуг в данном случае представления графа производится опять же достаточно просто – достаточно заменить в матрице смежности соответствующие единицы нулями. Удаление
самих вершин является более трудоемкой операции и требует либо удаления строк и столбцов матрицы смежности со смещением,
либо обработки списка учитываемых при работе алгоритма вершин.
Однако, как было ранее отмечено, в некоторых случаях матрица смежности и матрица инцидентности не являются удобными способами представления графов. В том случае, если количество дуг сравнительно невелико, в матрице смежности будут стоять почти одни нули и "концентрация" полезной информации будет мала, а в матрицы инцидентности в каждой строке (длина ко118
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
торой соответствует количеству вершин) будут также стоять значения 1 и –1 в двух столбцах, а остальные ячейки заполнены нулями. Но топологическая сортировка предназначена для линейного упорядочения элементов, отношения между которыми установлены лишь частично. Иначе говоря, лишь для некоторого небольшого количества пар элементов установлено отношение порядка, и на основании этих данных требуется упорядочить все
элементы. Это и соответствует случаю сравнительно малого количества дуг в соответствующем графе.
Такие графы удобнее представлять в компьютере в виде списка дуг с оглавлением. Удаление дуги в графе влечет к ее удалению из списка, а также к корректировке оглавления списка. Если
список дуг представлен в виде массива, то удаление элемента
(дуги) в нем требует значительных временных затрат (необходимо выполнять сдвиг большой части массива на одну позицию
влево). В этой ситуации удобнее в оглавлении отмечать не только
начало, но и конец списка дуг, выходящих из данной вершины.
Начало списка дуг для каждой из вершин будет оставаться неизменным, а конец списка будет изменяться по ходу удаления дуг
из соответствующего графа.
Поиск вершины, в которую не входит ни одной дуги, производить несколько сложнее по той причине, что дуги в списке отсортированы по началам дуг (сначала располагаются дуги, выходящие из первой вершины, потом дуги, исходящие из второй
вершины, и так далее). Номера концов дуг разбросаны достаточно беспорядочно, поэтому поиск по ним затруднен. В связи с
этим возможны два пути:
1. Отсортировать дуги в списке по номерам концов, после чего воспользоваться исходным алгоритмом топологической сортировки.
2. Скорректировать сам алгоритм сортировки так, чтобы он
обеспечивал достаточно эффективную работу для имеющегося
способа представления графа в виде списка ребер.
В первом варианте, конечно, требуется также соответствующим образом организовать оглавление списка. Удаление вершин
и дуг будет производиться описанным выше способом, а поиск
вершины, в которую не входит ни одной дуги, значительно упрощается – так как ребра отсортированы по номерам концов, то
119
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
легко найти вершину, которая не является концом ни одной дуги
(соответствующий ей список входящих дуг будет пустым).
Если оставить прежний способ организации списка ребер, то
корректировка алгоритма также не представляет большого труда.
Основан алгоритм будет на следующем свойстве: в ориентированном графе без циклов существует вершина, из которой не выходит ни одной дуги. Доказательство этого свойства аналогично
приведенному ранее доказательству существования вершины без
входящих дуг. Также, в отличие от рассмотренного ранее варианта алгоритма сортировки, последовательность отсортированных
вершин будет заполняться не с начала, а с конца. Новый алгоритм теперь состоит из следующих шагов:
Шаг 1. Найти вершину, из которой
не выходит ни одной дуги.
Шаг 2. Добавить ее в качестве очередной
вершины в последовательность,
заполняя ее с конца (справа налево)
Шаг 3. Удалить из графа данную вершину
со всеми входящими в нее дугами
Шаг 4. Если в графе не осталось вершин,
то завершить работу алгоритма,
иначе перейти к шагу 1.
Обоснование корректности работы нового алгоритма топологической сортировки проводится аналогично обоснованию работы исходного алгоритма.
В ходе работы скорректированного алгоритма процесс удаления вершин и дуг не претерпевает изменений, а вот поиск вершин, из которых не выходит ни одной дуги значительно ускоряется.
Контрольное задание
Реализуйте предложенные алгоритмы сортировки числового
массива в виде программ, при этом организуйте подсчет следующих параметров:
1) общего количества попарных сравнений элементов;
2) общего количества осуществленных перестановок элементов массива.
120
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Сравните данные алгоритмы, сопоставляя указанные параметры, для следующих примеров массивов:
1) случайный массив (заполняется каким-либо генератором
псевдослучайных чисел);
2) уже упорядоченный массив;
3) массив, упорядоченный в обратном порядке.
Реализуйте предложенные алгоритмы топологической сортировки ориентированного графа для разных способов представления графа в памяти компьютера:
1) матрица смежности;
2) матрица инцидентности;
3) список дуг с оглавлением.
Поиск подстроки в строке
Задача поиска
Помимо сортировки, при работе с большими наборами однотипных данных требуется осуществлять поиск элементов. Конечно, это намного проще сделать тогда, когда данные уже упорядочены. Например, поиск нужного элемента (X) в упорядоченном
по возрастанию числовом массиве размера N часто осуществляется методом деления пополам: рассмотрим среднее число; если
оно меньше X, то число X находится в правой половине массива,
иначе – в левой (предполагаем, что элементы расположены по
возрастанию слева направо). Потом рассматриваем половину
массива, в которой (как мы определили) находится число X: делим уже эту часть массива пополам и выбираем ту часть, где находится элемент X. И так далее, пока элемент (точнее, его положение в массиве) не будет найден. Потребуется на это порядка
log2N операций (что немного, даже для достаточно больших значений N). Однако сама сортировка также требует некоторых затрат времени.
В неупорядоченном массиве искать, конечно же, сложнее.
Для этого придется пользоваться полным перебором элементов
массива, а в худшем случае это потребует порядка N сравнений.
121
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Возникает вполне естественный вопрос, как же лучше поступить: отсортировать массив (затратив на это некоторое время), а
потом быстро осуществлять в нем поиск нужных элементов, или
же заниматься поиском в неотсортированном массиве (но не тратить время на сортировку)? Однозначного ответа на этот вопрос
нет. Конечно, если массив редко изменяется (новые числа не добавляются), а операцию сортировки приходится выполнять достаточно часто, то проще отсортировать массив, а потом осуществлять многократный поиск. Но если массив часто изменяется
(изменяются значения элементов массива или добавляются новые
в динамический массив), то эту сортировку придется осуществлять каждый раз при изменении массива. А это при частых изменениях массива требует значительных затрат времени, что может
свести на нет выигрыш от уменьшения времени поиска. Таким
образом, выбор "стратегии поиска" зависит от конкретной решаемой задачи.
В данной главе мы более подробно рассмотрим другую часто
встречающуюся задачу – поиск подстроки в строке. Сформулировать ее можно следующим образом: имеется строка символов
длины m (эту строку будем называть подстрокой) и строка длины
n (чаще всего можно считать, что m<n). Требуется найти, входит
ли подстрока в строку.
Иногда нужно решить и более общую задачу: найти все вхождения подстроки в данную строку. Но чаще всего эта задача
сводится к предыдущей. Действительно, если найдено первое
вхождение подстроки в строку, то как найти следующее? Очень
просто: пусть первое вхождение подстроки располагается в строке, начиная с позиции k (то есть с k-го символа в строке следует
искомая подстрока). Тогда достаточно рассмотреть строку с
(k+1)-го символа и решить ту же задачу – получим второе вхождение подстроки, и так далее.
Так же, как и для сортировки массива, существует множество
алгоритмов поиска подстроки в строке. Опишем некоторые из
них и сравним их трудоемкость.
122
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. Простой метод поиска
Наиболее простым в реализации, естественным по своей сути, но одним из самых плохих (из соображений трудоемкости)
является такой алгоритм.
Будем проверять каждую букву строки, не является ли она
началом искомой подстроки. Выполним эту проверку для первой
буквы (проверим, не располагается ли искомая подстрока в самом
начале строки). Если с первой буквы в строке искомая подстрока
не располагается, то проверяем, не располагается ли подстрока в
строке, начиная со второй буквы. Если же и для второй буквы
данное условие не выполняется, то переходим к третьей букве, и
т. д. Алгоритм заканчивает работу, если подстрока следует начиная с некоторой позиции, либо в том случае, если такой позиции
нет (подстрока не входит в строку).
Кажется, что может быть естественнее? Конечно, алгоритм
достаточно прост (в том числе и при реализации). Но постараемся
оценить его трудоемкость. В худшем случае нам придется сравнить n-m букв на предмет того, является ли какая-либо из них началом искомой подстроки (таким образом, выполняем n-m операций сравнения подстрок). А для сравнения двух строк длины m
(или для проверки, идет ли строка длины m, начиная с некоторой
позиции, в данной строке) требуется в худшем случае m операций сравнения (так как сравниваем строки посимвольно). Общее
количество операций сравнения будет порядка m∙(n-m).
Чаще всего рассматривают величину m намного меньше величины n (то есть длина искомой подстроки намного меньше
длины строки, в которой осуществляется поиск). В этих допущениях трудоемкость оценивают как n∙m.
Рассмотрим простой пример: хотим найти в книге "Война и
мир" (количество символов в ней порядка 2 – 3 миллионов) кусок
текста, размером в 1000 символов (некоторый абзац). С использованием рассмотренного выше "естественного" алгоритма это
потребует выполнения нескольких миллиардов операций сравнения. Достаточно много.
Такого рода неэффективность может быть следствием неполного использования полученной при сортировке информации.
При использовании рассмотренного выше алгоритма мы "при123
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
кладываем" подстроку к строке сначала с первого символа строки, потом смещаем на один символ вправо, и снова сравниваем, и
так далее. Каждый раз подстрока смещается на одну позицию
вправо и при этом мы абсолютно не делаем выводов из неудачной попытки предыдущего сравнения.
По-видимому, можно улучшить эффективность алгоритма,
если сдвигать искомую подстроку на большее количество символов вправо, учитывая результат предыдущего сравнения. Нужно
постараться сдвигать подстроку вправо на как можно большее
количество позиций так, чтобы быть уверенными в том, что в
пропущенном фрагменте искомой подстроки точно нет.
На такого рода идеях основаны некоторые алгоритмы поиска
подстроки, которые мы рассмотрим далее.
2. Алгоритм Бойера – Мура
В рассмотренном простом методе поиска искомая подстрока
последовательно сопоставлялась с фрагментами строки, сдвигаясь слева направо (от начала строки к ее концу). При этом и сравнение проводилось тоже от начала подстроки к ее концу. При неудачной попытке сравнения подстрока сдвигалась на одну позицию вправо.
В алгоритме Бойера – Мура подстрока также будет смещаться от начала строки к ее концу, но сравнение символов будет
проводиться в обратном порядке — от конца к началу (справа налево). Посмотрим, какие преимущества дает нам такой вариант
сравнения. Приложим подстроку X = x1x2…xm к началу строки
S = s1s2…sn (будем считать, что m – длина подстроки, n – длина
строки). В случае xm ≠ sm совпадения не обнаружено и подстроку
можно сдвинуть вправо.
Конечно, желательно, чтобы при этом сдвиг был максимальным. Если символ sm в подстроке не встречается, то можно сделать вывод, что искомая подстрока не встречается в заданной
строке ни с одной из позиций 1, 2, …, m, поэтому мы можем сместить подстроку вправо на целую длину подстроки и провести
аналогичное сравнение. Однако в том случае, когда в подстроке
присутствует символ sm, то величина возможного сдвига будет
меньше (к примеру, если символ sm стоит в подстроке на предпо124
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
следнем месте, то сдвинуть подстроку мы сможем только на одну
позицию).
Получается, что величина сдвига зависит от того, где именно
в подстроке в последний раз встречается тот или иной символ, на
котором произошло несовпадение. Максимальные сдвиги получаются тогда, когда этого символа либо вообще нет, либо он
встречается разве что ближе к началу подстроки. Для того чтобы
каждый раз не вычислять величину возможного сдвига, можно
перед началом поиска заполнить так называемый массив сдвигов.
Для этого достаточно каждому символу сопоставить расстояние
самого последнего его вхождения в подстроку до конца строки. К
примеру, если символ завершает подстроку, то это расстояние
равно нулю, а если символ расположен на первом месте в подстроке и больше в ней не встречается, то это расстояние равно
m – 1. Если символ в подстроке не встречается, то в массив сдвигов запишем m (действительно, уже упоминалось, что в этом случае можно сдвинуть подстроку на всю её длину, то есть на m позиций).
В таких переменных сдвигах и заключается основная идея
алгоритма Бойера – Мура. Очевидно, таблицу сдвигов можно заполнить до начала поиска, так как ее содержимое по ходу работы
алгоритма не меняется и зависит только от содержимого подстроки.
Алгоритм Бойера – Мура в его простейшей форме можно
описать следующим образом. Предполагаем, что строка символов – это массив S с элементами S[1], S[2], ..., S[n], искомая подстрока – массив X с элементами X[1], X[2], ..., X[m] (n и m –
длина строки и подстроки соответственно).
1) Строим таблицу смещений T:
для каждого символа a элемент T[a] — расстояние от
последнего вхождения символа a до последнего символа искомой подстроки (если символа a в подстроке
нет, то T[a]=m).
2) Совмещаем начало подстроки и начало строки
3) Сравниваем подстроку с фрагментом строки, начиная с последнего символа искомой подстроки.
125
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.1) Если последний символ подстроки (x) не
совпадает с соответствующим символом строки (y),
то сдвигаем подстроку вправо на величину сдвига
T[y], которую берем из таблицы, и снова выполняем
шаг 3.
3.2) Если в пункте 3.1 совпадения последних
символов не обнаружилось, то просматриваем справа
налево всю подстроку, и если какой-то (не последний) символ подстроки не совпадает с соответствующим символом фрагмента строки в таком положении,
то сдвигаем подстроку вправо на 1 символ и снова
выполняем сравнение в соответствии с шагом 3.
3.3) Если все символы подстроки совпадают с соответствующими символами строки (в данном положении), то подстрока найдена и поиск можно прекратить.
Проиллюстрируем работу алгоритма на примере. Будем искать подстроку
X = acdacb
в строке
S = aabbcbabbedcaedacdacbabbd.
Сначала заполняем таблицу смещений T:
a b c d e
2 0 1 3 6
ние:
Далее прикладываем подстроку к строке и начинаем сравне-
aabbcbabbedcaedacdacbabbd
Строка
Подстрока a c d a c b
Несовпадение обнаружилось на третьем с конца символе,
поэтому просто сдвигаем строку на одну позицию вправо и продолжаем сравнение:
126
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
Теперь различаются последние символы подстроки и фрагмента строки, поэтому сдвигаем подстроку на величину сдвига,
которую берем из таблицы: T[a] = 2, поэтому осуществляем сдвиг
на две позиции.
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
Снова несовпадение обнаружилось, но не на последнем
символе, поэтому снова сдвигаем подстроку на одну позицию:
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
При текущем положении подстроки не совпадают последние символы. В данном случае символа e в подстроке нет, поэтому в таблице сдвигов на соответствующем месте стоит число 6,
что позволяет осуществить сдвиг сразу на целую длину подстроки и продолжить сравнение:
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
В таком положении снова мы можем сдвинуться на две позиции вправо (несовпадение на последнем символе, берем из таблицы величину сдвига T[a]=2). Получаем следующее расположение подстроки:
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
127
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Снова последний символ подстроки (b) отличается от соответствующего последнего символа фрагмента строки (d), поэтому можно осуществить сдвиг на величину T[d] = 3:
aabbcbabbedcaedacdacbabbd
Строка
acdacb
Подстрока
Теперь видим, что все символы подстроки совпадают с соответствующими символами строки, и поиск можно считать завершенным.
Очевидно, что этот метод является некоторым улучшением
простого метода поиска: иногда мы сдвигаем подстроку на одну
позицию, но зачастую есть возможность осуществить сразу на
несколько позиций, а порой и на всю длину подстроки. Стоит отметить, что при поиске подстроки в настоящем тексте такая ситуация не будет редкостью: действительно, не стоит ожидать, что
последний символ искомой подстроки будет часто совпадать с
соответствующим символом в тексте, поэтому алгоритм Бойера –
Мура даст нам неплохие результаты (утверждается, что средняя
трудоемкость алгоритма – O(m + n)).
Однако при поиске подстроки в небольшой по длине строки
достаточно много времени уйдет на построение таблицы сдвигов,
что может свести на нет все преимущества алгоритма. Также несложно построить пример, когда алгоритм Бойера – Мура будет
работать крайне неэффективно: при поиске подстроке вида
baa…aa в строке aaaa…aaa (из одних букв "a") на каждом шаге придется просматривать всю подстроку справа налево, при
этом несовпадение будет обнаружено только в самом конце просмотра, а сдвинуть подстроку можно будет только на одну позицию вправо, поэтому время поиска будет иметь порядок mn, что
достаточно много. Поэтому существует достаточно много улучшений алгоритма Бойера – Мура, позволяющих более эффективно учитывать результаты предыдущих сравнений.
128
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3. Алгоритм Кнута – Морриса – Пратта
Простой (наивный) метод поиска подстроки был прост для
понимания, но достаточно неэффективен при работе. Во втором
из рассматриваемых нами эффективных алгоритмов (в алгоритме
Кнута – Морриса – Пратта) все наоборот: достаточно сложен для
понимания, однако обеспечивает более высокую скорость работы.
Для начала разберем несколько вспомогательных утверждений и задач.
Пусть есть некоторое слово S (последовательность букв).
Рассмотрим все его начала, являющиеся одновременно его концами (исключая, конечно, само слово S) и выберем из них самое
длинное. Будем обозначать это самое длинное начало как g(S).
Например: g(abcdab) = ab, g(ababa) = aba, g(abcda) = a.
Вполне возможно, что таких начал в слове S вообще не существует. Тогда будем считать, что g(S) – пустая строка. Например: g(abcd) = пустая строка.
Понятно, что g(S) является и началом, и концом строки S (по
определению). Также не очень сложно показать, что строки из
последовательности g(S), g(g(S)), g(g(g(S))), g(g(g(g(S)))), ... (последовательные применения функции g к строке S) являются и
началами, и концами строки S. Более того, если слово W является
началом и концом слова S, то оно входит в эту последовательность.
Введем еще и такое обозначение: пусть F(S) – длина строки
g(S).
Для успешной работы алгоритма Кнута – Морриса – Пратта
нужно ввести ограничение: у нас должен быть некоторый символ, который не встречается ни в искомой подстроке, ни в строке,
в которой осуществляем поиск. Для текстовых строк такие символы обычно есть (можно взять символы "~", "@", "^", "#"). Этот
символ будем называть разделителем.
Теперь перейдем описанию собственно алгоритма.
Идея алгоритма Кнута – Морриса – Пратта заключается в
следующем: пусть есть некоторое слово S = s1s2s3 ... sm (слово S
состоит из букв s1, s2, s3, ..., sm), будем строить по этому слову
129
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
последовательность L=[l1, l2, ..., lm], причем для каждого значения k от 1 до m должно выполняться соотношение:
lk = F(s1s2s3...sk). Иначе говоря, последовательно для всех k от 1
до m (длины строки S) берем строку, состоящую из первых k
символов строки S (обозначим этот фрагмент из первых k символов строки S как Vk) и записываем в lk длину наибольшего начала строки Vk, являющегося и концом Vk (то есть, lk = F(Vk)).
Итак, мы показали, как по строке S построить последовательность L. Теперь воспользуемся этим для поиска подстроки Y
(длины m) в строке X (длины n). Для этого объединим Y и X в
одну строку с использованием выбранного разделителя (например, "#"), получим строку: Y#X. А теперь построим по строке
Y#X последовательность L указанного выше вида. И если какойлибо элемент последовательности L равен m (длине искомой
подстроки), то подстрока найдена.
Осталось разобраться, как строить последовательность L по
строке S (желательно с минимальными затратами времени).
Последовательность L будем заполнять постепенно. Понятно,
что l1 = 0 (действительно, на первом шаге у нас есть просто строка из одного первого символа строки S, а в односимвольной
строке начала, совпадающего с концом строки, но не являющейся
всей этой строкой, просто нет, поэтому такое начало является
пустой строкой, и его длина равна 0).
Пусть на некотором этапе уже известны первые k элементов
(заполнено начало) последовательности L. Покажем, как, используя имеющиеся данные, найти следующий элемент последовательности L. Обозначим строку, состоящую из первых k символов строки S как Vk (то есть Vk = s1s2s3...sk). Итак, к настоящему
моменту рассмотрены уже все строки Vi, где i – от 1 до k (все начала строки S длиной не более k символов).
Рассмотрим строку Vk+1. Нам нужно найти в ней все начала,
являющиеся одновременно и концами, и выбрать из них наибольшее по длине. Воспользуемся той информацией, которая у нас уже
есть: рассмотрим все начала строки Vk и выберем из них те, за которыми следует символ sk+1, а из всех выбранных таким образом
подходящих начал найдем самое длинное. В конец его припишем
sk+1, получим искомое начало (самое длинное начало строки Vk+1,
являющееся одновременно его концом). А все начала строки Vk,
130
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
являющиеся ее концами, получить просто: достаточно последовательно применять к ней функцию g (причем длины этих строк, получающиеся от последовательных применений функции g у нас
уже есть – они находятся в последовательности L).
Опишем итоговый алгоритм. При этом будем считать, что
строка символов представляет собой массив S длины n (с элементами S[1], ..., S[n]). Последовательность L мы также будем хранить в массиве длины n (элементы этого массива: L[1], L[2], ...,
L[n]). Также нужен некоторый счетчик (целочисленная переменная k) для обращения элементам массива.
В элемент L[1] записать 0;
Далее для всех k от 2 до n-1 выполняем такие действия:
1) В переменную t запишем L[k] (длину наибольшего
начала строки Vk, являющегося к тому же ее началом)
2) Последовательно применяем функцию g. Точнее, ее
значения уже находятся в массиве L (нужно их только
взять). Для этого достаточно в переменную t записать
значение L[t]. Этим мы последовательно переберем все
начала строки Vk, являющиеся ее концами. Эту операцию
повторяем до тех пор, пока переменная t не станет
равна 0 (то есть, нужного начала не
нашлось), или
пока после соответствующего начала строки Vk не окажется символ S[k+1] (а тогда мы, фактически, нашли
нужное начало строки Vk+1, являющееся ее же концом).
3) Если на предыдущем шаге найдено соответствующее
начало строки Vk (это начало длины t), то в L[k+1]
запишем t+1 (начало строки Vk+1 будет на 1 больше —
ведь оно содержит еще и символ S[k+1]). Если же соответствующее начало не найдено, то в L[k+1] запишем 0.
Реализовать этот алгоритм заполнения достаточно просто:
L[1]:=0;
for k:=2 to n-1 do
begin
t:=L[k];
131
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
while (S[t+1]<>S[k+1]) and (t>0) do t:=L[t];
if
S[t+1]=S[k+1]
then
L[k+1]:=t+1
else
L[k+1]:=0;
end;
После того как массив L (по строке Y#X) заполнен, достаточно найти в массиве L элемент, равный длине строки Y (ее
длина равна m). Пусть L[k] = m. Тогда искомая подстрока Y находится второй раз в строке Y#X на позиции k, а это позволяет
определить и номер позиции, начиная с которой подстрока Y начинается и в строке X. Если такого элемента в массиве L нет, то и
подстрока Y в строке X не встречается.
На самом деле, это равенство можно проверять и в процессе
заполнения массива L и, после того как равенство L[k] = m выполнилось, прекращать работу (действительно, зачем дальше заполнять массив L, если уже найдена подстрока).
Контрольное задание
Реализуйте предложенные алгоритмы поиска в виде программы и сравните время выполнения алгоритмов для некоторого
набора примеров (строк и подстрок).
Отдельно проведите сравнение для следующих случаев:
1) поиск короткой подстроки в короткой строке;
2) поиск короткой подстроки (2 – 5 символов) в длинной
строке (несколько тысяч или десятков тысяч символов);
3) поиск длинной подстроки в длинной строке.
132
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Глава 3
Переключение алгоритмов
В этом разделе будут рассмотрены несколько задач, решения которых содержат одну общую идею. Суть её заключается в
том, что оптимальное решение, которое требуется отыскать в задаче, находится среди двух или более различных эвристических
подходов. Идея переключения стратегий поведения программы,
по-видимому, впервые была применена в игре "чет-нечет", суть
которой заключается в отгадывании четности задуманного противником числа. Лучшим методом отгадывания оказывался такой, при котором программа применяла несколько различных
принципов отгадывания, а предпочтение отдавала той стратегии,
которая на данный момент имела наилучшие результаты в текущей игре. В результате, программа "самонастраивалась на противника".
Три нижеприведенные задачи были в разное время предложены на Всероссийских и Международных олимпиадах. Формулировки задач немного изменены.
Проводки
В доску вбито N гвоздиков. В нашем распоряжении имеется
M проводков. Мы должны припаять концы каждого проводка к
двум гвоздикам. Одну пару гвоздиков запрещается соединять
дважды. После того как все сделано, считается, сколько проводков припаяно к каждому гвоздику, полученное число возводится
в квадрат и все квадраты суммируются. Требуется таким образом
выполнить работу, чтобы получившаяся сумма была максимальной.
На языке теории графов задача заключается в нахождении
графа с заданным количеством вершин и ребер, имеющего максимальную сумму квадратов степеней вершин.
133
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Пример 1.
N = 5, M = 4
Два возможных решения:
Первое решение получено после применения следующей
эвристики припаивания проводков: "каждый новый проводок
припаиваем к вершине с наибольшей степенью, так как при этом
квадрат степени растет быстрее всего".
Второе решение опирается на другую эвристику: "стараемся
сделать как можно больше вершин наибольшей возможной степени", для этого некоторое (возможно большее) множество вершин соединяем каждую с каждой, и еще одну вершину соединяем
оставшимися проводками с ранее соединенными.
В первом решении степени вершин: 4, 1, 1, 1, 1. Сумма их
квадратов равна 20.
Во втором решении степени вершин: 3, 2, 2, 1, 0. Сумма их
квадратов равна 18.
Лучшим оказывается алгоритм, опирающийся на первую
эвристику.
Пример 2.
N = 5, M = 6
Два решения, которые основываются на вышеупомянутых
эвристиках, дают следующие картинки.
134
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В первом решении степени вершин: 4, 3, 2, 2, 1. Сумма их
квадратов равна 34.
Во втором решении степени вершин: 3, 3, 3, 3, 0. Сумма их
квадратов равна 36.
Лучшим оказывается алгоритм, опирающийся на вторую эвристику.
Приведенные примеры могут послужить основанием отвергнуть оба эвристических подхода, как, вообще говоря, неверные. При этом поиск универсального правильного алгоритма, отличного от переборного, ни к чему не приводит. Дело в том, и это
можно теоретически доказать, что либо первая упомянутая эвристика, либо вторая всегда оказывается оптимальной. Доказательство этого факта не очень просто. Итак, как же можно было решить нашу задачу? И до одной, и до второй эвристик догадаться
легко, теоретически доказать их правильность невозможно, найти
третью эвристику и доказать её правильность тоже практически
невозможно. Единственным оставшимся подходом является подход переключения эвристик, т.е. расчет решения по каждой из
них, сравнение получившихся результатов и выбор наилучшего
из них.
Проход в метро
В вестибюль станции метро вошли несколько студентов. На
всю компанию у них имеются два проездных билета. Студенты
решают применить для прохода такой способ. Двое проходят через контроль, после чего один из прошедших возвращается в вестибюль с проездными билетами, и все начинается заново, пока
все не пройдут.
Студенты могут передвигаться с различными скоростями.
Известно время, которое каждому студенту требуется для прохода
через контроль. Пусть это же время требуется ему и для выхода.
Требуется определить, за какое наименьшее время все студенты окажутся в метро.
Введем следующие обозначения.
n – количество студентов,
t1, t2, … tn – время прохода через контроль каждого студента.
135
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Ясно, что решение зависит от очередности прохода студентов через контроль и их возвращения.
Пример 1.
n=4
t1 = 4 мин. , t2 = 8 мин., t3 = 9 мин., t4 = 10 мин.
Применим следующую эвристику, которая кажется наиболее естественной. Самый быстрый студент по очереди сопровождает через контроль всех остальных. При этом, на возврат в вестибюль требуется минимально возможное время.
Итак, сначала он ведет второго и возвращается. Время: 8 +
4 = 12 мин.
Переход с третьим и возврат требуют 9 + 4 = 13 мин.
И последнего он переводит за 10 мин.
Всего за 35 минут проходят все. Несложный перебор показывает, что в данном случае это наилучший результат. Но рассмотрим еще один
Пример 2.
n=4
t1 = 4 мин. , t2 = 5 мин., t3 = 9 мин., t4 = 10 мин.
Отличие от предыдущего примера минимально. Теперь
применение нашей эвристики дает следующий результат
Перевод второго и возврат. 5 + 4 = 9 мин.
Переход с третьим и возврат требует 9 + 4 = 13 мин.
И последнего он переводит за 10 мин.
Результат: 32 минуты.
А теперь применим другую, тоже естественную, но немного
более "хитрую" эвристику. Заметим, что основные потери времени происходят во время перехода самых медленных студентов. А
может быть, надо, чтобы такие студенты шли вместе? Тогда времена их прохода совместятся и потери уменьшатся. Чтобы обеспечить такую тактику, отправим сначала через контроль, как и
раньше, самых быстрых студентов, затем один из них возвратится и пошлет двух медленных. После них второй студент возвратится и вместе с первым пройдут в метро. Назовем такую эври136
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
стику "совмещением тормозов". В нашем примере она дает следующий результат.
Переход первого и второго, возврат первого: 5 + 4 = 9 мин.
Переход третьего и четвертого: 10 мин.
Возврат второго: 5 мин.
И последний переход первого и второго: 5 мин.
Результат: 29 минут.
Оказывается, что ни первый, ни второй подходы не гарантируют оптимального результата. Что же делать? Проанализируем ситуацию. Какие еще стратегии прохода в метро могут существовать? Ясно, что либо "совмещение тормозов" надо применять, либо нет. Во втором случае мы получаем первую эвристику.
В первом случае нетрудно понять, что, если и надо каких-то медленных студентов пускать через контроль вместе, то ими должны
быть два самых медленных. Самого медленного из них все равно
надо проводить, а вот вместе с ним можно пустить следующего,
так как при этом не будет потерь времени при его проходе. Получить большего эффекта при "совмещении тормозов" невозможно.
Как можно такое совмещение организовать? Только с помощью
каких-то студентов, которые сначала пройдут вместе, а затем организуют возврат, передачу проездных медленным и повторный
совместный проход. Ясно, что с таким переходом быстрее всего
справятся два самых быстрых студента. Итак, для прохода самых
медленных студентов, либо надо их "совмещать", либо нет. Подсчитать это очень легко.
При совмещении общая потеря времени составит
t2 + t1 + tn + t2 + t2.
Без совмещения: t2 + t1 + tn + t1 + tn–1.
Разница составит: 2t2 – t1 – tn–1. (*)
Если эта разница отрицательна, то лучей оказывается вторая
эвристика, если нет, то первая. Обратим внимание, что после "совмещения" самых медленных студентов вопрос – надо ли совмещать следующих – остается, и его надо решать заново. Если же
разница положительна и "совмещения" делать не надо, то и при
проходе более быстрых студентов разница останется положительна, т.е. "совмещения" делать не надо до конца.
137
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Окончательно, оптимальный по времени алгоритм прохода
студентов в метро выглядит следующим образом:
Если студентов меньше четырех, то самый быстрый проводит остальных.
Если студентов не меньше четырех, то считаем разницу (*).
Если она отрицательна, то организуем "совмещение тормозов" и
продолжаем решать задачу рекурсивно с меньшим количеством
студентов, иначе применяем первую эвристику.
Коррозия металла
Для хранения двух агрессивных жидкостей A и B используется емкость с многослойной перегородкой, которая изготавливается из имеющихся N листов. Для каждого листа i (i = 1, ..., N) известно время его растворения жидкостью A – ai и жидкостью B –
bi. Растворение перегородки каждой из жидкостей происходит
последовательно лист за листом, с постоянной скоростью по
толщине листа. Требуется спроектировать такую перегородку,
время растворения которой было бы максимальным.
Как решать эту задачу? Перебор, очевидно, можно применить только для очень небольших N.
Естественно попробовать так называемый перестановочный
прием. Он заключается в анализе ситуации, когда мы можем переставлять только какие-то два рядом стоящих листа перегородки. Если при одном их расположении мы получим результат, не
худший, чем при другом, то оставляем лучшее расположение.
Эта идея работает во многих алгоритмах, но её применение надо
138
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
серьезно обосновывать. Во-первых, если мы будем последовательно переставлять рядом стоящие листы, то никто не гарантирует конечность данного процесса. Во-вторых, перестановка
листов может привести к тупиковой ситуации, когда никакие два
рядом стоящих листа переставлять не надо, но это не лучший
вариант расположения всех листов.
Итак, перестановочный прием можно попробовать применить, но получение положительного результата не гарантировано.
Однако перестановочный прием наводит на мысль, что существует некоторая характеристика каждого листа, которая для любых двух листов указывает, какой из них должен быть расположен ближе к жидкости A, а какой – к B. Если это так, то получение оптимального результата сведется к простой сортировке листов в соответствии с этой характеристикой. Подумаем, что это за
характеристика.
Пусть у нас всего два листа и время растворения их жидкостями A и B, соответственно равны a1, a2 и b1, b2. Следующие
эвристические соображения совершенно естественны: если a1 >
a2, то первый лист лучше ставить слева, а если b1 > b2, то первый
лист лучше ставить справа. А если выполнено и то и другое?
Возникает идея искать характеристику, учитывающую обе возможности и устанавливающую между ними разумный компромисс. После некоторого раздумья такие характеристики находятся.
Первая – упорядочение производить по убыванию разности
ai – bi.
Вторая – упорядочение производить по убыванию
отношения ai / bi.
Третья – если максимальное из всех времен (и ai и bi) оказывается bi, то ставим i-й лист последним, иначе – первым.
Последняя характеристика оказывается наилучшей в хорошо известном алгоритме Джонсона решения задачи двух станков. Так, на чем остановиться? А не надо выбирать! Пусть программа рассчитает все три варианта и выберет наилучший. Даже
то, что им всегда окажется второй вариант, не должно нас останавливать. Пусть будет выбор, так надежнее. А то, что второй
139
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
вариант действительно оптимален – это совсем не простой теоретический результат.
Контрольное задание
Реализуйте предложенные алгоритмы решения задач в виде
программ.
140
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Литература
1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы. – М.: МЦНМО,
2000.
2. Кнут Д. Искусство программирования для ЭВМ. Т. 1, 2, 3 – М.:
Мир, 1976, 1977, 1978.
3. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. – М.: Мир, 1979.
4. Рейнгольд Э., Нивергельт Ю., Део Н. Комбинаторные алгоритмы. – М.: Мир, 1980.
5. Вирт Н. Алгоритмы и структуры данных. – СПб.: Невский диалект, 2001.
6. Кристофидес Н. Теория графов. Алгоритмический подход. –
М.: Мир, 1978.
7. Препарата Ф., Шеймос М. Вычислительная геометрия: введение. – М.: Мир, 1989.
8. Погорелов А.В. Аналитическая геометрия. – М.: Наука, 1968.
9. Окулов С. Программирование в алгоритмах. – М.: БИНОМ,
2002.
10. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация.
– М.: Мир, 1985.
11. Асанов М. Дискретная оптимизация. – Екатеринбург: Урал
НАУКА, 1998.
12 Шень А. Программирование: Теоремы и задачи. – М.:
МЦНМО, 1995.
13. Кофман А. Введение в прикладную комбинаторику. – М.:
Наука, 1975.
14. Бадин Н., Волченков С., Дашниц Н., Корнилов П. Ярославские олимпиады по информатике. – Ярославль: ИПК, 1995.
15. Андерсон Дж. Дискретная математика и комбинаторика. – М.:
Издательский дом "Вильямс", 2004.
141
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Оглавление
Предисловие ........................................................................................ 3
Глава 1. Алгоритмы на графах ....................................................... 4
Введение.......................................................................................... 4
Определения и примеры................................................................ 6
Представления графов в компьютере ........................................ 10
Алгоритмы нахождения путей в графе ..................................... 14
Поиск кратчайшего пути между двумя вершинами ................ 20
Поиск длин кратчайших путей между всеми вершинами.
Алгоритм Флойда ................................................................. 30
Деревья .......................................................................................... 32
Циклы ............................................................................................ 57
Потоки в сетях .............................................................................. 61
Примеры графовых задач в олимпиадах ................................... 63
Глава 2. Сортировка и поиск ........................................................ 93
Оценка трудоемкости алгоритмов ............................................. 93
Сортировка числового массива .................................................. 95
Поиск подстроки в строке ......................................................... 121
Глава 3. Переключение алгоритмов.......................................... 133
Проводки ..................................................................................... 133
Проход в метро ........................................................................... 135
Коррозия металла ....................................................................... 138
Литература ...................................................................................... 141
142
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Волченков Сергей Геннадьевич
Богомолов Юрий Викторович
Методы построения
эффективных алгоритмов
Учебное пособие
Редактор, корректор: А.А. Антонова
Компьютерная верстка: И.Н. Иванова
Подписано в печать: 30.12.2005 г. формат 60×84 1/8
Бумага тип. Усл. печ. л. 16,74. Уч.-изд. л. 5,4.
Тираж 200 экз. Заказ
Оригинал-макет подготовлен
редакционно-издательским отделом ЯрГУ.
Ярославский государственный университет.
150000 Ярославль, ул. Советская, 14
Отпечатано
ООО «Ремдер» ЛР ИД № 06151 от 26.10.2001.
Ярославль, пр. Октября, 94, оф. 37
тел. (4852) 73-35-03, 58-03-48, факс 58-03-49.
143
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Для заметок
144
Документ
Категория
Без категории
Просмотров
330
Размер файла
999 Кб
Теги
построение, 1067, алгоритм, метод, волченков, эффективные, учебно, пособие
1/--страниц
Пожаловаться на содержимое документа