Файл: Программная инженерия, 18. 04. 2013. Красноярск сфу 2013 2.pdf

5.7. Сильная связность Сильно связной компонентой ориентированного графа называется максимальное множество вершин, в котором существуют пути из любой вершины в любую другую вершину. Метод поискав глубину можно эффективно использовать для нахождения сильно связных компонентов ориентированного графа. Дадим точную формулировку понятия сильной связности. Пусть
G = (V, Е) – ориентированный граф. Множество вершин V разбивается на

116 классы эквивалентности
V
i
, 1 ≤
i ≤ r, так, что вершины v и w будут эквивалентны тогда и только тогда, когда существуют пути из вершины
v в вершину и из вершины w в вершину v. Пусть Е, 1 ≤
i ≤ r, – множество дуг, которые начинаются и заканчиваются в множестве вершин
V
i
. Тогда графы
G
i
= (
V
i
, Е) называются сильно связными компонентами графа
G. Ориентированный граф, состоящий только из одной сильно связной компоненты, называется сильно связным. На рис. 5.23 представлен ориентированный граф с двумя сильно связными компонентами. Эти сильно связные компоненты показаны на рис. 5.24. Рис. 5.23. Ориентированный граф Рис. 5.24. Сильно связные компоненты орграфа из рис. 5.23 Отметим, что каждая вершина ориентированного графа
G принадлежит какой-либо сильно связной компоненте, но некоторые дуги могут не принадлежать никакой сильно связной компоненте. Такие дуги идут от вершины одной компоненты к вершине, принадлежащей другой компоненте. Можно представить связи между компонентами путем создания редуцированного (приведенного) графа для графа
G. Вершинами приведенного графа являются сильно связные компоненты графа
G. В приведенном графе дуга от вершины С к вершине D существует только тогда, когда в графе
G есть дуга от какой-либо вершины, принадлежащей компоненте С, к какой-либо вершине, принадлежащей компоненте
D. Редуцированный граф всегда является ациклическим Рис. 5.25. Редуцированный граф орграфом, поскольку если бы существовал цикл, то все компоненты, входящие в этот цикл, в действительности были бы одной связной компонентой. На рис. 5.25 показан редуцированный граф для графа, изображенного на рис. Теперь рассмотрим алгоритм нахождения сильно связных компонент для заданного ориентированного графа
G.
1. Сначала выполняется поиск в глубину на графе
G. Вершины нумеруются в порядке завершения рекурсивно вызванной процедуры
dfs, те присвоение номеров вершинам происходит после строки (4) в листинге процедуры поискав глубину.
2. Конструируется новый ориентированный граф
G
r
путем обращения направления всех дуг графа
G.
3. Выполняется поиск в глубину на графе, начиная с вершины с наибольшим номером, присвоенным на шаге 1. Если проведенный поиск не охватывает всех вершин, то начинается новый поиск с вершины, имеющей наибольший номер среди оставшихся вершин.
4. Каждое дерево в полученном остовном лесу является сильно связной компонентой графа
G. Применим описанный алгоритм к ориентированному графу, представленному на рис. 5.23. Прохождение вершин графа начнем с вершины аи затем перейдем на вершину
b. Присвоенные после завершения шага 1 номера вершин показаны на рис. 5.26. Полученный путем обращения дуг граф
G
r
представлен на рис. 5.27. Выполнив поиск в глубину на графе
G
r
, получим глубинный остов- ный лес, показанный на рис. 5.28. Обход остовного леса начинается с вершины а, принимаемой в качестве корня дерева, так как она имеет самый высокий номер. Из корня а можно достигнуть только вершины си. Следующее дерево имеет только корень
d, поскольку вершина d имеет самый высокий номер среди оставшихся (но она и единственная оставшаяся вершина. Каждое из этих деревьев формирует отдельную сильно связанную компоненту исходного графа
G. Рис. 5.26. Номера вершин после выполнения шага
1 алгоритма Рис. 5.27. Граф Рис. 5.28. Глубинный остовный лес Выше утверждалось, что вершины строго связной компоненты в точности соответствуют вершинам дерева в остовном лесу, полученном при применении поискав глубину к графу. Докажем это. Сначала покажем, что если вершины
v и w принадлежат одной связной компоненте, то они принадлежат и одному остовному дереву. Если вершины
v и w принадлежат одной связной компоненте, тов графе G существует путь от вершины
v к вершине w и путь от вершины w к вершине
v. Допустим, что поиск в глубину на графе G
r
начат от некоторого корнях и достиг или вершины
v, или вершины w. Поскольку существуют пути в обе стороны) между вершинами
v и w, то обе они принадлежат остовно- му дереву с корнем х Теперь предположим, что вершины
v и w принадлежат одному и тому же остовному дереву в глубинном остовном лесу графа
G. Покажем, что они принадлежат одной и той же сильно связной компоненте. Пусть х – корень остовного дерева, которому принадлежат вершины
v и w. Поскольку вершина
v является потомком вершины х тов графе G
r
существует путь от вершины х к вершине v, а в графе G – путь от вершины v к вершине х В соответствии с прохождением вершин графа
G
r
методом поискав глубину вершина
v посещается позднее, чем вершинах, те. вершинах имеет более высокий номер, чем вершина
v. Поэтому при обходе графа G рекурсивный вызов процедуры
dfs для вершины v заканчивается раньше, чем вызов
dfs для вершины х Но если при обходе графа G вызывается процедура
dfs для вершины v, то из-за наличия пути от вершины v к вершине х процедура dfs для вершины х начнется и закончится до окончания процедуры
dfs(v), и, следовательно, вершинах получит меньший номер, чем вершина
v. Получаем противоречие. Отсюда заключаем, что при обходе графа
G вершина v посещается при выполнении
dfs(x) и поэтому вершина v является потомком вершины х Следовательно, в графе
G существует путь от вершины х к вершине v. Более того, так как существует и путь от вершины
v к вершинех, то вершины хи принадлежат одной сильно связной компоненте. Аналогично доказывается, что вершины хи принадлежат одной сильно связной компоненте. Отсюда вытекает, что и вершины
v и w принадлежат той же сильно связной компоненте, так как существует путь от вершины
v к вершине w через вершину хи путь от вершины w к вершине v через вершину х. Контрольные задания
1. Разработайте программу, реализующую алгоритм Дейкстры нахождения кратчайшего пути от произвольной вершины до остальных вершин ориентированного графа.
2. Разработайте программу, реализующую алгоритм Флойда нахождения кратчайшего пути между всеми вершинами ориентированного графа.
3. Разработайте программу, выполняющую обход ориентированного графа в глубину.
4. Постройте глубинный оставной лес графа и укажите прямые, обратные и поперечные дуги оставных деревьев.
5. Разработайте программу, реализующую алгоритм нахождения сильно связных компонент из параграфа 5.7.

119
6. НЕОРИЕНТИРОВАННЫЕ ГРАФЫ Неориентированный граф
G = (V, Е) состоит из конечного множества вершин
V и множества ребер Е В отличие от ориентированного графа, здесь каждое ребро (
v, w) соответствует неупорядоченной паре вершин если (
v, w) – неориентированное ребро, то (v, w) = (w, v). Далее неориентированный граф будем называть просто графом. Графы широко используются в различных областях науки и техники для моделирования симметричных отношений между объектами. Объекты соответствуют вершинам графа, а ребра – отношениям между объектами
[1]. В этой главе будут описаны различные структуры данных, которые применимы для представления графов. Также будут рассмотрены алгоритмы решения трех типовых задач, возникающих при работе с графами построения минимальных остовных деревьев, определения двусвязных компонент и нахождения максимального паросочетания графа.
6.1. Основные определения Многое из терминологии ориентированных графов применимо к неориентированным графам. Например, вершины
v и w называются смежными, если существует ребро (
v, w). Будем также говорить, что ребро (v, w) инцидентно вершинами Путем называется такая последовательность вершин
v
1
,
v
2
,
…, v
n
, что для всех
i, 1≤ i < п, существуют ребра (v
i
, и,
v
i + 1
). Путь называется простым, если все вершины пути различны, за исключением, возможно, вершин и
v
n
. Длина пути равна количеству ребер, составляющих путь, те. длина равна п – 1 для пути из n вершин. Если для вершин v
i
и
v
n
существует путь
v
1
,
v
2
,
…, v
n
, то эти вершины называются связанными Граф называется связным если в нем любая пара вершин связанная. Пусть есть граф G
= (V, Е) с множеством вершин V и множеством ребер Е Граф G' = (V', Е) называется подграфом графа G, если
1. множество
V' является подмножеством множества V;
2. множество Е' состоит из ребер (v, w) множества Е таких, что обе вершины
v и w принадлежат V'. Если множество Е' состоит из всех ребер (v, w) множества Е таких, что обе вершины
v и w принадлежат V', тов этом случае граф G' называется индуцированным подграфом графа
G. Пока не будет сказано другое, будем считать, что ребро всегда соответствует паре различных вершин.

120 На риса показан граф G = (V, Е) смножеством вершина си множеством дуг Е = {(a, b), (a, d), (b, с, (b, d), (с d)}. На рис. 6.1, б представлен один из его индуцированных подграфов, заданный множеством вершина си содержащий все ребра, не инцидентные вершине. а б Рис. 6.1. Граф и один из его подграфов Связной компонентой графа
G называется максимальный связный индуцированный подграф графа
G. Граф, показанный на риса, является связным графом и имеет только одну связную компоненту, а именно – самого себя. На рис. 6.2 представлен несвязный граф, состоящий из двух связных компонент. Рис. 6.2. Несвязный граф Циклом (простым) называется путь (простой) длины не менее 3 от какой-либо вершины до нее самой. Мы не считаем циклами пути длиной 0, длиной 1 (петля от вершины
v к ней самой) и длиной 2 (путь вида v, w, v). Граф называется циклическим, если имеет хотя бы один цикл. Связный ациклический граф, представляющий собой дерево без корня, называют свободным деревом. На рис. 6.2 показан граф, состоящий из двух связных компонент, каждая из которых является свободным деревом. Свободное дерево можно сделать обычным деревом, если какую-либо вершину назначить корнем, а все ребра сориентировать в направление от этого корня. Свободные деревья имеют два важных свойства, которые будут использоваться в следующих разделах

121 1. Каждое свободное дерево с числом вершин п п ≥ 1, имеет в точности п – 1 ребер.
2. Если в свободное дерево добавить новое ребро, то обязательно получится цикл. Докажем первое утверждение методом индукции поп Очевидно, что утверждение справедливо для п = 1, поскольку в этом случае имеем только одну вершину и не имеем ребер. Пусть утверждение 1 справедливо для свободного дерева с п – 1 вершинами. Рассмотрим дерево G с n вершинами. Сначала покажем, что в свободном дереве существуют вершины, имеющие одно инцидентное ребро. Заметим, что
G не содержит изолированных вершин (те. вершин, не имеющих инцидентных ребер, иначе граф
G не был бы связным. Теперь создадим путь от некоторой вершины
v
1
, следуя по произвольному ребру, инцидентному вершине
v
1
. На каждом шаге построения этого пути, достигнув какой-либо вершины, выбираем инцидентное ей ребро, которое ведет к вершине, еще не участвовавшей в формировании пути. Пусть таким способом построен путь
v
1
,
v
2
, ..., Вершина
v
k
будет смежной либо с одной вершиной
v
k–1
, либо еще с какой- нибудь, не входящей в построенный путь (иначе получится цикл. Впер- вом случае получаем, что вершина
v
k
имеет только одно инцидентное ей ребро, и значит, наше утверждение о том, что в свободном дереве существуют вершины, имеющие одно инцидентное ребро, будет доказано. Во втором случае обозначим через
v
k+1
вершину, смежную с вершиной
v
k
и строим путь
v
1
,
v
2
, ... ,
v
k
,
v
k+1
. В этом пути все вершины различны (иначе опять получится цикл. Так как количество вершин конечно, то этот процесс закончится за конечное число шагом и мы найдем вершину, имеющую одно инцидентное ребро. Обозначим такую вершину через
v, а инцидентное ей ребро через (
v, w). Теперь рассмотрим граф, полученный в результате удаления из графа
G вершины v иребра (v, w). Граф' имеет п – 1 вершину, для него выполняется утверждение 1 и поэтому он имеет
п – 2 ребра. Но граф G имеет на одну вершину и на одно ребро больше, чем граф, поэтому для него также выполняется утверждение 1. Следовательно, утверждение 1 доказано. Теперь докажем утверждение 2 о том, что добавлениеребра в свободное дерево формирует цикл. Применим доказательство от противного, те. предположим, что добавление ребра в свободное дерево не формирует цикл. Итак, после добавления нового ребра получаем граф с п вершинами и п ребрами.Этот граф остался связными, по нашему предположению, ацикличным. Следовательно,этот граф – свободное дерево. Нов таком случае получаем противоречие с утверждением 1. Отсюда вытекает справедливость утверждения 2.

122 Представление неориентированных графов
Для представления неориентированных графов можно применять те же методы, что и для представления ориентированных графов, если неориентированное ребро между вершинами
v и w рассматривать как две ориентированных дугиот вершины
v к вершине w и от вершины w к вершине v. На рис. 6.3 показаны матрица смежности и списки смежности, представляющие граф, приведенный на рис. 6.1,
a.
a b c d
a
0 1 0 1
b
1 0 1 1
c
0 1 0 1
d
1 1 1 0 а б Рис. 6.3. Представления неориентированного графа а – матрица смежности, б – списки смежности Очевидно, что матрица смежности для неориентированного графа симметрична. Отметим, что в случае представления графа посредством списков смежности для существующегоребра (
i, в списке смежности вершины
i присутствует вершина j, а в списке смежности вершины j – вершина
i.
6.2. Остовные деревья минимальной стоимости
Пусть G = (
V, Е – связный граф, в котором каждое ребро (v, w) помечено числом с w), которое называется стоимостью ребра. Остовным деревом графа
G называется свободное дерево, содержащее все вершины V графа
G. Стоимость остовного дерева вычисляется как сумма стоимостей всех ребер, входящих в это дерево. Далее будут рассмотрены методы нахож-
a
b
c
d
b
a
b
a
d
#
b
d
#
c
c
#
d
#

123 дения остовных деревьев минимальной стоимости. На рис. 6.4 показаны граф с помеченными ребрами и его остовное дерево минимальной стоимости. Рис. 6.4. Граф и его остовное дерево минимальной стоимости Типичное применение остовных деревьев минимальной стоимости можно найти при разработке коммуникационных сетей. Здесь вершины графа представляют города, ребра – возможные коммуникационные, линии между городами, а стоимость ребер соответствует стоимости коммуникационных линий. В этом случае остовное дерево минимальной стоимости представляет коммуникационную сеть, объединяющую все города коммуникационными линиями минимальной стоимости. Свойство остовных деревьев минимальной стоимости
Существуют различные методы построения остовных деревьев минимальной стоимости. Многие из них основываются наследующем свойстве остовных деревьев минимальной стоимости, которое для краткости будем называть свойством
ОДМС. Пусть G = (V, Е связный граф с заданной функцией стоимости, определенной на множестве ребер. Обозначим через
U подмножество множества вершин V. Если (и v)– такое ребро наименьшей стоимости, что и
 U и v  V \ U, тогда для графа G существует остовное дерево минимальной стоимости, содержащее ребро (и v). Рис. 6.5. Цикл в остовном дереве Доказать это свойство нетрудно. Допустим противное существует остовное дерево для графа обозначим его ТЕ, содержащее множество и не содержащее ребро (и v), стоимость которого меньше любого остовного дерева для
G, содержащего ребро (и v). Поскольку дерево Т – свободное дерево, то из второго свойства свободных деревьев следует, что добавление ребра (и, v) к этому дереву приведет к образованию цикла. Этот цикл содержит ребро (и v) и будет содержать другое ребро (и v') такое, что и'
 U и v'  V \ U, как показано на рис. 6.5. Удаление ребра (и v') приведет к разрыву цикла и образованию ос- товного дерева, чья стоимость будет не выше стоимости дерева Т, поскольку сиси Приходим к противоречию с предположением, что остовное дерево Т – это дерево минимальной стоимости. Алгоритм Прима
Существуют два популярных метода построения остовного дерева минимальной стоимости для помеченного графа
G = (V, Е, основанные на свойстве ОДМС. Один такой метод известен как алгоритм Прима (
Prim). В этом алгоритме строится множество вершин
U, из которого вырастает остовное дерево. Пусть
V = {1, 2, …, п. Сначала U = {1}. На каждом шаге алгоритма находится ребро наименьшей стоимости (и v) такое, что и
 U и
v
 V \ U, затем вершина v переносится из множества V \ U в множество U. Этот процесс продолжается до тех пор, пока множество
U не станет равным множеству
V. Процесс построения остовного дерева для графа из риса показан на рис. 6.6, эскиз же алгоритма следующий
procedure Prim (G: граф var T: множество ребер) ;
var U: множество вершин
и v: вершина
begin
T := 0; U := {1};
while U ≠ V do begin нахождение ребра (и v) наименьшей стоимости и такого, что и
 U и v  V \ U
T := Т и v)};
U := U
{v}
end Если ввести два массива, то можно сравнительно просто организовать на каждом шаге алгоритма выбор ребра с наименьшей стоимостью, соединяющего множества
U и V \ U. Массив CLOSEST[i] для каждой вершины из множества V \ U содержит вершину из U, с которой он соединен ребром минимальной стоимости (это ребро выбирается среди ребер, инцидентных вершине
i, и которые ведут в множество U). Другой массив
LOWCOST[i] хранит значение стоимости ребра (i, CLOSEST[i]). а
б в
г
д Рис. 6.6. Последовательность построения остовного дерева алгоритмом Прима На каждом шаге алгоритма просматривается массивна- ходится минимальное значение
LOWCOST[k]. Вершина k принадлежит множеству
V \ U и соединена ребром с вершиной из множества U. Затем выводится на печать ребро (
k, CLOSEST[k]). Так как вершина k присоединяется к множеству
U, то вследствие этого изменяются массивы LOWCOST и
CLOSEST. На вход алгоритма Прима поступает массив С размера п х п, чьи элементы
C[i, j] равны стоимости ребер (i, j). Если ребра (i, j) не существуют, то элемент
C[i, j] полагается равным некоторому достаточно большому числу. После нахождения очередной вершины
k остовного дерева
LOWCOST[k] приравнивается значению равному infinity (бесконечность, очень большому числу, такому, чтобы эта вершина уже в дальнейшем не рассматривалась. Значение числа
infinity должно быть больше стоимости любого ребра графа. Время выполнения алгоритма Прима имеет порядок п. Если значение п достаточно большое, то использование этого алгоритма нерационально. Далее рассматривается алгоритм Крускала нахождения остовного

126 дерева минимальной стоимости, который выполняется за время порядка е log e), где е – количество ребер в данном графе. Если е значительно меньше п, то алгоритм Крускала предпочтительнее, но если е близко к n
2
, рекомендуется применять алгоритм Прима. Алгоритм Крускала Снова предположим, что есть связный граф G = (
V, Е) с множеством вершин
V = {1, 2, ..., пи функцией стоимости с, определенной на множестве ребер Е. В алгоритме Крускала (Kruskal) построение остовного дерева минимальной стоимости для графа
G начинается с графа Т = (V,
), состоящего только из
n вершин графа G и не имеющего ребер. Таким образом, каждая вершина является связной (с самой собой) компонентой. В процессе выполнения алгоритма имеем набор связных компонент, постепенно объединяя которые формируем остовное дерево. При построении связных, постепенно возрастающих компонент поочередно проверяются ребра из множества Ев порядке возрастания их стоимости. Если очередное ребро связывает две вершины из разных компонент, тогда оно добавляется в граф
T. Если это ребро связывает две вершины из одной компоненты, то оно отбрасывается, так как его добавление в связную компоненту, являющуюся свободным деревом, приведет кобра- зованию цикла. Когда все вершины графа
G будут принадлежать одной компоненте, построение остовного дерева минимальной стоимости Т для этого графа заканчивается. Рассмотрим помеченный граф, представленный на риса. Последовательность добавления ребер в формирующееся дерево Т показана на рис. 6.7. Ребра стоимостью 1, 2, 3 и 4 рассмотрены первыми и все включены в Т, поскольку их добавление не приводит к циклам. Ребра (1, 4) и (3, 4) стоимостью 5 нельзя включить в Т, так как они соединяют вершины одной и той же компоненты (рис. 6.7, г) и поэтому замыкают цикл. Но оставшееся ребро (2, 3) также стоимостью 5 не создает цикл. После включения этого ребра в Т формирование остовного дерева завершается. Этот алгоритм можно реализовать, основываясь на множествах (для вершин и ребер) и операторах работы сними. Прежде всего, необходимо множество ребер Е, к которому можно было бы последовательно применять оператор
DELETEMIN для отбора ребер в порядке возрастания их стоимости. Поэтому множество ребер целесообразно представить в виде очереди с приоритетами и использовать для нее частично упорядоченное дерево в качестве структуры данных. Необходимо также поддерживать набор С связных компонент, для чего можно использовать следующие операторы
1. Оператор
MERGE(A, В С) объединяет компоненты Аи Виз набора Си результат объединения помещает или в А, или в В.

127 2. Функция
FIND(v, С) возвращает имя той компоненты из набора С, которая содержит вершину
v.
3. Оператор
INITIAL(A, v, С) создает в наборе С новую компоненту с именем А, содержащую только одну вершину v. а
б в
г
д Рис. 6.7. Последовательное формирование остовного дерева минимальной стоимости посредством алгоритма Крускала Введем для множеств абстрактный тип данных
MFSET, поддерживающий операторы
MERGE и FIND. Будем использовать этот тип данных в эскизе программы, реализующей алгоритм Крускала:
procedure Kruskal (V: SET; E: SET;var T: SET ) ;
{
V – множество вершин, E и Т — множества дуг
var
ncomp: integer; текущее количество компонент
edges: PRIORITYQUEUE;
множество дуг, реализованное как очередь с приоритетами
components: SET;
множество
V, сгруппированное во множество компонент и, v: вершина

128 е ребро
nextcomp: integer; имя (номер) новой компоненты
исотр, vcomp: integer; имена (номера) компонент
begin Т
MAKENULL(edges);
nextcomp := 0; р := число элементов множества V;
for v
 V do begin инициализация компонент, содержащих по одной вершине из
V}
nextcomp := nextcomp + 1;
INITIAL(nextcomp, v, components)
end;
for е
 E do инициализация очереди с приоритетами, содержащей ребра }
INSERT(e, edges);
while ncomp > 1 do begin рассматривается следующее ребро е := DELETEMIN(edges); пусть е = (и v);
исотр := FIND(u, components);
vcomp := FIND(v, components);
if исотр <> vcompthen begin
ребро е соединяет две различные компоненты
MERGE(исотр, vcomp, components);
ncomp := ncomp – 1; е, Т)
end
end Время выполнения этой программы зависит от двух факторов. Если в исходном графе
G всего e ребер, то для вставки их в очередь с приоритетами потребуется время порядка е log e). Каждая итерация цикла while для нахождения ребра с наименьшей стоимостью в очереди
edges требует времени порядка
O(log e). Поэтому выполнение всего этого цикла в самом худшем случае потребует времени
O(e log e). Вторым фактором, влияющим на время выполнения программы, является общее время выполнения операторов
MERGE и FIND, которое зависит от метода реализации абстрактный тип данных
MFSET. В любом случае алгоритм Крускала может быть выполнен за время е log e).

129

1   ...   6   7   8   9   10   11   12   13   14

---

6.3. Обход неориентированных графов
Во многих задачах, связанных с графами, требуется организовать систематический обход всех вершин графа. Существуют два наиболее часто используемых метода обхода графов поиск в глубину и поиск в ширину, о которых речь пойдет в этом разделе. Оба этих метода можно эффективно использовать для поиска вершин, смежных сданной вершиной. Поиск в глубину
Напомним, что в разделе 5.5 был построен алгоритм
dfs для обхода вершин ориентированного графа. Этот же алгоритм можно использовать для обхода вершин и неориентированных графов, поскольку неориентированное ребро (
v, w) можно представить в виде пары ориентированных дуги. Фактически построить глубинный остовный лес для неориентированного графа (те. совершить обход его вершин) даже проще, чем для ориентированного. Во-первых, заметим, что каждое дерево остовного леса соответствует одной связной компоненте исходного графа, поэтому, если граф связный, его глубинный остовный лес будет состоять только из одного дерева. Во-вторых, при построении остовного леса для орграфа мы различали четыре типа дуг дуги дерева, передние, обратные и поперечные дуги, а для неориентированного графа в этой ситуации выделяют только два типа ребер ребра дерева и обратные ребра. Так как для неориентированного графа не существует направления ребер, то, естественно, прямые и обратные ребра здесь не различаются и объединены общим названием обратные ребра. Аналогично, так как в остовном дереве для неориентированного графа вершины не делятся на потомков и предков, тонет и перекрестных ребер. В самом деле, пусть есть ребро (
v, w) и предположим, что при обходе графа вершина
v достигнута раньше, чем вершина w. Тогда процедура
dfs(v) не может закончиться раньше, чем будет рассмотрена вершина
w. Поэтому в остовном дереве вершину w можно считать потомком вершины
v. Но подобным образом, если сначала вызывается dfs(w), вершина
v становится потомком вершины w. Итак, при обходе вершин неориентированного графа методом поискав глубину все ребра делятся наследующие группы
1. Ребра дерева – это такие ребра (v, w), что при обходе графа процедура) вызывается непосредственно перед процедурой dfs(w) или, наоборот, сначала вызывается процедура
dfs(w), а затем сразу процедура
dfs(v).
2. Обратные ребра – такие ребра (

---

v, w), что ни процедура dfs(w) не следует непосредственно за процедурой
dfs(v), ни процедура dfs(v) не следует непосредственно за процедурой
dfs(w) (те. между вызовами этих процедур следуют вызовы нескольких других процедур Рассмотрим связный граф
G на риса. Остовное дерево для этого графа, полученное методом поискав глубину, показано на рис. 6.8, б. Поиск был начат с вершины а, ребра дерева изображены сплошными линиями, а обратные ребра – пунктирными. Изображение остовного дерева начато от корня, и сыновья каждой вершины рисовались слева направо в том порядке, в каком они впервые посещались в процедуре
dfs.
а
б Рис. 6.8. Граф и остовное дерево, полученное при обходе его вершин методом поискав глубину Опишем несколько шагов поискав глубину для данного графа. Процедура) добавляет ребро (а b) в остовное дерево Т, поскольку вершина ранее не посещалась, и вызывает процедуру dfs(b). Процедура dfs(b) добавляет ребро (
b, d) в остовное дерево Т ив свою очередь вызывает процедуру. Далее процедура dfs(d) добавляет в остовное дерево ребро (d,
e) и вызывает dfs(e). С вершиной е смежны вершины аи, но они помечены как посещенные вершины. Поэтому процедура
dfs(e) заканчивается без добавления ребер в дерево Т. Процедура dfs(d) также находит среди вершин, смежных с вершиной
d, только вершины, помеченные как посещенные. Процедура
dfs(d) завершается без добавления новых ребер в ос- товное дерево. Процедура
dfs(b) проверяет оставшиеся смежные вершины аи е (до этого была проверена только вершина d). Эти вершины посещались ранее, поэтому процедура
dfs(b) заканчивается без добавления новых
1
Здесь приведены конструктивные определения ребер дерева и обратных ребер. Можно дать следующие, менее конструктивные, но более общие, определения если при обходе графа достигнута вершина v, имеющая инцидентное ребро (v, w), тов случае, когда вершина w еще не посещалась вовремя этого обхода, данное ребро является ребром дерева, если же вершина w уже посещалась ранее, то ребро (v, w) – обратное ребро.

131 ребер в дерево Т. Процедура dfs(a), продолжая работу, находит новые вершины, которые ранее не посещались. Это вершины си. Поиск в ширину Другой метод систематического обхода вершин графа называется поиском в ширину. Он получил свое название из-за того, что при достижении вовремя обхода любой вершины
v далее рассматриваются все вершины, смежные с вершиной
v, те. осуществляется просмотр вершин вши- рину». Этот метод также можно применить и к ориентированным графам. Также, как и при применении поиска вглубь, посредством метода поискав ширину при обходе графа создается остовный лес. Если после достижения вершины х при рассмотрении ребрах, у) вершина у не посещалась ранее, то это ребро считается ребром дерева. Если же вершина у уже посещалась ранее, то ребро (х убудет поперечным ребром, так как оно соединяет вершины, несвязанные наследованием друг друга. При выполнении алгоритма поискав ширину, ребра дерева помещаются в первоначально пустой массив Т, формирующий остовный лес. Посещенные вершины графа заносятся в очередь
Q. Массив mark (метка) отслеживает состояние вершин если вершина
v пройдена, то элемент mark[v] принимает значение
visited (посещалась, первоначально все элементы этого массива имеют значение
unvisited (не посещалась. Отметим, что в этом алгоритме во избежание повторного помещения вершины в очередь пройденная вершина помечается как
visited до помещения ее в очередь. Процедура поискав ширину работает на одной связной компоненте. Если граф не односвязный, то эта процедура должна вызываться для вершин каждой связной компоненты. Эскиз процедуры
bfs
1
, реализующей алгоритм поискав ширину представлен ниже.
procedure bfs (v);
{
bfs обходит все вершины, достижимые из вершины
v}
var
Q: QUEUE очередь для вершин х у вершина
begin
mark[v]:= visited;
ENQUEUE(v, Q);
while not EMPTY(Q) do begin
x := FRONT(Q) ;
DEQUEUE(Q);
for для каждой вершины у, смежной с вершиной х do
1
Название процедуры bfs является сокращением от breadth-first search, что обозначает поиск в ширину.

132
if mark[y] = unvisited then begin
mark[y] := visited;
ENQUEUE(y, Q); х, у) , T)
end
end
end;
Остовное дерево для графа из риса, построенное методом поискав ширину, показано на рис. 6.9. Здесь обход графа начат с вершины а Как и ранее, ребра дерева показаны сплошными линиями, а остальные ребра – пунктирными. Отметим также, что дерево нарисовано от корня, а все сыновья любой вершины располагаются слева направо в порядке их посещения. Рис. 6.9. Остовное дерево для графа, изображенного на риса, полученное методом поискав ширину Время выполнения алгоритма поискав ширину такое же, как и для алгоритма поискав глубину. Каждая пройденная вершина помещается в очередь только один раз, поэтому количество выполнении цикла совпадает с количеством просмотренных вершин. Каждое ребро (х у) просматривается дважды, один раз для вершины хи один раз для вершины у. Поэтому, если граф имеет п вершин и е ребер, а также если для представления ребер используются списки смежности, общее время обхода такого графа составит ах, е. Поскольку обычное п, то получаем время выполнения алгоритма поискав ширину порядка е, те. такое же, как и для алгоритма поискав глубину. Метод поискав ширину можно использовать для обнаружения циклов в произвольном графе, причем за время п) (п – количество вершин графа, которое не зависит от количества ребер. Как показано в разделе 6.1, граф с п вершинами и с n или большим количеством ребер обязательно имеет цикл. Однако если в графе пили меньше ребер, то цикл может быть только в том случае, когда граф состоит из двух или более связных

133 компонент. Один из способов нахождения циклов состоит в построении остовного леса методом поискав ширину. Тогда каждое поперечное ребро
(
v, w) замыкает простой цикл, состоящий из ребер дерева, ведущих к вершинами от общего предка этих вершин, как показано на рис. 6.10. Рис. 6.10. Цикл, найденный методом поискав ширину Методы поисков в глубину ив ширину часто используются как основа при разработке различных эффективных алгоритмов работы с графами. Например, оба этих метода можно применить для нахождения связных компонент графа, поскольку связные компоненты представимы отдельными деревьями в остовном лесу графа.
6.4. Точки сочленения и двусвязные компоненты Точкой сочленения графа называется такая вершина
v, когда при удалении этой вершины и всех ребер, инцидентных вершине
v, связная компонента графа разбивается на две или несколько частей. Например, точками сочленения для графа из риса являются вершины аи с. Если удалить вершину а, то граф, который является одной связной компонентой, разбивается на два треугольника {
b, d, е и с, f, g}. Если удалить вершину сто граф расчленяется на подграфы а, b, d, е и {f, g}. Но если удалить какую-либо другую вершину, тов этом случае не удастся разбить связную компоненту на несколько частей. Связный граф, не имеющий точек сочленения, называется двусвязным Для нахождения двусвязных компонент графа часто используется метод поискав глубину. Метод нахождения точек сочленения часто применяется для решения важной проблемы, касающейся связности графов. Граф называется k- связным, если удаление любых
k — 1 вершин не приведет к расчленению графа В частности, граф имеет связность 2 или выше тогда и только то Существует другое, более конструктивное определение связности. Граф называется связным, если между любой парой вершин v и w существует не менее k разных путей, таких, что, за исключением вершин v и w, ни одна из вершин, входящих в один путь, не входит нив какой другой из этих путей.

134 гда, когда он не имеет точек сочленения, те. только тогда, когда он является двусвязным. Чем выше связность графа, тем больше можно удалить вершин из этого графа, не нарушая его целостности, те. не разбивая его на отдельные компоненты. Опишем простой алгоритм нахождения всех точек сочленения связного графа, основанный на методе поискав глубину. При отсутствии этих точек граф, естественно, будет двусвязным, те. этот алгоритм можно рассматривать также, как тест на двусвязность неориентированного графа.
1. Выполняется обход графа методом поискав глубину, при этом для всех вершин
v вычисляются числа dfnumber[v], введенные в разделе 5.5. В сущности, эти числа фиксируют последовательность обхода вершин в прямом порядке вершин глубинного остовного дерева.
2. Для каждой вершины
v вычисляется число low[v] равное минимуму чисел
dfnumber потомков вершины v, включая и саму вершину v, и предков
w вершины v, для которых существует обратное ребро (х w), где х – потомок вершины v. Числа low[v] для всех вершин v вычисляются при обходе остовного дерева в обратном порядке, поэтому при вычислении
low[v] для вершины v уже подсчитаны числа low[x] для всех потомков х вершины
v. Следовательно, low[v] вычисляется как минимум следующих чисел а)
dfnumber[v]; б)
dfnumber[z] всех вершин z, для которых существует обратное ребро в)
low[x] всех потомков х вершины v.
3. Теперь точки сочленения определяются следующим образом а) корень остовного дерева будет точкой сочленения тогда и только тогда, когда он имеет двух или более сыновей. Так как в остовном дереве, которое получено методом поиска вглубь, нет поперечных ребер, то удаление такого корня расчленит остовное дерево на отдельные поддеревья с корнями, являющимися сыновьями корня построенного остовного дерева б) вершина
v, отличная от корня, будет точкой сочленения тогда и только тогда, когда имеет такого сына что low[w]≥ dfnumber[v]. В этом случае удаление вершины
v (и, конечно, всех инцидентных ей ребер) отделит вершину
w и всех ее потомков от остальной части графа. Если же
low[w] < dfnumber[v], то существует путь по ребрам дерева к потомкам вершины
w и обратное ребро от какого-нибудь из этих потомков к истинному предку вершины
v (именно значению dfnumber для этого предка равно. Поэтому в данном случае удаление вершины v не отделит от графа поддерево с корнем
w. Числа
dfnumber и low, подсчитанные для вершин графа из риса, показаны на рис. 6.11. В этом примере вычисление чисел
low начато в обратном порядке с вершины е. Из этой вершины выходят обратные ребра (е

135 аи (е, b), поэтому low[e] = min(dfnumber[e], dfnumber[a], dfnumber[b]) = 1. Затем рассматривается вершина
d, для нее low[d] находится как минимум чисел
dfnumber[d], low[e] и dfnumber[a]. Здесь число low[e] участвует потому, что вершина е является сыном вершины d, а число dfnumber[a]– из- за того, что существует обратное ребро (
d, а. Рис. 6.11. Числа dfnumber и low, подсчитанные для графа, изображенного на риса Для определения точек сочленения после вычисления всех чисел
low просматривается каждая вершина остовного дерева. Корень а является точкой сочленения, так как имеет двух сыновей. Вершина с также является точкой сочленения – для ее сына, вершины
f, выполняется неравенство
low[f]≥ dfnumber[c]. Другие вершины не являются точками сочленения. Время выполнения описанного алгоритма на графе с
n вершинами и е ребрами имеет порядок е. Можно легко проверить, что время, затрачиваемое на выполнение каждого этапа алгоритма, зависит или от количества посещаемых вершин, или от количества ребер, инцидентных этим вершинам, те. в любом случае время выполнения, с точностью до константы пропорциональности, является функцией как количества вершин, таки количества ребер. Поэтому общее время выполнения алгоритма имеет порядок
O(n + е) или е, что тоже самое при n ≤ е.
6.5. Паросочетания графов В этом разделе будет описан алгоритм решения задачи о паросоче- тании» графов. Простым примером, приводящим к такой задаче, может служить ситуация распределения преподавателей по множеству учебных курсов. Надо назначить на чтение каждого курса преподавателя определенной квалификации так, чтобы ни на какой курс не было назначено более одного преподавателя. С другой стороны, желательно использовать максимально возможное количество преподавателей из общего состава. Описанную ситуацию можно представить в виде графа, показанного на рис. 6.12, где все вершины разбиты на два множества
V
1
итак, что вершины из множества
V
1
соответствуют преподавателям, а вершины из множества
V
2
– учебным курсам. Тот факт, что преподаватель v может вести курс
w, отражается посредством ребра (v, w). Графу которого множество вершин распадается на два непересекающихся подмножества
V
1
и
V
2
таких, что каждое ребро графа имеет один конец из
V
1
, а другой – из
V
2
, называется двудольным Таким образом, задача распределения преподавателей по учебным курсам сводится к задаче выбора определенных ребер в двудольном графе, имеющем множество вершин-преподавателей и множество вершин-учебных курсов. Задачу паросочетания можно сформулировать следующим образом. Есть граф
G = (V, Е. Подмножество его ребер, такое, что никакие два ребра из этого подмножества не инциденты какой-либо одной вершине из
V, называется паросочетанием
. Задача определения максимального подмножества таких ребер называется задачей нахождения максимального паросочетания
. Ребра, выделенные толстыми линиями на рис. 6.12, составляют одно возможное максимальное паросочетание для этого графа. Полным паросочетанием называется паросочетание, в котором участвуют (в качестве концов ребер) все вершины графа. Очевидно, что любое полное паросочетание является также максимальным паросочетанием. Рис. 6.12. Двудольный граф
Существуют прямые способы нахождения максимальных паросоче- таний. Например, можно последовательно генерировать всевозможные паросочетания, а затем выбрать то, которое содержит максимальное количество ребер. Но такой подход имеет существенный недостаток – время его выполнения является экспоненциальной функцией от числа вершин. В настоящее время разработаны более эффективные алгоритмы нахождения максимальных паросочетаний. Эти алгоритмы используют в основном метод, известный как чередующиеся цепи. Пусть М – паросоче- тание в графе
G. Вершину v будем называть парной, если она является концом одного из ребер паросочетания М. Путь, соединяющий две непарные вершины, в котором чередуются ребра, входящие и не входящие в множество М, называется чередующейся (аугментальной) цепью относительно М. Очевидно, что чередующаяся цепь должна быть нечетной длины, начинаться и заканчиваться ребрами, не входящими в множество М. Также ясно, что, имея чередующуюся цепь Р, можно увеличить паросо- четание М, удалив из него те ребра, которые входят в цепь Р, и вместо удаленных ребер добавить ребра из цепи Р, которые первоначально не входили в паросочетание М. Это новое паросочетание можно определить как M
Δ
P, где Δ обозначает симметрическую разность множеств Ми Рте. в новое множество паросочетаний войдут те ребра, которые входят или в множество Мили в множество Р,но не в оба сразу. На риса показаны граф и паросочетание М, состоящее из ребер на рисунке они выделены толстыми линиями) (1, 6), (3, 7) и (4, 8). На рис.
6.13, б представлена чередующаяся цепь относительно М,состоящая из вершин 2, 6, 1, 8, 4, 9. На рис. 6.14 изображено паросочетание (1, 8), (2, 6),
(3, 7), (4, 9), которое получено удалением из паросочетания М ребер, входящих в эту чередующуюся цепь, и добавлением новых ребер, также входящих в эту цепь. а б Рис. 6.13. Паросочетание и чередующаяся цепь а – паросочетание, б – чередующаяся цепь
Паросочетание М будет максимальным тогда и только тогда, когда не будет существовать чередующейся цепи относительно М. Это ключевое свойство максимальных паросочетаний будет основой следующего алгоритма нахождения максимального паросочетания.

138 Пусть Ми паросочетания в графе G, причем М < |N| (здесь М обозначает количество элементов множества М. Для того чтобы показать, что
M Δ N содержит чередующуюся цепь относительно М, рассмотрим граф
G' = (V', М Δ N), где V' – множество концевых вершин ребер, входящих в М Δ N. Нетрудно заметить, что каждая связная компонента графа G' формирует простой путь (возможно, цикл, в котором чередуются ребра из Ми Каждый цикл имеет равное число ребер, принадлежащих Ми, а каждый путь, не являющийся циклом, представляет собой чередующуюся цепь относительно или Мили, в зависимости оттого, ребер какого па- росочетания больше в этой цепи. Поскольку М < |N|, то множество M Δ N содержит больше ребер из паросочетания
N, чем Ми, следовательно, существует хотя бы одна чередующаяся цепь относительно М. Теперь можно описать алгоритм нахождения максимального паросочетания М для графа
G = (V, Е.
1. Сначала положим М =
.
2. Далее ищем чередующуюся цепь Р относительно Ми множество М заменяется на множество
M Δ P.
3. Шаг 2 повторяется до тех пор, пока существуют чередующиеся цепи относительно М. Если таких цепей больше нетто М – максимальное паросочетание. Теперь осталось показать способ построения чередующихся цепей относительно паросочетания М. Рассмотрим более простой случай, когда граф
G является двудольным графом с множеством вершин,
6.14. Увеличенное паросочетание разбитым на два подмножества
V
1
и V
2
. Будем строить граф чередующейся цепи, по уровням
i = 0, 1, 2, …, используя процесс, подобный поиску в ширину. Граф чередующейся цепи уровня 0 содержит все непарные вершины из множества
V
1
. На уровне с нечетным номером
i добавляются новые вершины, смежные с вершинами уровня
i – 1 и соединенные ребром, не входящим в паросочетание (это ребро тоже добавляется в строящийся граф. На уровне счетным номером
i также добавляются новые вершины, смежные с вершинами уровня
i — 1, но которые соединены ребром, входящим в паросочетание это ребро тоже добавляется в граф чередующейся цепи. Процесс построения продолжается до тех пор, пока к графу чередующейся цепи можно присоединять новые вершины. Отметим, что непарные вершины присоединяются к этому графу только на нечетном уровне. В построенном графе путь от любой вершины нечетного уровня до любой вершины уровня 0 является чередующейся цепь относительно М.

139 На рис. 6.15 изображен граф чередующейся цепи, построенный для графа из риса относительно паросочетания, показанного на рис.
6.14. На уровне 0 имеем одну непарную вершину 5. На уровне 1 добавлено ребро (5, 6), не входящее в паросочетание. На уровне 2 добавлено ребро (6,
2), входящее в паросочетание. На уровне 3 можно добавить или ребро (2,
9), или ребро (2, 10), не входящие в паросочетание. Поскольку вершины 9 и 10 пока в этом графе непарные, можно остановить процесс построения графа чередующейся цепи, добавив в него одну или другую вершину. Оба пути 9, 2, 6, 5 и 10, 2, 6, 5 являются чередующимися цепями относительно паросочетания из рис. 6.14.
6.15. Увеличенное паросочетание Пусть граф
G имеет п вершин и е ребер. Если используются списки смежности для представления ребер, тона построение графа чередующейся цепи потребуется времени порядка е. Для нахождения максимального паросочетания надо построить не более п / 2 чередующихся цепей, поскольку каждая такая цепь увеличивает текущее паросочетание не менее чем на одно ребро. Поэтому максимальное паросочетание для двудольного графа можно найти за время порядка пе. Задания
1. Разработайте программу, реализующую алгоритм построения ос- тавного дерева минимальной стоимости неориентированного графа с помощью алгоритма Прима.
2. Разработайте программу, реализующую алгоритм построения ос- тавного дерева минимальной стоимости неориентированного графа посредством алгоритма Крускала.
3. Разработайте программу, реализующую алгоритмы Прима и Крас- кала и сравните время выполнения алгоритмов на различных графах.
4. Разработайте программу, выполняющую обход неориентированного графа в ширину.
5. Сравните эффективность алгоритмов обхода в ширину ив глубину произвольного графа.
6. Реализуйте алгоритм нахождения точек сочлениния, представленный в параграфе 6.4.
7. Разработайте программу, нахождения максимального паросочита- ния для двудольного графа.

140

1   ...   6   7   8   9   10   11   12   13   14

---

7. СОВРЕМЕННЫЕ АЛГОРИТМЫ
ОБРАБОТКИ ДАННЫХ Настоящий раздел содержит краткое изложение некоторых идейна основе которых разрабатываются современные алгоритмы. Подчеркнем тот факт, что сегодня наиболее интересные результаты в разработке эффективных алгоритмов связаны с привлечением аппарата других научных дисциплин, в частности – биологии и теоретических результатов специальных разделов современной математики [6].
7.1. Алгоритмы и простые числа Вне очень далеком прошлом теория простых чисел считалась разделом чисто теоретической математики, однако современные алгоритмические идеи решения разнообразных задач опираются на результаты этой теории. Значительное повышение интереса к простым числам в области информатики связано с известной криптосистемой
RSA. При построении этой криптосистемы используется ряд алгоритмов, в том числе и алгоритм Евклида (III в. дон. э, который до сих пор остается современными востребованным в алгоритмической практике. В целях дальнейшего изложения приведем некоторые сведения и обозначения из теории простых чисел. Сравнения Говорят, что два целых числа аи сравнимы по модулю с, если они дают при делении нас равные остатки. Операция получения остатка отделения а нас записывается в виде a mod с = d, что эквивалентно представлению ас целые числа. Сравнимость двух чисел по модулю с означает, что a mod с = b mod си записывается в виде ас. Если ас, то число а делится на число с без остатка. Простые числа Число р называется простым, если оно не имеет других делителей, кроме единицы и самого себя. Очевидно, что при проверке в качестве возможных делителей есть смысл проверять только простые числа, меньшие или равные квадратному корню из проверяемого числа. Множество простых чисел счетно, доказательство принадлежит Евклиду. Пусть
p
1
, …,
p
k
,
– простые числа, и
p
k
– последнее из них, но тогда число ар) в силу основной теоремы арифметики должно разлагаться, ипритом, единственно в произведение простых. Но число а не делится нацело ни на одно из р. Приходим к противоречию.

141 Функция π(
n) Функция π(
n) в теории простых чисел обозначает количество простых чисел, не превосходящих
n, например, π(12) = 5, так как существует 5 простых чисел не превосходящих 12. Асимптотическое поведение функции) было исследовано в конце XIX века. В 1896 году Адамар и Валле-
Пуссен доказали, что
n
n
n
ln
)
(


, Полученный результат означает, что простые числа не так уж редки, получаем оценку 1 / (ln
n) для вероятности того, что случайно взятое число, не превосходящее п, является простым. Теорема Ферма Введем операцию умножения чисел по модулю паи определим степени числа а = (а × а mod n, а + 1
= (
a
k
x а) mod n. Для любого простого числа р и числа а, 0 < ар справедлива малая теорема Ферма теорема Ферма–Эйлера): а – 1
≡ 1 (mod p). Алгоритм Евклида Алгоритм Евклида асимптотически оптимально решает задачу нахождения наибольшего общего делителя двух чисел НОД(
а, b). Заметим, что задача нахождения НОД является сегодня составной частью многих эффективных алгоритмов. Обоснование правильности этого алгоритма основано на свойствах НОД. Если
d = НОД (а, b), то d есть наименьший положительный элемент множества целочисленных линейных комбинаций чисел
a и b – ах у, где x, у – целые числа можно показать, что
a mod b является целочисленной линейной комбинацией аи, поэтому
НОД(
а, b) = НОД(b, а mod b). Впервой главе уже рассматривлась одна из реализаций алгоритма Евклида. Теперь приведем его рекурсивную реализацию
Ес(а, b);
If b = 0
then Ес = а
else Ес = Ec(b, a mod b);
end. Трудоемкость алгоритма Евклида определяется значениями чисел. Лучшим случаем при фиксированной битовой длине чисел, очевидно, является ситуация, когда
b = 0. Заметим, что в ситуации, когда а < b, алгоритм первой рекурсией переворачивает пару чисел. Анализ в худшем случае не так очевиден – если аи, где
F
k + 1
– (
k + 1)-ое число

142 Фибоначчи, то процедура
Еc(а, b) выполняет менее k рекурсивных вызовов теорема Ламе, начало XIX века. Из этой теоремы можно получить сложность алгоритма Евклида – поскольку
F
k

φ
k
, где
618
,
1 2
/
)
5 1
(




(φ – величина, обратная к золотому сечению, то количество рекурсивных вызовов не превышает 1 +
log
φ
b. Если рассматривать числа аи как двоичные битовые числа, то можно показать, что процедура
Еc(а, b) имеет сложность
O(β
2
) битовых операций. Вероятностный тест Миллера-Рабина На практике, особенно в криптографических алгоритмах, возникает необходимость нахождения больших простых чисел. Один из эффективных алгоритмов решения этой задачи – вероятностный тест Миллера-
Рабина (1980). Идея теста Миллера-Рабина состоит в последовательной генерации случайных чисел и проверке их на простоту с использованием теоремы
Ферма-Эйлера. Основная задача теста связана с уменьшением вероятности ошибочного признания некоторого составного числа в качестве простого. Проблема состоит в том, что существуют составные числа п (числа Кар- майкла), для которых сравнение
a
n – 1
≡ 1 (
mod n) справедливо для всех целых чисел а, удовлетворяющих неравенству 0 < а < п. Решением проблемы является проверка на нетривиальный корень изв момент вычисления
a
n –
1
методом последовательного возведения в квадрат, те. проверка того, что
(
x x х) mod n = 1, при х ≠ 1, х ≠ п – 1. Отсутствие нетривиальных корней свидетельствует в пользу того, что число п является простым. Тест Миллера–Рабина
1. Цикл пока не будет найдено простое число
2. Генерация случайного числа п (двоичное битовое число)
3. Повторять
s раз
4. Случайный выбор числа
a
 {2, …, п – 2} если (
a
n – 1
)
mod n ≠ 1, то, очевидно, что число п составное если (
a
n – 1
)
mod n = 1, то, необходимо проверить другое а при вычислении (
a
n – 1
)
mod n проверить нетривиальный корень из 1 если (х x х) mod п = 1 при х ≠1, х ≠ п – 1, то число п – составное.
5. Конец цикла по
s
6. Выход, если все выбранные числа а показали простоту числа п.
7. Конец теста.

143 Вероятность ошибки теста экспоненциально падает с ростом успешных проверок с различными значениями а, а именно, если выполнено s успешных проверок, то она составляет 2
–s
, что приводит реально к выбору
s в пределах нескольких десятков. Сложность теста оценивается как
O(s x β
3
) битовых операций. Алгоритм Рабина–Карпа Одна из нетривиальных идей использования простых чисел для разработки и доказательства эффективности алгоритмов – идея предложенного в 1981 и опубликованного в 1987 году Рабином и Карпом алгоритма поиска подстроки в строке. Центральная идея алгоритма связана с переходом к сравнению чисел вместо посимвольного сравнения образца и части строки поиска. Пусть дана символьная строка
T длиной т (битовая строка) и образец Р длиной п Нам необходимо найти все вхождения образца в строку. Обозначим через Т подстроку длиной
n, начиная сбита Определим
)
(
2
)
(
1
i
P
P
H
n
i
i
n




, Мы рассматриваем тем самым подстроки как двоичные числа, очевидно, что образец Р входит в строку Т, начиная с позиции r, если Н(Р) = Н(Т
r
). Таким образом, мы сравниваем числа, а не символы, и если вычисление
Н(Т
r
) при сдвиге может быть выполнено зато сложность алгоритма составит п + т, те. теоретическую границу сложности задачи поиска. Принципиальная проблема этой идеи – экспоненциальный рост чисел
Н(Р) и
Н(Т
r
), с ростом длины образца. При обычном байтовом кодировании символов образец всего из 12 букв занимает 96 бит, и, следовательно,
Н(Р)
≤ 2 96
– 1. Необходимо было сохранить внешнюю привлекательность идеи, но уложиться в рамки реального диапазона представления целых чисел машинного слова) в компьютере для образцов любой длины. Решение проблемы, предложенное Рабином и Карпом, состоит вис- пользовании остатков отделения
Н(Р) и Н(Т
r
) на некоторое простое число р Эти остатки называются дактилограммами. Но действительная мощность предложенного метода состоит в доказательстве того, что вероятность ошибки (ложного срабатывания) может быть сделана малой, если простое число выбирается случайно из некоторого множества. Обозначим через
Н
р
(
Р) = H (Р) mod р Н
р
(
Т
r
)
= Н Т)
mod p. Однако если вычислять вначале
Н(Р), а затем брать остаток, то мы снова окажемся за пределами машинного слова. Для эффективного вычисления
Н
р
(
Р) и H
р
(
Т
r
) может быть использована схема Горнера, в результате

144 чего вовремя вычислений ни один из промежуточных результатов небу- дет больше р Схема вычислений имеет вид
Н
р
(
Р)=((((Р (1)×2 mod p + Р (2)) × 2 mod p + Р) × 2 mod p)+ … + Р(п)) mod p. Следующая задача на пути создания эффективного алгоритма – быстрое вычисление сдвига значения
Н(Т
r
). Заметим, что Т) = 2 x
H(T
r – 1
) – 2
n x T(r – 1) + T(r + n + 1), и, выполняя вычисления по
mod p, можно вычислить H
р
(
Т
r
) по
Н
р
(
Р) и
H
р
(
Т
r – 1
) с трудоемкостью
O(1). Очевидно, что Н
р
(
Р) и H
р
(
Т
1
) вычисляются однократно со сложностью п. При каждом сдвиге по строке мы вычисляем
H
р
(
Т
r
) и сравниваем числа, что дает по порядку т – пимы получаем общую линейную сложность. Обоснование того, что вероятность ложного совпадения (возможно, что числа
Н(Р) и Н(Т
r
) различны, в то время как
Н
р
(
Р) и H
р
(
Т
r
) совпадают) мала, происходит на основе теорем и лемм теории простых чисел. Центральная теорема подхода Рабина-Карпа формулируется следующим образом Пусть Р и Т некоторые строки, причем п x т ≥ 29, где п = Рт. Пусть
I – некоторое положительное число. Если р – случайно выбранное простое число, не превосходящее
I, то вероятность ложного совпадения Р и Т не превосходит п x т) / π (I). Если выбрать I = п x т, то вероятность ложного совпадения не превосходит 2,53 /
m. Алгоритм Рабина–Карпа
1. Выбрать положительное целое
I (например, I = п x т)
.
2. Случайно выбрать простое число р, не превосходящее I (например, используя тест Миллера-Рабина) .
3. По схеме Горнера вычислить
Н
р
(
Р) и H
р
(
Т
1
).
4. Для каждой позиции
r в Т (1< r < т – n + 1) вычислить H
р
(
Т
r
) и сравнить с
Н
р
(
Р). Если они равны, то либо объявить о вероятном совпадении, либо выполнить явную проверку, начиная с позиции
r. Существует несколько модификаций метода Рабина-Карпа, связанных с обнаружением ошибок. Один из них основан на методе Бойера-Мура и со сложностью О) либо подтверждает отсутствие ложных совпадений, либо декларирует, что, по меньшей мере, одно из совпадений ложное. В случае ложных совпадений нужно выполнять алгоритм заново с новым значением р, вплоть до отсутствия ложных совпадений. Тем самым алгоритм Рабина-Карпа преобразуется из метода с малой вероятностью ошибки и со сложностью О + n) в худшем случаев метод, который не делает ошибок, но обладает ожидаемой сложностью От + п – это преобразование алгоритма Монте-Карло в алгоритм Лас-Вегаса. Отметим, что метод Рабина–Карпа успешно применяется (наряду с целым рядом других алгоритмов поиска подстрок) в таком разделе современной науки как вычислительная молекулярная биология, для поиска совпадающих цепочек ДНК и расшифровки генов.
7.2. Генетические алгоритмы Практическая необходимость решения ряда полных задач в оптимизационной постановке при проектировании и исследовании сложных систем привела разработчиков алгоритмического обеспечения к использованию биологических механизмов поиска наилучших решений. В настоящее время эффективные алгоритмы разрабатываются в рамках научного направления, которое можно назвать природные вычисления, объединяющего такие разделы, как генетические алгоритмы, эволюционное программирование, нейросетевые вычисления, клеточные автоматы и ДНК- вычисления, муравьиные алгоритмы. Исследователи обращаются к природным механизмам, которые миллионы лет обеспечивают адаптацию биоценозов к окружающей среде. Одним из таких механизмов, имеющих фундаментальный характер, является механизм наследственности. Его использование для решения задач оптимизации привело к появлению генетических алгоритмов. В живой природе особи в биоценозе конкурируют друг с другом за различные ресурсы, такие как пища или вода. Кроме того, особи одного видав популяции конкурируют между собой, например за привлечение брачного партнера. Те особи, которые более приспособлены к окружающим условиям, будут иметь больше шансов на создание потомства. Слабо приспособленные либо не произведут потомства, либо их потомство будет очень немногочисленным. Это означает, что гены от высоко приспособленных особей будут распространяться в последующих поколениях. Комбинация хороших характеристик от различных родителей иногда может приводить к появлению потомка, приспособленность которого даже больше, чем приспособленность его родителей. Таким образом, вид в целом развивается, лучше и лучше приспосабливаясь к среде обитания. Введение в генетические алгоритмы Алгоритм решения задач оптимизации, основанный на идеях наследственности в биологических популяциях, был впервые предложен Джоном
Холландом (1975). Он получил название репродуктивного плана Холланда, и широко использовался как базовый алгоритм в эволюционных вычислениях. Дальнейшее развитие эти идеи, как собственно и свое название – генетические алгоритмы, получили в работах Гольдберга и Де Йонга. Цель генетического алгоритма при решении задачи оптимизации состоит в том, чтобы найти лучшее возможное, ноне гарантированно оптимальное решение. Для реализации генетического алгоритма необходимо выбрать подходящую структуру данных для представления решений. В постановке задачи поиска оптимума, экземпляр этой структуры должен содержать информацию о некоторой точке в пространстве решений. Структура данных генетического алгоритма состоит из набора хромосом. Хромосома, как правило, представляет собой битовую строку, так что термин строка часто заменяет понятие хромосома. Вообще говоря, хромосомы генетических алгоритмов не ограничены только бинарным представлением. Известны другие реализации, построенные на векторах вещественных чисел. Несмотря на то, что для многих реальных задач, видимо, больше подходят строки переменной длины, в настоящее время структуры фиксированной длины наиболее распространены и изучены. Для иллюстрации идеи мы ограничимся только структурами, которые являются битовыми строками. Каждая хромосома (строка) представляет собой последовательное объединение ряда подкомпонентов, которые называются генами. Гены расположены в различных позициях или локусах хромосомы, и принимают значения, называемые аллелями – это биологическая терминология. В представлении хромосомы бинарной строкой, ген является битом этой строки, локус – есть позиция бита в строке, а аллель – это значение гена, 0 или 1. Биологический термин генотип относится к полной генетической модели особи и соответствует структуре в генетическом алгоритме. Термин фенотип относится к внешним наблюдаемым признаками соответствует вектору в пространстве параметров задачи. В генетике под мутацией понимается преобразование хромосомы, случайно изменяющее один или несколько генов. Наиболее распространенный вид мутаций – случайное изменение только одного из генов хромосомы. Термин кроссинговер обозначает порождение из двух хромосом двух новых путем обмена генами. В литературе по генетическим алгоритмам также употребляется термин кроссовер, скрещивание или рекомбинация. В простейшем случае кроссинговер в генетическом алгоритме реализуется также, как ив биологии. При скрещивании хромосомы разрезаются в случайной точке и обмениваются частями между собой. Например, если хромосомы
(11, 12, 13, 14) и (0, 0, 0, 0) разрезать между вторыми третьим генами и обменять их части, то получатся следующие потомки (11, 12, 0, 0) и (0, 0, 13, 14). Основные структуры и фазы генетического алгоритма Приведем простой иллюстративный пример – задачу максимизации некоторой функции двух переменных
f(x
1
,
x
2
), при ограничениях 0 <
x
1
< 1 и 0 <
x
2
< 1. Обычно методика кодирования реальных переменных
x
1
и состоит в преобразовании их в двоичные целочисленные строки определенной длины, достаточной для того, чтобы обеспечить желаемую точность Предположим, что 10-ти разрядное кодирование достаточно для
x
1
и Установить соответствие между генотипом и фенотипом можно, разделив соответствующее двоичное целое число на 2 10
– 1. Например, 0000000000 соответствует 0 / 1023 или 0, тогда как 1111111111 соответствует
1023 / 1023 или 1. Оптимизируемая структура данных есть 20-ти битовая строка, представляющая собой конкатенацию (объединение) кодировок
x
1
и
x
2
. Пусть переменная
x
1
размещается в крайних левых 10-ти битах строки, тогда как
x
2
размещается в правой части генотипа особи. Таким образом, генотип представляет собой точку в 20-ти мерном целочисленном пространстве вершину единичного гиперкуба), которое исследуется генетическим алгоритмом. Для этой задачи фенотип будет представлять собой точку в двумерном пространстве параметров (
x
1
,
x
2
). Чтобы решить задачу оптимизации нужно задать некоторую меру качества для каждой структуры в пространстве поиска. Для этой цели используется функция приспособленности. При максимизации целевая функция часто сама выступает в качестве функции приспособленности, для задач минимизации целевая функция инвертируется и смещается в область положительных значений. Рассмотрим фазы работы простого генетического алгоритма. Вначале случайным образом генерируется начальная популяция (набор хромосом. Работа алгоритма представляет собой итерационный процесс, который продолжается до тех пор, пока не будет смоделировано заданное число поколений или выполнен некоторый критерий останова. В каждом поколении реализуется пропорциональный отбор приспособленности, одно- точечная рекомбинация и вероятностная мутация. Пропорциональный отбор реализуется путем назначения каждой особи (хромосоме)
i вероятности Р, равной отношению ее приспособленности к суммарной приспособленности популяции (по целевой функции Затем происходит отбор (с замещением) всех п особей для дальнейшей генетической обработки, согласно убыванию величины Р. Простейший пропорциональный отбор реализуется с помощью рулетки
(Гольдберг, 1989 г. Колесо рулетки содержит по одному сектору для каждого члена популяции, а размер го сектора пропорционален соответствующей величине Р. При таком отборе члены популяции, обладающие более высокой приспособленностью, будут выбираться чаще по вероятности. После отбора выбранные п особей подвергаются рекомбинации с заданной вероятностью Р, при этом п хромосом случайным образом разбиваются на п / пар. Для каждой пары с вероятность Р
с
может быть выполнена рекомбинация. Если рекомбинация происходит, то полученные потомки заменяют собой родителей. Одноточечная рекомбинация работает следующим образом. Случайным образом выбирается одна из точек разрыва, те. участок между соседними битами в строке. Обе родительские структуры разрываются на два сегмента поэтому участку. Затем соответствующие сегменты различных родителей склеиваются и получаются два генотипа потомков. После стадии рекомбинации выполняется фаза мутации. В каждой строке, которая подвергается мутации, каждый бит инвертируется с вероятностью Рт. Популяция, полученная после мутации, записывается поверх старой, и на этом завершается цикл одного поколения в генетическом алгоритме. Полученное новое поколение обладает (по вероятности) более высокой приспособленностью, наследованной от хороших представителей предыдущего поколения. Таким образом, из поколения в поколение, хорошие характеристики распространяются по всей популяции. Скрещивание наиболее приспособленных особей приводит к тому, что исследуются наиболее перспективные участки пространства поиска. В результате популяция будет сходиться к локально оптимальному решению задачи, а иногда, может быть, благодаря мутации, и к глобальному оптимуму. Теперь можно сформулировать основные шаги генетического алгоритма. Генетический алгоритм
1. Создать начальную популяцию
2. Цикл по поколениям пока не выполнено условие останова
// цикл жизни одного поколения
3. Оценить приспособленность каждой особи
4. Выполнить отбор по приспособленности
5. Случайным образом разбить популяцию на две группы пар
6. Выполнить фазу вероятностной рекомбинации для пар популяции и заменить родителей
7. Выполнить фазу вероятностной мутации
8. Оценить приспособленность новой популяции и вычислить условие останова
9. Объявить потомков новым поколением
10. Конец цикла по поколениям Модификации генетического алгоритма Очевидно, что тонкая настройка базового генетического алгоритма может быть выполнена путем изменения значений вероятностей рекомбинации и мутации, существует много исследований и предложений в данной области. В настоящее время предлагаются разнообразные модификации генетических алгоритмов в части методов отбора по приспособленности, рекомбинации и мутации. Приведем несколько примеров. Метод турнирного отбора (Бриндел, 1981 г Гольдберг и Деб, 1991 г) реализуется в виде п турниров для выборки п особей. Каждый турнир состоит в выборе
k элементов из популяции и отбора лучшей особи среди них. Элитные методы отбора (Де Ионг, 1975 г) гарантируют, что при отборе обязательно будут выживать лучший или лучшие члены популяции. Наиболее распространена процедура обязательного сохранения только одной лучшей особи, если она не прошла через процесс отбора, рекомбинации и мутации. Этот метод может быть внедрен практически в любой стандартный метод отбора. Двухточечная рекомбинация (Гольдберг 1989 г) и равномерная рекомбинация (Сисверда, 1989 г) являются вполне достойными альтернативами одноточечному оператору. При двухточечной рекомбинации выбираются две точки разрыва, и родительские хромосомы обмениваются сегментом, который находится между двумя этими точками. Равномерная рекомбинация предполагает, что каждый бит первого родителя наследуется первым потомком с заданной вероятностью в противном случае этот бит передается второму потомку. Механизмы мутаций могут быть также заимствованы из молекулярной биологии, например, обмен концевых участков хромосомы (механизм транслокации, обмен смежных сегментов (транспозиция. По мнению МВ. Ульянова, интерес представляет механизм инверсии, те. перестановки генов в хромосоме, управляющим параметром при этом может выступать инверсионное расстояние – минимальное количество единичных инверсий генов, преобразующих исходную хромосому в мутированную. Применение генетических алгоритмов Основная проблема, связанная с применением генетических алгоритмов это их эвристический характер. Говоря более строго, какова вероятность достижения популяцией глобального оптимума в заданной области приданных настройках алгоритма В настоящее время не существует строгого ответа и теоретически обоснованных оценок. Имеются предположения, что генетический алгоритм может стать эффективной процедурой поиска оптимального решения, если
 пространство поиска достаточно велико, и предполагается, что целевая функция не является гладкой и унимодальной в области поиска, те. не содержит один гладкий экстремум
 задача не требует нахождения глобального оптимума, необходимо достаточно быстро найти приемлемое хорошее решение, что довольно часто встречается в реальных задачах.

150 Если целевая функция обладает свойствами гладкости и унимодаль- ности, то любой градиентный метод, такой как метод наискорейшего спуска, будет более эффективен. Генетический алгоритм является в определенном смысле универсальным методом, те. он явно не учитывает специфику задачи или должен быть на нее каким-то образом специально настроен. Поэтому если имеется некоторую дополнительную информацию о целевой функции и пространстве поиска (как, например, для хорошо известной задачи коммивояжера, то методы поиска, использующие эвристики, определяемые задачей, часто превосходят любой универсальный метод. С другой стороны, при достаточно сложном рельефе функции приспособленности градиентные методы с единственным решением могут останавливаться в локальном решении. Наличие у генетических алгоритмов целой популяции решений, совместно с вероятностным механизмом мутации, позволяют предполагать меньшую вероятность нахождения локального оптимума и большую эффективность работы на многоэкстремальном ландшафте. Сегодня генетические алгоритмы успешно применяются для решения классических полных задач, задач оптимизации в пространствах с большим количеством измерений, ряда экономических задач оптимального характера, например, задач распределения инвестиций.

1   ...   6   7   8   9   10   11   12   13   14

---

---