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

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

2.  Для всех вершин находим ближайшую вершину BV и строим симметричное замыкание BV: если BV(i)=j и BV(j) ≠ i, то в BV(j) добавляем i. В замыкании будет не более (n-1) неориен.ребра.

3.  Поиском сначала вширь по массиву BV выделяем компоненты связности. NKS(j) – номер компоненты связности j-ой вершины, SKS(k) –список вершин k-ой компоненты связности,   Q – текущая очередь при поиске k –компоненты, pop(Q) – выбор первой вершины из очереди.

Списки вершин компонент связности на выходе: I:   1,4,5          II:   2,3            III:  6,9     IV:   7,8

Трудоемкость этой части = числу ребер в симметрическом замыкании < 2n.

4.  ЧИСТКА. Формируем ребра макрографа в виде списков соседних компонент связности, просматривая по списку SKS вершины очередной КС. Если в списке соседей очередной вершины i встретится вершина j из другой компоненты k с более коротким, чем было записано ранее, ребром между компонентами, то запишем в список соседних макровершин блок k/d (i, j), где d – длина кратчайшего ребра между вершинами компонент.

Список соседей до очистки

Список соседей после очистки

I

_ II _ ,

_ IV_ ,

_III_

I

_ II _ ,

_ IV_ ,

_III_

4(1,2)

3(4,7)

4(5,6)

4(1,2)

3(4,7)

4(5,6)

II

__I_ ,

_III_ ,

II

__I_ ,

_III_

4(2,1)

3(3,6)

4(2,1)

3(3,6)

III

__II_ ,

__I_,

_IV_ ,

__IV_

III

__II_ ,

__I_,

_IV_

3(6,3)

4(6,5)

6(6,8)

4(6,7)

3(6,3)

4(6,5)

4(6,7)

IV

_III_,

__I__

__I__

IV

_III_,

__I__

4(7,6)

5(7,5)

3(7,4)

4(7,6)

3(7,4)

Этап 3. Все вершины  одной компоненте è STOP.

Трудоемкость алгоритма удовлетворяет неравенству Tn<Cn+Tn/2, Þ линейна по n.

Особенность реализации алгоритма: Заводим и обнуляем вектор прямого доступа из n компонент. Когда в какую-либо ячейку вектора вносится информация, адрес ячейки заносим «в журнал». Для очистки строк таблицы обнуляем поля, адреса которых есть в журнале. При этом очистка не требует большей работы, чем запись. Иначе очистка может потребовать n2 операций.


3.4. КРАТЧАЙШИЕ ПУТИ В ГРАФАХ.

Волновой алгоритм построения ДКП (Дейкстра)

Аналогичен алгоритму Прима (Т=O(n2)), но теперь D(k) – текущее кратчайшее расстояние до вершины, в которой находится аварийная служба, и для которой проводится инициализация. При корректировке сравниваем R=D(k)+d(k,j) и D(j). Если < - то коррекция: D(j)=R. Алгоритм работает корректно, если все d(i,j)≥0.

Рассмотрим работу алгоритма Дейкстры на том же графе:

O

1

1

1

1

4

6 5

2 3

9

i

1

2

3

4

5

6

7

8

9

D

1

3

2

4

7 5

7 5

9

W

1

1

1

1

1

1

1
Скачать файл