Минимальные маршруты и покрытия. Лекция 5

1. Минимальные маршруты и покрытия

МИНИМАЛЬНЫЕ
МАРШРУТЫ И
ПОКРЫТИЯ
Лекция 5

2. Содержание

СОДЕРЖАНИЕ
Часть
1. Минимальные маршруты,
связывающие две вершины.
Часть 2. Минимальные маршруты,
связывающие выбранную вершину
со всеми остальными.
Часть 3. Минимальные
покрывающие подмножества
вершин.
2

3. Часть 1. Минимальные маршруты, связывающие две вершины.

ЧАСТЬ 1.
МИНИМАЛЬНЫЕ
МАРШРУТЫ,
СВЯЗЫВАЮЩИЕ ДВЕ
ВЕРШИНЫ.
3

4. Содержательная постановка задачи

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
На заданном взвешенном графе требуется
определить маршрут, суммарный вес ребер
которого минимален.
2
3
1
4
12
2
10
7
6
4
3
3
1
6
5
Синим цветом выделен минимальный маршрут,
объединяющий первую и шестую вершины.
4

5. Формальная постановка задачи

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Ниже считается, что выбраны s-я и t-я вершины.
r (i, j ) z (i, j ) min;
i j
z ( s, i ) 1;
i
z (i, t ) 1;
i
j {s, t} : z (i, j ) j , q );
i
q
(i, j ) U : z (i, j ) 1,0.
5

6. АЛГОРИТМ 1

Шаг 1. У одной из выбранных вершин полученного
графа выбираем ребро с минимальным весом.
Шаг 2. Вес всех ребер, инцидентных выбранной
вершине, уменьшаем на величину выбранного
ребра.
Шаг 3. Ребра с нулевым весом стягиваются в одну
вершину.
Шаг 4. Если на полученном графе образовались
параллельные ребра, то остается одно из них,
обладающее минимальным весом.
Шаг 5. Если выбранные вершины стянулись в одну
вершину, то перейти к шагу 6, в противном случае
– к шагу 1.
Шаг 6. Конец алгоритма. На множестве стянутых
ребер есть минимальный маршрут.
6

7. Пример 1

ПРИМЕР 1
2
2
3
3
4
1
1
8
6
3
3
1,2
3
1,2,
3
4
1
4
4
а)
1,2,3,4
1
4
б)
2
3
3
1
в)
2
4
г)
4
7

8. Достоинства и недостатки алгоритма 1

ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА 1
Достоинства:
1. Число итераций пропорционально числу вершин.
2. Наглядность алгоритма.
3. Алгоритм гарантирует глобально оптимальное
решение.
4. Легкость программной реализации.
Недостатки:
1. Неоднозначность полученного результата.
2. Невозможность в общем случае получить
суммарный вес ребер минимального маршрута.
8

9. САМОСТОЯТЕЛЬНО

Определить минимальный маршрут между 1-й и 5-й
вершинами:
2
2
4
3
11
1
1
10
8
9
3
4
5
9

10. Часть 2 Минимальные маршруты, связывающие выбранную вершину со всеми остальными

ЧАСТЬ 2
МИНИМАЛЬНЫЕ
МАРШРУТЫ,
СВЯЗЫВАЮЩИЕ
ВЫБРАННУЮ ВЕРШИНУ
СО ВСЕМИ ОСТАЛЬНЫМИ
10

11. Содержательная постановка задачи

СОДЕРЖАТЕЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
На заданном взвешенном графе требуется
определить минимальные маршруты,
соединяющие выделенную вершину со всеми
остальными.
2
3
1
2
7
12
14
3
4
11
7
6
4
5
6
11
Синим цветом выделен минимальный маршрут,
объединяющий первую и шестую вершины.

12. Формальная постановка задачи

ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ
Ниже полагаем, что выбрана s-я вершина.
t { X \ s} : max z (i, j ) z (i, j ) r (i, j ) min;
d
( i , j ) Ld ( s ,t )
( i , j ) Ld ( s ,t )
z ( s, i ) 1;
i
t { X \ s} : z (i, t ) 1;
Многокритериальная
i
оптимизация
t { X \ s} :
z (i, j ) 1;
d
( i , j ) Ld ( s ,t )
(i, j ) U : z (i, j ) 1,0.
12

13. Алгоритм 2

АЛГОРИТМ 2
Шаг 1. Выбранной вершине присваивается
потенциал, равный нулю, а остальным –
равный ∞.
Шаг 2. Каждой i-й вершине (│i-s│>0),
присваивается потенциал, равный p(i):
p(i ) min{ p(i ); p( j ) r ( j, i )}.
Шаг 3. Если потенциал хотя бы одной
вершины изменился, то перейти к шагу 2, в
противном случае – к шагу 4.
Шаг 4. Конец алгоритма. Потенциалы вершин
равны величинам минимальных маршрутов до
выбранной вершины.
13

14. Пример 2

ПРИМЕР 2
Граф G(X,U)
2
0
1
∞
2 14 ∞
3
8
5
1
4
∞
а)
Расстановка потенциалов
2
0
2
2
1 4
1
6
3
8
5
1
5
4
б)
2
2
0 21
1
4 4
3
8
1
5
3
4
в)
2
2
02
1 4 4
1
3
8
5
1
3
4
г)
На рис. г) синим цветом выделен минимальный маршрут,
связывающий первую и третью вершины.
14

15. Достоинства и недостатки алгоритма 2

ДОСТОИНСТВА И НЕДОСТАТКИ АЛГОРИТМА 2
Достоинства:
1. Гарантия глобального оптимума.
2. Отсутствие необходимости полного перебора всех
маршрутов.
3. Легкость программной реализации.
Недостатки:
1. Алгоритм дает лишь возможность определить
величины минимальных маршрутов, но не
входящие в них ребра.
2. Невозможно a priori определить число итераций этим
алгоритмом.
15

16. САМОСТОЯТЕЛЬНО

Определить величины минимальных маршруты между 1-й
и остальными вершинами:
2
2
4
3
11
1
1
10
8
9
3
4
5
16

17. Алгоритм 3

АЛГОРИТМ 3
Определение
минимального маршрута
между выбранными
вершинами
17

18. Пошаговое описание алгоритма 3

ПОШАГОВОЕ ОПИСАНИЕ АЛГОРИТМА 3
Шаг 1. Выбирается та из выделенных вершин, которая
обозначается j, потенциал которой не равен нулю.
Шаг 2. Ищется q-я вершина, для которой справедливо:
p(q) = p(j) – r(j,q).
Шаг 3. Ребро (j,q) принадлежит минимальному маршруту.
Шаг 4. Если p(q) = 0, то перейти к шагу 6, в противном
случае – к шагу 5.
Шаг 5. Вершину q считаем вновь j-й и переходим к шагу 2.
Шаг 6. Конец алгоритма.
18

19. Пример 3

ПРИМЕР 3
Граф G(X,U)
0
4
2
2 1
2
2
4 4
0 2
3
1
1
5
4
Потенциалы расставлены алгоритмом 2
1
2 2
2
1 4
4
3
5
4
1
0
21
4 4
1
5
2
3
4
3
3
3
а)
б)
в)
1
Определение ребер, входящих в минимальный маршрут,
соединяющий 1-ю и 3-ю вершины.
0 2
2
1 4
1
3
5
4
1
3
г)
19

20. САМОСТОЯТЕЛЬНО

Определить ребра минимального маршрута между 1-й и 3й вершинами приведенного ниже графа G(X,U):
2
2
4
3
11
1
1
10
8
9
3
4
5
20

21. Часть 3 Минимальные покрывающие подмножества вершин

ЧАСТЬ 3
МИНИМАЛЬНЫЕ
ПОКРЫВАЮЩИЕ
ПОДМНОЖЕСТВА
ВЕРШИН
21

22. Определения

ОПРЕДЕЛЕНИЯ
1. Покрывающим подмножеством вершин графа G((X,U) называется такое
подмножество вершин X’ для которого справедливо:
если две вершины xi , x j принадлежат подмножеству X’, то ребра (i,j) на
графе не существует, т. е. (i, j ) U ;
любая вершина подмножества X\X’ соединена одним ребром с одной из
вершин подмножества X’. (i, j ) U ;
2. Минимальным покрывающим подмножеством вершин графа G((X,U)
называется такое покрывающее подмножество вершин X ' X , мощность
множества вершин которого минимальна.
Граф G(X,U) Покрывающее подмножество Минимальное покрывающее
выделено синим цветом.
подмножество – красным.
1
2
3
4
5
22

23.

Пример 4: компрессия изображений методом
вариабельных фрагментов
1. Замена фрагментов изображения графом G(X,U) и выделение на графе
минимального покрывающего подмножества вершин
1
5
2
6
9
10
13
14
3
7
11
15
4
8
1
2
1
3
4
5
6
7
8
9
10
11
12
12
16
13
14
15
16
Рис. 1. Фрагментация изображения
Рис. 2. Замена
фрагментов графом
G(X,U), где вершины
отвечают фрагментам,
а ребра – связям
между ними.
Рис. 3. На графе G(X,U)
красным цветом выделено
минимальное покрывающее
1
подмножество вершин.
Коэффициент компрессии
равен |X|/|X |=1.8
1
23

24.

Поиск минимального покрытия перебором
1
2
4
3
5
6
Граф G(X,U)
№
1
2
3
4
5
6
R
1
0
0
0
0
0
1
∞
2
0
0
0
0
1
0
∞
3
0
0
0
0
1
1
∞
4
0
0
0
1
0
0
∞
5
0
0
0
1
0
1
2
6
0
0
0
1
1
0
2
7
0
0
0
1
1
1
3
Таблица перебора покрытий графа G(X,U)
24

25.

РЕШИТЬ САМОСТОЯТЕЛЬНО
1
2
4
3
5
6
Граф G(X,U)
№
1
2
3
4
5
6
R
1
0
0
0
0
0
1
?
2
0
0
0
0
1
0
?
3
0
0
0
0
1
1
?
4
0
0
0
1
0
0
?
5
0
0
0
1
0
1
?
6
0
0
0
1
1
0
?
7
0
0
0
1
1
1
?
Таблица перебора покрытий графа G(X,U)
24

26.

САМОСТОЯТЕЛЬНО
1. Дать формальное описание задачи
выделения покрывающего множества
вершин.
2. Дать формальное описание задачи
выделения минимального
покрывающего множества вершин.
26