Лекция 13 Топологическая сортировка




НазваниеЛекция 13 Топологическая сортировка
Дата конвертации27.05.2013
Размер445 b.
ТипЛекция


Топологическая сортировка, пути в графе

Лекция 13

Топологическая сортировка

Определение. Частичным порядком на множестве А называется отношение R, определенное на А и такое, что
  • R транзитивно,

  • для всех aA утверждение aRa ложно, т.е. отношение R иррефлексивно.

Из свойств (1) и (2) следует, что если aRb истинно, то bRa ложно (асимметричность).

Примеры частичного порядка:

Примеры частичного порядка:
  • решение большой задачи разбивается на ряд подзадач, над которыми установлен частичный порядок: без решения одной задачи нельзя решить несколько других;

  • последовательность чтения курсов в учебных программах: один курс основывается на другом;

  • выполнение работ: одну работу следует выполнить раньше другой.



Если R — частичный порядок на множестве А, то (А, R) — ациклический граф.

Если R — частичный порядок на множестве А, то (А, R) — ациклический граф.

Если (А, R ) — ациклический граф и R — отношение являться потомком, определенное на А, то R — частичный порядок на А.

Определение. Линейный порядок R на множестве А — это такой частичный порядок, что если a и b принадлежат А, то либо aRb, либо bRa, либо a = b.

Определение. Линейный порядок R на множестве А — это такой частичный порядок, что если a и b принадлежат А, то либо aRb, либо bRa, либо a = b.

Если А — конечное множество, то линейный порядок R удобно представлять , считая все элементы множества А расположенными в виде последовательности

a1, a2,..., an,

для которой имеет место aiRaj тогда и только тогда, когда i < j.

Если задан частичный порядок R на множестве А, часто бывает нужен линейный порядок, содержащий этот частичный порядок.

Если задан частичный порядок R на множестве А, часто бывает нужен линейный порядок, содержащий этот частичный порядок.

Эта проблема вложения частичного порядка в линейный называется топологической сортировкой.

Топологическая сортировка. Пример



Алгоритм. Топологическая сортировка

Вход. Частичный порядок R на конечном множестве А.

Выход. Линейный порядок R' на А, для которого RR'.

Метод. Так как А — конечное множество, линейный порядок R' на А можно представить в виде списка On = a1, a2, ..., аn, для которого ai R' aj, если i < j, и А = {а1, a2, ..., аn}.

Эта последовательность элементов строится с помощью следующих шагов:
  • Положить i=1, АI=А и Ri=R.

  • Если Ai пусто, остановиться и выдать Оi = a1, ..., аi, в качестве искомого линейного порядка. В противном случае выбрать в Аi такой элемент аi+1 что a' R аi+1, ложно для всех a' Ai.

  • Положить Ai+1= Ai \ {аi+1} и Ri+1= Ri \ ({ai+1}Ai+1). Затем увеличить i на единицу и повторить шаг 2.



Топологическая сортировка. Пример



Топологическая сортировка. Реализация на матрице смежности



Топологическая сортировка. Реализация на иерархических списках

1< 2;

3< 1;

4<1;

2< 5;

2< 6;

Кратчайшие пути

Пусть G = (V, E) – ориентированный граф. Поставим в оответствие

каждому ребру eE в графе G неотрицательную стоимость w (e).

w: E R+ - функция стоимости

Стоимость (вес) пути p(v0, v1, … , vk) определяется как сумма

стоимостей ребер, входящих в этот путь: w(p) = ∑i w ( vi-1, vi ).

Вес кратчайшего пути из u в v равен по определению

min { w(p): u p v }, если существует путь из u в v

δ(u,v)=

∞, иначе

Кратчайший путь из u в v это любой путь из u, для которого w(p)= δ(u,v)

Ребра отрицательного веса

Веса ребер могут ребер могут быть отрицательными.

Важно знать, имеются ли циклы отрицательного веса. Если

из вершины s можно добраться до цикла отрицательного

веса, то можно обойти этот цикл сколь угодно раз, при этом

вес все время будет уменьшаться.

Для вершин этого цикла кратчайших путей не существует.

Если циклов отрицательного веса нет, то любой цикл можно

выбросить. Путей без циклов конечное число, так что вес

Кратчайшего пути определен корректно.

Пусть G = (V, E) – заданный граф.

Пусть G = (V, E) – заданный граф.

Для каждой вершины vV мы будем помнить ее предшественника.

Релаксация – постепенное уточнение верхней оценки на вес

кратчайшего пути в заданную вершину.

Свойства оптимальности.

Лемма 1. Отрезки кратчайших путей являются кратчайшими:

Если p(v1, v2, … , vk) – кратчайший путь из v1 в vk и 1 ≤ ij k,

то pij = (vi, vi+1, … , vj) есть кратчайший путь из vi в vj

Следствие 1. Рассмотрим кратчайший путь p из s в v. Пусть (u,v) –

последнее ребро этого пути. Тогда δ(s,v) = δ(s,u) + w(u,v).

Следствие 2. Для любого ребра (u,v)  E справедливо

δ(s,v) ≤ δ(s,u) + w(u,v).

Идея алгоритма нахождения кратчайших путей из

Идея алгоритма нахождения кратчайших путей из

одной вершины во все другие:

Строится множество S, содержащее вершины

графа, кратчайшие расстояния до которых от

источника известны.

На каждом шаге добавляется тот из оставшихся

узлов, кратчайшее расстояние до которого меньше

всех других оставшихся узлов.



Техника релаксации

Для каждого ребра (u,v) храним d[v] – верхнюю оценку

кратчайшего пути из s в v.

Initialize (G,s){

for (для v  V) {

d[v] ← ∞

Π[v] ← NULL;

}

d[s] ← 0;

}

Релаксация ребра (u,v):

Релаксация ребра (u,v):

значение d[v] уменьшается до d[v+w(u,v)]

(если второе второе значение меньше первого)

Relax (u, v, w) {

If (d[v] > d[u] +w(u,v)){

d[v] = d[ u] +w(u,v);

Π[v] ← u;

}

}



В ходе работы алгоритма поддерживается множество S,

В ходе работы алгоритма поддерживается множество S,

состоящее из вершин, для которых δ(s,v) уже найдено

( т.е. d[s,v]= δ(s,v)).
  • Выбираем вершину uV \ S c наименьшим d[u];

  • Добавляем вершину u к множеству S;

  • Выполняем релаксацию для всех инцидентных ребер;

  • Пока в S не добавили все вершины, повторять шаги 1-3.



Алгоритм Дейкстры

Dijkstra(G,w,s){

Initialize(G,s);

S ← ø;

Q ← V; //очередь с приоритетами

While (Q ≠ ø){

u ← Exstract_min(Q); //выбрать ближайшую

S ← S U {u};

for (для v  Adj[u])

Relax ( u, v, w);

}

}

Пример. Каждой вершине из V сопоставили метку — минимальное известное расстояние от этой вершины до 1. На каждом шаге посещаем одну вершину и пытаемся уменьшать расстояние.



Аналогичную операцию проделываем с двумя другими соседями 1-й вершины —

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины —

3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до

Все соседи вершины 1 проверены. Текущее минимальное расстояние до

вершины 1 считается окончательным и пересмотру не подлежит.

Вычеркнем её, чтобы отметить, что эта вершина посещена.

Снова пытаемся уменьшить расстояния у смежных вершин, пытаясь

Снова пытаемся уменьшить расстояния у смежных вершин, пытаясь

пройти в них через 2-ю. Смежные вершины к 2 являются 1, 3, 4.

Вершина 1 уже посещалась, поэтому с 1-й вершиной ничего не делаем.

Вершина 3: если идти в неё через 2, то длина такого пути будет

7 + 10 = 17. Но текущее расстояние у нее 9<17, ничего не меняем.

Все смежные вершины с вершиной 2 просмотрены, замораживаем расстояние

Все смежные вершины с вершиной 2 просмотрены, замораживаем расстояние

до неё и помечаем её как посещенную.

Повторяем шаг алгоритма для оставшихся вершин 6, 4 и 5.

Повторяем шаг алгоритма для оставшихся вершин 6, 4 и 5.



Реализация с дополнительным массивом - O(n2)

Массив D[v] содержит стоимость текущего

кратчайшего пути из s в v.

Dijkstra

Dijkstra

{

S  {s};

D[s]  0;

для всех v V \ {v0} выполнить: D[v] = w (s, v);

пока S ≠ V выполнять:

{

выбрать узел u  V \ S, для которого

D[u] принимает наименьшее значение;

добавить w к S;

для всех v V \ S выполнить

D[v] = min (D[v], D[u] + w(u, v));

}

}

Пример

№ S u D[u] D[1] D[2] D[3] D[4]

0 {0} - - 2 +∞ +∞ 10
  • {0, 1} 1 2 2 5 +∞ 9

  • {0, 1, 2} 2 5 2 5 9 9

  • {0, 1, 2, 3} 3 9 2 5 9 9

4 {0, 1, 2, 3, 4} 4 9 2 5 9 9

Сложность алгоритма Дейкстры зависит от способа нахождения вершины v, а также способа хранения множества непосещенных вершин и способа обновления расстояний.

  • В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O(n2 + m). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций, которое не превосходит количества ребер в исходном графе.

  • Для разреженных графов непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из U станет log n, при том, что время модификации d[i] возрастет до log n. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O(nlogn + mlogn).



Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(log n), а уменьшение значения в среднем за O(1), то время работы алгоритма составит

  • Если для хранения непосещенных вершин использовать фибоначчиеву кучу, для которой удаление происходит в среднем за O(log n), а уменьшение значения в среднем за O(1), то время работы алгоритма составит

O(n log n + m).

Алгоритм Беллмана — Форда

За время O(|V| × |E|) алгоритм находит кратчайшие пути от

одной вершины графа до всех остальных, допускает рёбра с

отрицательным весом. Предложен независимо Ричардом

Беллманом (Bellman) и Лестером Фордом (Ford).

Алгоритм маршрутизации RIP был впервые разработан в

1969 году, как основной для сети ARPANET.

В 1969 году Агентство передовых исследовательских

проектов (ARPA) предложило разработать компьютерную

сеть.

Компьютерная сеть была названа ARPANET, все работы финансировались

за счёт Министерства обороны США. Затем сеть ARPANET начала активно

расти и развиваться, её начали использовать учёные из разных областей

науки. В 1973 году к сети были подключены первые иностранные

организации из Великобритании и Норвегии, сеть стала международной.

Стоимость пересылки электронного письма по сети ARPANET составляла

50 центов.

В 1984 году у сети ARPANET появился серьёзный соперник,

Национальный фонд науки США (NSF) основал обширную

Межуниверситетскую сеть NSFNet, которая имела гораздо бо́льшую

пропускную способность (56 кбит/с), нежели ARPANET.

В 1990 году сеть ARPANET прекратила своё существование, полностью

проиграв конкуренцию NSFNet.

Идея алгоритма.

Идея алгоритма.

Алгоритм позволяет очень просто определить, существует ли

в графе G отрицательный цикл, достижимый из вершины s.

Для проверки нужно произвести внешнюю итерацию цикла

|V| раз. Если при исполнении последней итерации длина

кратчайшего пути до какой-либо вершины строго

уменьшилась, то в графе есть отрицательный цикл,

достижимый из s.

На основе этого можно предложить следующую

оптимизацию. Можно отслеживать изменения в графе и,

как только они закончатся, дальнейшие итерации будут

бессмысленны.

Bellman-Ford(G,w,s) {

Bellman-Ford(G,w,s) {

Initialize(G,s);

for(i=1; i for( (u,v)  E )

Relax(u,v,w);

for( (u,v)  E )

if (d[v]>d[u]+w(u,v)

return 0;

return 1;

}



Нахождение кратчайших путей между всеми парами вершин

Строим матрицу стоимостей:

w(i, j), если ребро (i, j)E

M[i, j] = +∞ , если ребро (i, j)E

0, если i = j

Обозначим через d [i, j] матрицу кратчайших

путей между всеми вершинами.

Вершины занумеруем числами от 1 до n.

Алгоритм Флойда-Уоршолла

Обозначим через dij(k) стоимость кратчайшего пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}.

M[i, j] , если k = 0,

dij(k) =

min(dij(k-1) , dik(k-1) + dkj(k-1) ), если k1

D(n) содержит искомое решение

Floyd-Warshall(M, n) {

Floyd-Warshall(M, n) {

D(0)  M;

for k  1 to n do

for i 1 to n do

for j  1 to n do

dij(k)  min(dij(k-1), dik(k-1) + dkj(k-1) );

return D(n);

}

Транзитивное замыкание графа

Пусть G= (V, E) ориентированный граф. Транзитивным замыканием графа G называется граф G’= (V, E’), в котором из вершины v в вершину w идет ребро  существует путь (длины 0 или больше) из v в w в графе G.

E’:

(a, b)E & (b, c)  E  (a, b)E’ & (b, c)  E’ & (a, c)  E

Построение транзитивного замыкания графа. Пример



Обозначим через tij(k) наличие пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M – матрица смежностей графа G.

Обозначим через tij(k) наличие пути из вершины с номером i в вершину с номером j с промежуточными вершинами из множества {1, 2, …, k}. M – матрица смежностей графа G.

M[i, j] , если k = 0,

tij(k) =

tij(k-1)  (tik(k-1)  tkj(k-1) ), если k1

T(n) содержит искомое решение.

Алгоритм построения транзитивного замыкания графа

Tranzitive_Clusure(M, n)

{

T(0)  M;

for k  1 to n do

for i 1 to n do

for j  1 to n do

tij(k)  tij(k-1)  (tik(k-1)  tkj(k-1) );

return T(n);

}





Похожие:

Лекция 13 Топологическая сортировка iconСортировка – определение очередности оказания первой помощи пострадавшим в дтп. Сортировка

Лекция 13 Топологическая сортировка iconСортировка- это упорядочивание данных (числа, текст, даты, логические значения) в электронных таблицах. Можно сортировать по возрастанию или по убыванию. Сортировка

Лекция 13 Топологическая сортировка iconСортировка в базах данных Сортировка – процесс упорядочения записей в таблице
При использовании строки меню появляется диалоговое окно в котором можно задать параметры сортировки
Лекция 13 Топологическая сортировка iconБиометрическая сортировка трупов в очаге катастрофы с многочисленными человеческими жертвами

Лекция 13 Топологическая сортировка iconЯзыки и методы конструирования программ
...
Лекция 13 Топологическая сортировка iconСведения о работе
Этапы и формы работы: поиск, анализ, сортировка, обработка и оформление информации; опрос, эксперимент, фотографирование
Лекция 13 Топологическая сортировка iconЛекция 1 Основные понятия и определения теоретической механики Лекция 2 Виды связей и реакции связей Лекция 3 Момент силы относительно точки Лекция 4 Кинематика точки
Теоретическая механика это наука о наиболее общих законах механиче­ского движения и равновесия материальных объектов
Лекция 13 Топологическая сортировка iconСортировка это процесс упорядочения некоторого множества элементов, на котором определены отношения порядка >
Имеется последовательность однотипных записей, одно из полей которых выбрано в качестве ключевого (ключ сортировки)
Лекция 13 Топологическая сортировка iconАудитория Odnoklassniki ru Апрель 2011
Россия, Апрель 2011, от Monthly Reach; сортировка по доле аудитории в возрасте 12-24
Лекция 13 Топологическая сортировка iconАудитория Odnoklassniki ru Май 2011
Россия, Май 2011, от Monthly Reach; сортировка по доле аудитории в возрасте 12-24
Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница