Математика \ Теория игр и исследование операций

Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 25

Пусть G = (V , E )– граф, V и E - множества его вершин и ребер. G ¢ - подграф графа G, если G ¢ = (V ¢ , E ¢), и E ¢ Ì (V ¢ ´ V ¢) Ç E. Подграф G ¢ называют остовным деревом, если V ¢ = V и G ¢ является деревом. Всего в графе £ n n-2 остовных деревьев. Пусть заданы длины ребер. Минимальное остовное дерево (МОД)– остовное дерево с минимальной суммой длин всех ребер. Деревом кратчайших путей (ДКП) из фиксированной вершины назовем объединение кратчайших по длине путей из нее во все остальные.

Пример: пусть центр обслуживания размещен в крайней левой точке.

Исходная сеть дорог.                    Dмод=3,  Rmax=3.                        Dдкп=4,  Rmax=2

Для укладки асфальта лучше строить МОД, а для аварийной службы – ДКП.

№19. Волновой алгоритм нахождения МОД (Прим).

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

W – множество включенных, = V \ W - множество невключенных вершин.

Множество W можно понимать как характеристический вектор = функцию w:

W = w –1 (1) = {i | wi = w(i) = 1 }        ` = w –1 (0) = {i | wi = 0 }

Разрез R (W) = {(v1, v2) Î E | v1 Î W , v2 Ï W }

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

D(i)=d(i,O(i)) – расстояние от i-ой вершины до ее текущего отца.

На выходе алгоритма получаем множество включенных ребер {(i,O(i))}, т.е. ориентированный по включению граф. Эту ориентацию можно не учитывать. В худшем случае алгоритм имеет трудоемкость T=O(n2).

Рассмотрим работу алгоритма на примере:

O

1

1

1 4

1

4

3 5

2 8 6

6 7

i

1

2

3

4

5

6

7

8

9

D

1

3 1

2

2

4 1

6 2 1

4 2

W

1

1

1

1

1

1

1

1

0

N

`W Ç O-1(>0) ={i}

{Di}

Dk=

min Di

k=

argmin

`W Ç S(k)

j

Oj

Dj

R= dk,j

коррекция

Oj=k, Dj=R

2

{4,3,2}

{2,3,1}

1

2

{3, 7}

3

≠0

3

5

нет

7

=0

6

O7=2, D7=6

3

{4,3,7}

{2,3,6}

2

4

{3, 5}

3

≠0

3

1

O3=k, D3=1

5

=0

2

O5=k, D5=2

4

{5,3,7}

{2,1,6}

1

3

{5, 6, 7}

5

≠0

2

3

нет

6

=0

4

O6=k, D6=4

7

≠0

6

2

O7=k, D7=2

5

{5,6,7}

{2,4,2}

2

5

{ 6}

6

≠0

4

1

O6=k, D6=1

6

{6,7}

{1,2}

1

6

{7, 8}

7

≠0

2

1

O7=k, D7=1

8

=0

4

O8=k, D8=4

7

{7,8}

{1,4}

1

7

{ 8}

8

≠0

4

2

O8=k, D8=2

8

{8}

{2}

2

8

{}

нет
Скачать файл