Кратко напомним определения, известные из курса дискретной математики.
Определеия:
Граф – пара ,
где V={ V1, V2,…, Vn } – множество вершин
графа G, E – множество дуг (рёбер) графа: E={ (V1i,V2i)}.
Рёбра можно задавать разными способами, например матрицей инцидентности или списком рёбер.
Неориентированный граф – граф, удовлетворяющий условию,
что если
, то и
,
т.е. порядок расположения концов дуг графа не существенен.
Матрица инцидентности такого графа симметрична.
Взвешенный граф – граф, каждой дуге которого приписан её вес.
Цикл в графе – маршрут, заданный последовательностью вершин, каждая вершина посещается по одному разу, и начальная вершина совпадает с конечной.
Граф без циклов – куст.
Связный граф – граф, из любой вершины которого можно дойти до любой другой.
Связный куст – дерево.
Компонента связности – совокупность вершин, для каждой из которых существует путь в любую другую вершину этой совокупности.
Задача: Дан граф G=(V,E) – связный, неориентированный, взвешенный. Нам нужно выделить в нем минимальный (по суммарному весу ребер) связный граф с теми же вершинами – остов ( остовное дерево), т.е. исключить из графа часть ребер таким образом, чтобы сумма весов оставшихся была минимальна, и получившийся граф по- прежнему был связным.
Идея решения: Для решения этой задачи обычно применяется алгоритм Краскала (классический пример т.н. “жадного алгоритма”).
Алгоритм Краскала:
1. Сначала упорядочиваем все ребра по возрастанию весов.
2. Заводим таблицу: в левой колонке список ребер, в правой компоненты связности.
3. В первой строчке список ребер пустой и все компоненты связности одновершинные. Берем минимальное по стоимости (по весу) ребро и включаем его в список ребер. Соответствующие две вершины объединяем в одну компоненту связности.
4. Берем следующее по стоимости ( весу) ребро, добавляем к содержимому предыдущей строчки левого столбца; объединяем компоненты связности. Если концы ребра уже принадлежат одной и той же компоненте связности, то данное ребро в состав минимального остова не включается.
5. Повторяем эти операции до тех пор, пока все вершины не окажутся в одной единственной компоненте связности (для этого потребуется включить в
состав остова ровно n–1 ребро).
Пример: Пусть имеется граф, изображённый на рисунке 3.1.
Рисунок 3.1 Исходный граф
Решение: Составим таблицу, в которой будем отражать порядок выбора ребер для минимального остова.
Подграф (ребра) |
Связи (компоненты связности) |
|
1,2,3,4,5,6,7 |
(1,7) – минимально по цене. |
(1,7),2,3,4,5,6 |
(1,7)+(3,4) |
(1,7),2,(3,4),5,6 |
(1,7)(3,4)+(2,7)< |
(1,2,7),(3,4),5,6 |
(1,7)(3,4)(2,7)+(2,3) |
(1,2,3,4,7),5,6 |
(1,7)(3,4)(2,7)(2,3) +(3,7) ◊ |
(1,2,3,4,7),5,6> |
(1,7)(3,4)(2,7)(2,3) +(4,7) ◊◊ |
(1,2,3,4,7),5,6 |
(1,7)(3,4)(2,7)(2,3)+(4,5) |
(1,2,3,4,5,7),6 |
(1,7)(3,4)(2,7)(2,3)(4,5) +(1,2) ◊◊◊ |
(1,2,3,4,5,7),6 |
(1,7)(3,4)(2,7)(2,3)(4,5)+(1,6)> |
(1,2,3,4,5,6,7) |
Пояснения:
◊ – вершины 3 и 7 уже находятся в одной компоненте связности на момент включения в остов ребра (3,7);
◊◊ – следующее по весу ребро – (4, 7), однако вершины 4 и 7 уже находятся в одной компоненте связности на момент включения в остов ребра (4,7);
◊◊◊ – аналогично.
Теорема 3.1: Алгоритм Краскала всегда выдает минимальный по стоимости остов.
Доказательство: Заметим, что в результате работы алгоритма Краскала мы всегда получаем дерево (так как мы не включаем ребра, вершины которых лежат в одной компоненте связности, следовательно, возникновение циклов невозможно).
Предположим, что получившееся в результате работы алгоритма Краскала дерево не минимально по своей стоимости и существует другое, предположительно “оптимальное” дерево. Например, такое, как на рисунке 3.2. Цифрами в кружочках обозначены ребра в порядке их добавления в дерево.
Рисунок 3.2
Рассмотрим подробно тот этап работы алгоритма Краскала, на котором мы впервые добавили в остов “неправильное” ребро, т.е. то, которого нет в “оптимальном” дереве. Первые два по порядку добавления ребра (3,6) и (6,5) присутствуют в “оптимальном” дереве. Расхождение начинается после добавления ребра (7,8).
Добавим ребро (7,8) к “оптимальному” дереву (см. рис 3.3):
Рисунок 3.3
При этом в “оптимальном” дереве возникает цикл, и мы можем убрать из него любое ребро, например, (1,2), участвующее в цикле, и при этом граф останется связанным. Заметим, что при этом общий вес полученного дерева будет меньше веса “оптимального” дерева, т.к. ребро (7,8) самое меньшее по весу в этом цикле (т.к. в алгоритме Краскала мы по очереди добавляем все ребра, начиная с самого минимального по весу, меньше ребра (7,8) по весу только ребра (3,6) и (6,5), а они в этот цикл не входят). В этом примере мы можем построить меньший, чем предполагаемый “оптимальный”, по суммарному весу остов:
Рисунок 3.4 Минимальный остов
Он отличается от “оптимального” заменой ребра (1,2) на меньшее по весу ребро (7,8).
Данные рассуждения можно обобщить для случая произвольного графа.
Теорема доказана.
Оценим трудоемкость работы алгоритма Краскала:
Пусть в
графе было n вершин и k ребер .
При быстрой сортировке на первый этап работы алгоритма затрачиваем k log
k действий. Далее нам потребуется ровно (n–1) результативных этапов
(результативным будем считать этап работы алгоритма, в результате которого осуществляется
добавление ребра к минимальному остову и слияние компонент связности), и не
больше, чем k–(n–1) нерезультативных этапов. Нерезультативный этап состоит
из одного сравнения – проверки принадлежности вершин добавляемого ребра на нахождение
в одной компоненте связности. В случае же результативного этапа мы должны переприсвоить
номера компонент связности всем n вершинам – итого n действий.
Таким образом, трудоемкость алгоритма Краскала:
Следовательно, алгоритм Краскала – полиномиальный.
Дан связный
неориентированный взвешенный граф G. Если существует ребро с вершинами
vi и vj , то стоимость перехода из vi
в vj составит .
Если же ребра vi– vj нет, то полагаем
.
На входе в данном графе выделяется вершина v0. Надо найти кратчайшее расстояние от v0 до всех остальных вершин.
Для решения задачи поиска кратчайшего расстояния используется (кроме прямого перебора) два алгоритма: Форда – Беллмана и Дейкстры.
Рассмотрим простейший алгоритм поиска кратчайшего расстояния – алгоритм Форда-Беллмана. Этот алгоритм является классическим примером алгоритма на поиск транзитивного замыкания.
Общая идея работы всех алгоритмов на поиск транзитивного замыкания:
Пересчитываем что-либо (в нашем случае, стоимости вершин) до тех пор, пока это что-то не стабилизируется. Как только произойдёт стабилизация, необходимо остановиться. Ответ получен.
3.3.1 Алгоритм Форда – Беллмана
Формируем массив –
минимально возможная стоимость переезда (перехода, перевозки) из вершины v0
в vi на каждом этапе работы нашего алгоритма.
Первоначально он задается
как .
Затем пересчитываем стоимости всех вершин по формуле
(3.1)
до тех пор, пока система не стабилизуется (так называемое транзитивное замыкание). В результате мы получим стоимости переезда из каждой вершины графа до заданной v0 и эти стоимости будут минимально возможными.
Пример: Дан граф (рис. 3.5). Найти расстояние от нулевой вершины до всех остальных.
Рисунок 3.5 Исходный граф
Решение:
Рисунок 3.6 Стоимости переездов из вершины v0
Первоначальный массив стоимостей переходов выглядит так:
D(0)=(0,
). Сосчитаем стоимость вершины
i на k-том шаге. В вершину i мы могли попасть из нулевой вершины,
из первой вершины и т.д.
Тогда:
D(k+1)(i)= (D(k)(0) + (0,i),D(k)(1) +(1,i),…………. )
стоимость перехода из стоимость вершины 0 на предыдущем шаге +
вершины 0 в вершину i. стоимость переезда из нулевой вершины в i-ую.
Стоимость вершины i на каждом шаге считаем по формуле (3.1):
.
Вычислим стоимости вершин данного графа на первом шаге:
;
;
;
.
Вычислим стоимости вершин данного графа на втором шаге:
;
;
;
– наблюдается стабилизация.
Вычислим стоимости вершин данного графа на третьем шаге:
;
;
–
стабилизация;
–
стабилизация.
Вычислим стоимости вершин данного графа на четвёртом шаге:
;
–
стабилизация;
–
стабилизация;
–
стабилизация.
Вычислим стоимости вершин данного графа на пятом шаге:
–
стабилизация;
–
стабилизация;
–
стабилизация;
–
стабилизация.
Массив стоимостей вершин перестал изменяться. Таким образом, мы получили кратчайшие расстояния от всех вершин данного графа до нулевой вершины.
Оценим трудоемкость алгоритма Форда-Беллмана:
В нем участвуют три цикла: внешний типа While выполняется до тех пор, пока не произошла стабилизация. Следующий по вложенности цикл – по вершинам графа. Самый внутренний цикл (нахождение минимума) – по переменной j.
Итого, T(n) = l∙n∙n, где l – количество проходов внешнего цикла While. Так как l ≤ n (потому что самый длинный оптимальный маршрут включает в себя прохождение n–1 вершин, плюс делаем еще один проход, чтобы убедиться в стабилизации) , то 2n2 ≤ T(n) ≤ n3
3.3.2 Алгоритм Дейкстры
Описание алгоритма Дейкстры:
Ищем расстояние от нулевой вершины.
S = {o}
D[i] = C(0,i) i = 0……n
While S ≠ V do
Пример: Рассмотрим работу алгоритма на уже знакомом графе:
Рисунок 3.7 Исходный граф
Решение: Составим таблицу:
S |
w |
D(w) |
D(1) |
D(2) |
D(3) |
D(4) |
0 |
Не определены |
25 |
15 |
7 |
2 |
|
(0,4) |
4 |
2 |
25 ◊ |
15 |
5 |
─ ◊◊ |
(0,4,3) |
3 |
5 |
25 |
9 ◊◊◊ |
─ |
─ |
(0,4,3,2) |
2 |
9 |
15 |
─ |
─ |
─ |
(0,4,3,2,1) |
1 |
15 |
─ |
─ |
─ |
─ |
Пояснения:
◊
– 25 = min(25, 2+), где C(4,1)=
– стоимость перехода напрямую
от 4 вершины к первой, так как эти вершины не соединены ребром;
◊◊ – стоимость маршрута от нулевой до четвертой вершины не пересчитывается, так как четвертая вершина уже вошла во множество S. Прочерки в остальных ячейках таблицы также означают отсутствие пересчета маршрутов для соответствующих вершин;
◊◊◊ – 9 = min(11, 5+4), где 4 – вес пути из 3 вершины во вторую.
Комментарии: В алгоритме Дейкстры на каждом шаге
S – растущее множество вершин, для которых уже найдены их подлинные стоимости;
w – добавляемая к множеству S вершина;
D[j] – минимально возможная стоимость маршрута следующего вида:
Рисунок 3.8
Замечание:
Алгоритм Дейкстры работает корректно, так как на каждом шаге стоимость каждой
вершины пересчитывается
по формуле (3.1), что соответствует выбору из двух маршрутов – старого
(
) и нового (
).
Оценим трудоемкость данного алгоритма:
В процессе реализации алгоритма Дейкстры n раз выполняется цикл While. Внутри цикла While имеется цикл For, в котором нам приходится пересчитывать n–1, n–2, n–3,…,1 значений. Каждое из них – минимум из двух чисел, одно из которых – сумма двух слагаемых.
Следовательно, получаем квадратичную трудоёмкость:
.
То есть алгоритм Дейкстры в целом работает на порядок быстрее, чем алгоритм Форда-Беллмана.
Замечание:
Алгоритм Дейкстры может работать только с графами, для которых стоимости
переезда . Алгоритм
Форда-Беллмана справляется с графами и с отрицательными стоимостями переезда,
но работает дольше.
Определения:
Диаметром графа (взвешенного) называется максимально возможное расстояние между вершинами.
–
максимальная стоимость маршрута
.
Радиусом графа называется минимально возможный радиус круга (центр круга выбирается среди всех вершин), внутри которого помещается весь граф.
,
где –
минимально возможный радиус круга (в который входит весь граф) с центром в вершине
.
Центр
графа – та вершина , для
которой достигается минимально возможный радиус круга:
:
.
При применении алгоритма
Дейкстры и диаметр, и радиус графа можно найти за операций,
где n2 трудоёмкость однократного применения алгоритма Дейкстры.
Алгоритм
Дейкстры мы запускаем n раз: сначала от v0, потом от
v1 и т.д. перебирая все возможные вершины .
Получаем квадратную матрицу
, по которой мы за
n2 операций находим диаметр и радиус графа.
Определение: Два взвешенных графа G1 и G2 называются изоморфными, если существует взаимнооднозначное отображение вершин, сохраняющих расстояние, т.е. после перенумерации вершин графа G1 получаем ровно граф G2.
Оценим трудоемкость этой задачи методом прямого перебора:
На входе имеем два графа из n вершин.
Существует всего n! различных перестановок
( перенумераций ) для n-элементного массива и при каждой перенумерации
необходимо проверить n2 – попарных расстояний. Таким образом,
трудоемкость этих операций составит .
Нетрудно заметить, что этот алгоритм не полиномиальный и его трудоемкость велика. На данный момент не известны алгоритмы решения данной задачи для графов произвольного вида за полиномиальное время, но и не доказано, что такого алгоритма не существует.
В тоже время для графов некоторых специальных видов (для деревьев) данные алгоритмы существуют.
Задача: Имеется взвешенный неориентированный связный граф. Необходимо найти гамильтонов цикл наименьшей длины, т.е. нужно обойти все вершины графа, побывав в каждой из них по одному разу, затратив как можно меньше денег.
Оценим трудоемкость методом прямого перебора.
Имеем n! всевозможных маршрутов. Стоимость каждого маршрута – сумма n ребер. Следовательно,
n! можно заменить (n–1)!, т.к. маршрут проходит через все вершины, и поэтому в качестве стартовой мы можем взять вершину v1, располагая оставшиеся вершины (n–1) произвольным образом.
– неполиномиальная.
Для более быстрого решения нашей задачи существует метод ветвей и границ. На самом деле это целая группа методов, они используются для решения множества задач. Их объединяет общая идея, но в каждом случае реализация метода ветвей и границ своя. Впервые этот метод был придуман для решения задачи коммивояжера.
Идея метода ветвей
и границ: Пусть нам необходимо найти минимум некоторой функции .
Предположим, что у нас есть:
а) Алгоритм дробления множества D на всё уменьшающиеся части (вплоть до одноэлементных множеств).
б) Для каждой
части , полученной в результате
дробления, имеется некоторая оценка
.
Эта величина оценивает значение функции f на интервале
снизу, причем на одноэлементных множествах эта оценка совпадает со значениями
функции f.
Тогда для нахождения минимума поступаем следующим образом:
Возьмем точку x из множества D (желательно, чтобы f(x) была как можно меньше). Объявим f(x) рекордом r . Делим множество D на части:
D
D(1)1 D(1)2 D(1)3 D(1)4
H(D(1)1)<r H(D(1)2)>r H(D(1)3)=r H(D(1)4)<r
где f – функция-оценка минимума.
Для множества D(1)2 справедливо:
H(D(1)2)
> r, тогда для всех y
D(1)2 выполняется f(y) ≥ H(D(1)2)
> r,
следовательно, на этом множестве мы минимума не достигнем, поэтому данное множество отбрасываем. Таким образом, ветвь мы отрубаем тогда и только тогда, когда функция-оценка минимума на этом множестве больше либо равна рекорда. Далее работаем с множествами D(1)1 и D(1)4 , и, не смотря на то, что множество D(1)1 кажется более перспективным, может случиться так, что реальное значение минимума будет достигнуто на D(1)4 (так как мы не требовали, чтобы выполнялось H(D(i)k ) = min f(x) , а H(D(i)k является лишь некоторой оценкой этого минимума снизу).
H(D(i)k)
≤ min f(x) , x D(i)k
Множество D(1)3 мы можем в процессе работы не рассматривать, если нам достаточно найти хотя бы одну точку, в которой достигается минимум, если же нам необходимо найти все точки, то множество D(1)3 считаем перспективным.
Замечание: Подобное дробление множества D продолжаем до тех пор, пока не доберемся до одноэлементных множеств (нижнего этажа дерева).
Рисунок 3.9 Дробление множества, где
неперспективное множество
При этом возможны два варианта дробления:
Схема одновременного ветвления:
На каждом шаге мы работаем со всеми перспективными множествами:
нижний этаж – одноэлементные множества
Рисунок 3.10 Одновременное дробление
Схема одностороннего ветвления:
Отличие этой схемы от предыдущей заключается в том, что на каждом шаге мы работаем только с одним перспективным множеством, а не со всеми сразу, как в схеме одновременного ветвления (см. рис.3.11).
Здесь:
перспективное множество
неперспективное множество
отложенное перспективное множество
ветвь, ставшая неперспективной после обновления рекорда
Рисунок 3.11 Одностороннее дробление
По ходу дробления на каждом шаге из всех множеств выбирается самое перспективное – то, на котором меньше всего оценка f. С ним и будем работать дальше. Рассмотрение остальных перспективных множеств пока отложим. Эта схема предпочтительнее, т.к. при ее применении мы быстрее доберемся до нижнего этажа, где сможем обновить рекорд, а после его обновления многие множества, ранее перспективные, при новом рекорде могут перейти в разряд неперспективных, и их мы рассматривать вообще не будем. Таким образом, трудоемкость схемы одностороннего ветвления существенно меньше схемы одновременного ветвления.
Алгоритм одностороннего ветвления:
На каждом шаге оставляем в работе только одно, самое перспективное множество. Таким образом доходим до нижнего этажа дерева, при этом все находящиеся на нем множества станут одноэлементными. Обновляем рекорд. Выкидываем уже неперспективные отложенные ветви. Среди оставшихся перспективных ветвей выбираем самую перспективную (либо по оценке f, либо по уровню, на котором она расположена в дереве – чем ближе к нижнему этажу, тем перспективнее отложенная ветвь).
Подобную процедуру подъема и спуска продолжаем до тех пор, пока не останется ни одной перспективной ветви.
Применение метода ветвей и границ для решения задачи коммивояжера.
В нашем случае исходное множество D – множество всевозможных маршрутов, проходящих по всем вершинам графа (так называемых гамильтоновых циклов), для определенности стартующих из точки 0. Напомним, что гамильтонов цикл должен содержать все вершины графа, причем, переходя по его ребрам, можно обойти все вершины, побывав в каждой только по одному разу.
В предложенной схеме дробления будут возникать подмножества D следующего вида:
Множество
состоит из всевозможных маршрутов, у которых
– первоначальный участок, а следующий переход из вершины
мы можем совершить в любую вершину, кроме указанных в фигурных скобках вершин
. Также мы не можем идти в вершины
, так как тогда маршрут будет уже не гамильтонов.
Составим
оценку f для множества следующего вида:
где
– стоимость выхода (выезда) из вершины
(т.е. минимально возможная цена, за которую мы можем выехать в какую-либо другую
допустимую вершину),
– минимально возможная стоимость въезда в вершину
после уже уплаченных стоимостей выездов.
Пример: Пусть у нас имеется гамильтонов цикл в ориентированном графе (для орграфа матрица стоимости ребер не симметрична относительно своей главной диагонали). По главной диагонали расположены бесконечности, а не нули, потому что в гамильтоновом цикле петли запрещены.
Имеем первоначальный маршрут: D = [ (2,5,0),{1} ].
Таким образом, из вершины 0 мы можем идти в любую, кроме 1(так как она запрещенная), 2 и 5 (так как их уже прошли).
Вычисляем оценку Н. Для этого:
1. Вычеркиваем из имеющейся матрицы 2 и 5 строки, так как стоимости ребер, по которым можно попасть во 2 и 5 вершины, нам не понадобятся, в эти вершины мы уже въезжали и больше туда не собираемся.
2. Вычеркиваем 5 и 0 столбцы, так как уже въезжали в вершины 5 и 0.
3. Получилась матрица:
Стоимость переезда из 0 в 1 полагаем равной бесконечности, так как он запрещен. В каждой строке находим минимальный элемент (минимальную стоимость выезда из вершин 0,1,3 и 4), т.е. находим α:
“Уплачиваем”
найденные стоимости выездов, т.е. вычитаем из каждого элемента строки минимальный
элемент данной строки. Стоимости выездов “уплачены”, однако мы еще должны заехать
в вершины 1, 2, 3, 4. находим для них оценку .
Итак, оценка
из первоначальной матрицы
= 3+3+( 6+3+4+2 )+( 0+0+1+0 ) = 22.
То есть,
проехав по любому маршруту из множества , мы не
можем потратить менее 22 долларов.
Осталось записать схему возможных вариантов дробления маршрутов D.
Рассмотрим два варианта этой схемы на примере пятиэлементного множества:
Первый вариант:
Рисунок 3.12
Тут не возникает запретных вершин.
Второй вариант:
При этой схеме дробления на каждом этапе ветка делится на две новые ветви, но также возникают и запретные вершины.
Рисунок 3.13
и т.д.
Замечание: Обычно метод ветвей и границ позволяет существенно уменьшить объем перебора. Однако это справедливо не для каждой задачи, например для задачи коммивояжера до сих пор неизвестен алгоритм, который гарантированно бы решал ее за полиномиальное время. Впрочем, для большинства графов он дает существенный выигрыш по сравнению с прямым перебором.
Домашнее задание №1 (А, Б, В):
А) Найти остов минимального веса для связного взвешенного неориентированного графа, заданного матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет).
Б) Найти кратчайшие расстояния от второй до всех остальных вершин графа (нумерация вершин начинается с 0), для связного взвешенного графа, заданного матрицей весов дуг, соединяющих всевозможные пары вершин (0 означает, что соответствующей дуги нет)
Б1) с помощью алгоритма Форд-Беллмана;
Б2) с помощью алгоритма Дейкстры.
Матрица стоимостей:
В) Определить нижнюю оценку стоимости любого маршрута из множества D =[(4,0,3),{1,5}] для задачи коммивояжера.
Матрица стоимостей переездов: