Топологическая сортировка, пути в графе - презентация, доклад, проект скачать

Нажмите для полного просмотра!

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Топологическая сортировка, пути в графе. Доклад-сообщение содержит 50 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

Топологическая сортировка Определение. Частичным порядком на множестве А называется отношение R, определенное на А и такое, что R транзитивно, для всех a  A утверждение aRa ложно, т.е. отношение R иррефлексивно. Из свойств (1) и (2) следует, что если aRb истинно, то bRa ложно (асимметричность).

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

Определение. Линейный порядок R на множестве А — это такой частичный порядок, что если a и b принадлежат А, то либо aRb, либо bRa, либо a = b. Определение. Линейный порядок R на множестве А — это такой частичный порядок, что если a и b принадлежат А, то либо aRb, либо bRa, либо a = b. Если А — конечное множество, то линейный порядок R удобно представлять , считая все элементы множества А расположенными в виде последовательности a1, a2,..., an, для которой имеет место aiRaj тогда и только тогда, когда i < j.

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

Алгоритм. Топологическая сортировка Вход. Частичный порядок R на конечном множестве А. Выход. Линейный порядок R' на А, для которого R  R'. Метод. Так как А — конечное множество, линейный порядок 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.

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

Топологическая сортировка. Реализация на иерархических списках 1< 2; 3< 1; 4

Слайд 12

Описание слайда:

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

Слайд 13

Описание слайда:

Работа алгоритма(построение) 1< 2; 2< 5; 4 < 1; 2 < 6; 3 < 1;

Слайд 14

Описание слайда:

Работа алгоритма (перестройка списка)

Слайд 15

Описание слайда:

Кратчайшие пути Пусть G = (V, E) – ориентированный граф. Поставим в оответствие каждому ребру eE в графе 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)

Слайд 16

Описание слайда:

Ребра отрицательного веса Веса ребер могут ребер могут быть отрицательными. Важно знать, имеются ли циклы отрицательного веса. Если из вершины s можно добраться до цикла отрицательного веса, то можно обойти этот цикл сколь угодно раз, при этом вес все время будет уменьшаться. Для вершин этого цикла кратчайших путей не существует. Если циклов отрицательного веса нет, то любой цикл можно выбросить. Путей без циклов конечное число, так что вес кратчайшего пути определен корректно.

Слайд 17

Описание слайда:

Пусть G = (V, E) – заданный граф. Пусть G = (V, E) – заданный граф. Для каждой вершины v  V мы будем помнить ее предшественника. Релаксация – постепенное уточнение верхней оценки на вес кратчайшего пути в заданную вершину. Свойства оптимальности. Лемма 1. Отрезки кратчайших путей являются кратчайшими: Если p(v1, v2, … , vk) – кратчайший путь из v1 в vk и 1 ≤ i ≤ j ≤ 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).

Слайд 18

Описание слайда:

Идея алгоритма нахождения кратчайших путей Идея алгоритма нахождения кратчайших путей из одной вершины во все другие Строится множество S, содержащее вершины графа, кратчайшие расстояния до которых от источника известны. На каждом шаге добавляется тот из оставшихся узлов, кратчайшее расстояние до которого меньше всех других оставшихся узлов.

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Техника релаксации Для каждого ребра (u,v) храним d[v] – верхнюю оценку кратчайшего пути из s в v. Initialize (G,s){ for (для v  V) { d[v] ← ∞ Π[v] ← NULL; } d[s] ← 0; }

Слайд 21

Описание слайда:

Релаксация ребра (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; } }

Слайд 22

Описание слайда:

Слайд 23

Описание слайда:

В ходе работы алгоритма поддерживается множество S, В ходе работы алгоритма поддерживается множество S, состоящее из вершин, для которых δ(s,v) уже найдено ( т.е. d[s,v]= δ(s,v)). Выбираем вершину u V \ S c наименьшим d[u]; Добавляем вершину u к множеству S; Выполняем релаксацию для всех инцидентных u ребер; Пока в S не добавили все вершины, повторять шаги 1-3.

Слайд 24

Описание слайда:

Алгоритм Дейкстры Dijkstra(G,w,s){ Initialize(G,s); S ← ø; Q ← V; //очередь с приоритетами While (Q ≠ ø){ u ← get(Q); //выбрать ближайшую S ← S U {u}; for (для v  Adj[u]) Relax ( u, v, w); } }

Слайд 25

Описание слайда:

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

Слайд 26

Описание слайда:

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

Слайд 27

Описание слайда:

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

Слайд 28

Описание слайда:

Снова пытаемся уменьшить расстояния у смежных вершин, пытаясь Снова пытаемся уменьшить расстояния у смежных вершин, пытаясь пройти в них через 2-ю. Смежные вершины к 2 являются 1, 3, 4. Вершина 1 уже посещалась, поэтому с 1-й вершиной ничего не делаем. Вершина 3: если идти в неё через 2, то длина такого пути будет 7 + 10 = 17. Но текущее расстояние у нее 9

Слайд 29

Описание слайда:

Все смежные вершины с вершиной 2 просмотрены, замораживаем расстояние Все смежные вершины с вершиной 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Слайд 30

Описание слайда:

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

Слайд 31

Описание слайда:

Слайд 32

Описание слайда:

Реализация с дополнительным массивом - O(n2) Массив D[v] содержит стоимость текущего кратчайшего пути из s в v.

Слайд 33

$Dijkstra Dijkstra { S  {s}; D[s]  0; для всех v V \ {v0} выполнить: D[v] = w (s, v); пока S ≠ V выполнять: { выбрать узел u  V \ S, для которого...$

Описание слайда:

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)); } }

Слайд 34

Описание слайда:

Пример № 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

Слайд 35

Описание слайда:

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

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

Алгоритм Беллмана — Форда За время O(n × m) алгоритм находит кратчайшие пути от одной вершины графа до всех остальных, допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом (Bellman) и Лестером Фордом (Ford). Алгоритм маршрутизации RIP был впервые разработан в 1969 году, как основной для сети ARPANET. В 1969 году Агентство передовых исследовательских проектов (ARPA) предложило разработать компьютерную сеть.

Слайд 38

Описание слайда:

Компьютерная сеть была названа ARPANET, все работы финансировались за счёт Министерства обороны США. Затем сеть ARPANET начала активно расти и развиваться, её начали использовать учёные из разных областей науки. В 1973 году к сети были подключены первые иностранные организации из Великобритании и Норвегии, сеть стала международной. Стоимость пересылки электронного письма по сети ARPANET составляла 50 центов. В 1984 году у сети ARPANET появился серьёзный соперник, Национальный фонд науки США (NSF) основал обширную межуниверситетскую сеть NSFNet, которая имела гораздо бо́льшую пропускную способность (56 кбит/с), нежели ARPANET. В 1990 году сеть ARPANET прекратила своё существование, полностью проиграв конкуренцию NSFNet.

Слайд 39

Описание слайда:

Идея алгоритма Идея алгоритма Алгоритм позволяет очень просто определить, существует ли в графе G отрицательный цикл, достижимый из вершины s. Для проверки нужно произвести внешнюю итерацию цикла |V| раз. Если при исполнении последней итерации длина кратчайшего пути до какой-либо вершины строго уменьшилась, то в графе есть отрицательный цикл, достижимый из s. На основе этого можно предложить следующую оптимизацию. Можно отслеживать изменения в графе и, как только они закончатся, дальнейшие итерации будут бессмысленны.

Слайд 40

Описание слайда:

Bellman-Ford(G,w,s) { Bellman-Ford(G,w,s) { Initialize(G,s); for(i=1; id[u]+w(u,v) return 0; return 1; }

Слайд 41

Описание слайда:

Слайд 42

Описание слайда:

Нахождение кратчайших путей между всеми парами вершин Строим матрицу стоимостей: w(i, j), если ребро (i, j)E M[i, j] = +∞ , если ребро (i, j)E 0, если i = j Обозначим через d [i, j] матрицу кратчайших путей между всеми вершинами. Вершины занумеруем числами от 1 до n.

Слайд 43

Описание слайда:

Алгоритм Флойда-Уоршолла Обозначим через 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) содержит искомое решение

Слайд 44

Описание слайда:

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); }

Слайд 45

Описание слайда:

Транзитивное замыкание графа Пусть 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’

Слайд 46

Описание слайда:

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

Слайд 47

Описание слайда:

Обозначим через 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) содержит искомое решение.

Слайд 48

$Алгоритм построения транзитивного замыкания графа Tranzitive_Closure(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) ...$

Описание слайда:

Алгоритм построения транзитивного замыкания графа Tranzitive_Closure(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); }