🗊Презентация Кратчайшие пути в графе топологическая сортировка

Нажмите для полного просмотра!
Кратчайшие пути в графе топологическая сортировка, слайд №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Кратчайшие пути в графе топологическая сортировка, слайд №51Кратчайшие пути в графе топологическая сортировка, слайд №52Кратчайшие пути в графе топологическая сортировка, слайд №53Кратчайшие пути в графе топологическая сортировка, слайд №54

Содержание

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

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


Слайд 1


Кратчайшие пути в графе топологическая сортировка, слайд №1
Описание слайда:

Слайд 2





КРАТЧАЙШИЕ пути в графе
Топологическая сортировка
Лекция 17-18
Описание слайда:
КРАТЧАЙШИЕ пути в графе Топологическая сортировка Лекция 17-18

Слайд 3





План лекции
Кратчайшие пути
Алгоритм Дейкстры
Алгоритм Беллмана-Форда
Алгоритм Флойда-Уоршелла
Топологическая сортировка
Описание слайда:
План лекции Кратчайшие пути Алгоритм Дейкстры Алгоритм Беллмана-Форда Алгоритм Флойда-Уоршелла Топологическая сортировка

Слайд 4





Кратчайшие пути
Пусть G = (V, E) – ориентированный граф и w: E  R+ -- функция стоимости ребер G
Длиной ребра e называется значение w (e)
Длиной пути p = (v0, v1, … , vk) называется сумма w(p) = ∑ w(vi-1, vi ) длин ребер, входящих в p
Описание слайда:
Кратчайшие пути Пусть G = (V, E) – ориентированный граф и w: E  R+ -- функция стоимости ребер G Длиной ребра e называется значение w (e) Длиной пути p = (v0, v1, … , vk) называется сумма w(p) = ∑ w(vi-1, vi ) длин ребер, входящих в p

Слайд 5





Кратчайшие пути
Длиной кратчайшего пути из u в v называется δ(u, v) = min { w(p) | p = (u, …, v) путь в графе G }
Считаем минимум пустого множества min  = 
Кратчайшим путём из u в v называется путь из u в v, для которого w(p) = δ(u, v)
Кратчайших путей может быть несколько
Описание слайда:
Кратчайшие пути Длиной кратчайшего пути из u в v называется δ(u, v) = min { w(p) | p = (u, …, v) путь в графе G } Считаем минимум пустого множества min  =  Кратчайшим путём из u в v называется путь из u в v, для которого w(p) = δ(u, v) Кратчайших путей может быть несколько

Слайд 6





Пример
Описание слайда:
Пример

Слайд 7





Корректность определения и рёбра отрицательной длины
Условие w(e) >= 0 можно заменить на менее строгое условие отсутствия циклов отрицательной длины
Если циклов отрицательной длины нет, то длина кратчайшего пути определена корректно
Кратчайший путь не содержит циклов
Путей без циклов конечное число
Если есть цикл отрицательной длины, то для любых вершин u, v из такого цикла δ(u, v) = -, но кратчайшего пути нет
длину любого пути из u в v можно уменьшить, обойдя цикл ещё один раз
Описание слайда:
Корректность определения и рёбра отрицательной длины Условие w(e) >= 0 можно заменить на менее строгое условие отсутствия циклов отрицательной длины Если циклов отрицательной длины нет, то длина кратчайшего пути определена корректно Кратчайший путь не содержит циклов Путей без циклов конечное число Если есть цикл отрицательной длины, то для любых вершин u, v из такого цикла δ(u, v) = -, но кратчайшего пути нет длину любого пути из u в v можно уменьшить, обойдя цикл ещё один раз

Слайд 8





Алгоритм Дейкстры -- схема
Э́дсгер Ви́бе Де́йкстра 1930 – 2002
Edsger Wybe Dijkstra
Dijkstra, E. W. (1959). "A note on two problems in connection with graphs". Numerische Mathematik 1: 269–271.
Описание слайда:
Алгоритм Дейкстры -- схема Э́дсгер Ви́бе Де́йкстра 1930 – 2002 Edsger Wybe Dijkstra Dijkstra, E. W. (1959). "A note on two problems in connection with graphs". Numerische Mathematik 1: 269–271.

Слайд 9





Алгоритм Дейкстры -- схема
Вычисляем расстояния от вершины-источника до остальных вершин графа
Строим множество S вершин графа, кратчайшие расстояния от которых до источника известны
На каждом шаге
добавляем в S вершину vmin, которая ближе всего к источнику среди оставшихся вершин V \ S
обновляем расстояния от источника до соседей vmin
Описание слайда:
Алгоритм Дейкстры -- схема Вычисляем расстояния от вершины-источника до остальных вершин графа Строим множество S вершин графа, кратчайшие расстояния от которых до источника известны На каждом шаге добавляем в S вершину vmin, которая ближе всего к источнику среди оставшихся вершин V \ S обновляем расстояния от источника до соседей vmin

Слайд 10





Пример (Википедия) – шаг 1
S = , d[] = { 0 ,  ,  ,  ,  ,  }
==> vmin = 1
==> S = {1}
==> d[] = { 0 , 7 , 9 ,  ,  , 14 }
Описание слайда:
Пример (Википедия) – шаг 1 S = , d[] = { 0 ,  ,  ,  ,  ,  } ==> vmin = 1 ==> S = {1} ==> d[] = { 0 , 7 , 9 ,  ,  , 14 }

Слайд 11





Пример – шаг 2
S = {1}, d[] = { 0 , 7 , 9 ,  ,  , 14 }
==> vmin = 2
==> S = {1, 2}
==> d[] = { 0 , 7 , 9 , 22 ,  , 14 }
Описание слайда:
Пример – шаг 2 S = {1}, d[] = { 0 , 7 , 9 ,  ,  , 14 } ==> vmin = 2 ==> S = {1, 2} ==> d[] = { 0 , 7 , 9 , 22 ,  , 14 }

Слайд 12





Пример – шаг 3
S = {1, 2}, d[] = { 0 , 7 , 9 , 22 ,  , 14 }
==> vmin = 3
==> S = {1, 2, 3}
==> d[] = { 0 , 7 , 9 , 20 ,  , 11 }
Описание слайда:
Пример – шаг 3 S = {1, 2}, d[] = { 0 , 7 , 9 , 22 ,  , 14 } ==> vmin = 3 ==> S = {1, 2, 3} ==> d[] = { 0 , 7 , 9 , 20 ,  , 11 }

Слайд 13





Пример – шаг 4
S = {1, 2}, d[] = { 0 , 7 , 9 , 20 ,  , 11 }
==> vmin = 6
==> S = {1, 2, 3, 6}
==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }
Описание слайда:
Пример – шаг 4 S = {1, 2}, d[] = { 0 , 7 , 9 , 20 ,  , 11 } ==> vmin = 6 ==> S = {1, 2, 3, 6} ==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }

Слайд 14





Пример – шаг 5
S = {1, 2, 3, 6}, d[] = { 0 , 7 , 9 , 20 , 20 , 11 }
==> vmin = 4 (зависит от того, как мы ищем минимум)
==> S = {1, 2, 3, 4, 6}
==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }
Описание слайда:
Пример – шаг 5 S = {1, 2, 3, 6}, d[] = { 0 , 7 , 9 , 20 , 20 , 11 } ==> vmin = 4 (зависит от того, как мы ищем минимум) ==> S = {1, 2, 3, 4, 6} ==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }

Слайд 15





Пример – шаг 6
S = {1, 2, 3, 6}, d[] = { 0 , 7 , 9 , 20 , 20 , 11 }
==> vmin = 5
==> S = {1, 2, 3, 4, 5, 6}
==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }
Описание слайда:
Пример – шаг 6 S = {1, 2, 3, 6}, d[] = { 0 , 7 , 9 , 20 , 20 , 11 } ==> vmin = 5 ==> S = {1, 2, 3, 4, 5, 6} ==> d[] = { 0 , 7 , 9 , 20 , 20 , 11 }

Слайд 16





Алгоритм Дейкстры
// S -- множество вершин v, для которых min
// расстояние δ(s,v) от источника s уже найдено
// d[v] – известная оценка сверху для δ(s,v)
Пока S != V
Выбираем вершину u V \ S c наименьшим d[u]
Добавляем вершину u к множеству S
Обновляем d[v] для всех соседей u
Описание слайда:
Алгоритм Дейкстры // S -- множество вершин v, для которых min // расстояние δ(s,v) от источника s уже найдено // d[v] – известная оценка сверху для δ(s,v) Пока S != V Выбираем вершину u V \ S c наименьшим d[u] Добавляем вершину u к множеству S Обновляем d[v] для всех соседей u

Слайд 17





Алгоритм Дейкстры
Dijkstra( граф G = (V,E), вершина s из V)
S  {s};
D[s]  0;
D[v] = w (s, v) для всех v != s;
пока S ≠ V
выбрать вершину u  V \ S, для которого D[u] принимает наименьшее значение;
добавить u к S;
для каждого соседа v вершины u
D[v] = min (D[v], D[u] + w(u, v));
Описание слайда:
Алгоритм Дейкстры Dijkstra( граф G = (V,E), вершина s из V) S  {s}; D[s]  0; D[v] = w (s, v) для всех v != s; пока S ≠ V выбрать вершину u  V \ S, для которого D[u] принимает наименьшее значение; добавить u к S; для каждого соседа v вершины u D[v] = min (D[v], D[u] + w(u, v));

Слайд 18





Алгоритм Дейкстры С
// N -- число вершин в графе, s – источник
void sp(const int G[], int N, int s, int dmin[])
{
	int *blue = calloc(N, sizeof(*blue)), i;
	if (blue == 0) return;
	for (i = 0; i < N; ++i) dmin[i] = G[s*N+i];
	dmin[s] = 0; blue[s] = 1; // Красим вершины множества S в синий цвет
	for (i = 0; i < N; ++i) {
		int jmin = -1, j;
		for (j = 0; j < N; ++j)
			if (!blue[j] && (jmin == -1 || dmin[j] <= dmin[jmin]))
				jmin = j;
		if (jmin == -1) break; // Достижимые вершины кончились
		blue[jmin] = 1; // расстояние найдено
		for (j = 0; j < N; ++j) // Обновляем расстояния до соседей jmin
			if (!blue[j] && d[jmin]+G[j*N+jmin] < dmin[j])
				dmin[j] = dmin[jmin]+G[j*N+jmin];
	}
	free(blue);
}
Описание слайда:
Алгоритм Дейкстры С // N -- число вершин в графе, s – источник void sp(const int G[], int N, int s, int dmin[]) { int *blue = calloc(N, sizeof(*blue)), i; if (blue == 0) return; for (i = 0; i < N; ++i) dmin[i] = G[s*N+i]; dmin[s] = 0; blue[s] = 1; // Красим вершины множества S в синий цвет for (i = 0; i < N; ++i) { int jmin = -1, j; for (j = 0; j < N; ++j) if (!blue[j] && (jmin == -1 || dmin[j] <= dmin[jmin])) jmin = j; if (jmin == -1) break; // Достижимые вершины кончились blue[jmin] = 1; // расстояние найдено for (j = 0; j < N; ++j) // Обновляем расстояния до соседей jmin if (!blue[j] && d[jmin]+G[j*N+jmin] < dmin[j]) dmin[j] = dmin[jmin]+G[j*N+jmin]; } free(blue); }

Слайд 19





Сложность алгоритма Дейкстры по времени
Сложность операции поиска min и операции обновления элемента зависит от типа dmin
Массив
Пирамида из пирамидальной сортировки
Фибоначчиева куча (Тарьян, Фредман 1984)
Обязательно знать оценки сложности поиска min и обновления элемента
Реализация операций и доказательство оценок -- по желанию
Описание слайда:
Сложность алгоритма Дейкстры по времени Сложность операции поиска min и операции обновления элемента зависит от типа dmin Массив Пирамида из пирамидальной сортировки Фибоначчиева куча (Тарьян, Фредман 1984) Обязательно знать оценки сложности поиска min и обновления элемента Реализация операций и доказательство оценок -- по желанию

Слайд 20





Алгоритм Беллмана-Форда
Если есть ребера длины < 0, то алгоритм Дейкстры может вычислить dmin[vmin] > δ(s, vmin)
если есть вершина vS и путь p отрицательной длины из v в vmin по вершинам V\S – см. рисунок
Как вычислять кратчайшие пути в этом случае?
Описание слайда:
Алгоритм Беллмана-Форда Если есть ребера длины < 0, то алгоритм Дейкстры может вычислить dmin[vmin] > δ(s, vmin) если есть вершина vS и путь p отрицательной длины из v в vmin по вершинам V\S – см. рисунок Как вычислять кратчайшие пути в этом случае?

Слайд 21





Алгоритм Беллмана-Форда
Вычисление кратчайших путей в графе c ребрами и/или циклами отрицательной длины за O(|V| × |E|) операций
Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics 16: 87–90. MR 0102435.
Ford, Lester Randolph, Jr.; Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.
Описание слайда:
Алгоритм Беллмана-Форда Вычисление кратчайших путей в графе c ребрами и/или циклами отрицательной длины за O(|V| × |E|) операций Bellman, Richard (1958). "On a routing problem". Quarterly of Applied Mathematics 16: 87–90. MR 0102435. Ford, Lester Randolph, Jr.; Fulkerson, D. R. (1962). Flows in Networks. Princeton University Press.

Слайд 22





Алгоритм Беллмана-Форда -- схема
/* Вычисляем длины кратчайших путей от источника до вершин графа в порядке увеличения числа ребер в пути */
dmin[s] = 0, dmin[v] =  для v != s
Для i = 1, …, |V|-1 // кратчайшем пути <= |V|-1 ребер
Для каждой вершины v
dnext[v] = min { dmin[v], dmin[u]+w(u,v) }
dmin = dnext
// обычно значение min{…} записывают сразу в dmin
Если dmin[u]+w(u,v) < dmin[v] для одного из ребер (u, v), то G содержит цикл отрицательной длины
Описание слайда:
Алгоритм Беллмана-Форда -- схема /* Вычисляем длины кратчайших путей от источника до вершин графа в порядке увеличения числа ребер в пути */ dmin[s] = 0, dmin[v] =  для v != s Для i = 1, …, |V|-1 // кратчайшем пути <= |V|-1 ребер Для каждой вершины v dnext[v] = min { dmin[v], dmin[u]+w(u,v) } dmin = dnext // обычно значение min{…} записывают сразу в dmin Если dmin[u]+w(u,v) < dmin[v] для одного из ребер (u, v), то G содержит цикл отрицательной длины

Слайд 23





Алгоритм Беллмана-Форда C
int BellmanFord(const int G[], int N, int s, int dmin[])
{
    int i, v, u;
    for (i = 0; i < N; ++i) dmin[i] = G[s*N+i];
    dmin[s] = 0;
    for (i = 1; i < N; ++i)
        for (v = 0; v < N; ++v) 
            for (u = 0; u < N; ++u) 
                if (dmin[v] > dmin[u] + G[u*N+v])
                    dmin[v] = dmin[u] + G[u*N+v];
    for (v = 0; v < N; ++v) 
        for (u = 0; u < N; ++u) 
            if (dmin[v]>dmin[u]+G[u*N+v]) return 0;
    return 1;
}
Описание слайда:
Алгоритм Беллмана-Форда C int BellmanFord(const int G[], int N, int s, int dmin[]) { int i, v, u; for (i = 0; i < N; ++i) dmin[i] = G[s*N+i]; dmin[s] = 0; for (i = 1; i < N; ++i) for (v = 0; v < N; ++v) for (u = 0; u < N; ++u) if (dmin[v] > dmin[u] + G[u*N+v]) dmin[v] = dmin[u] + G[u*N+v]; for (v = 0; v < N; ++v) for (u = 0; u < N; ++u) if (dmin[v]>dmin[u]+G[u*N+v]) return 0; return 1; }

Слайд 24





Алгоритм Флойда-Уоршелла
Вычисление кратчайших расстояний между всеми парами вершин графа
Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM 9 (1): 11–12
Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM 5 (6): 345
Описание слайда:
Алгоритм Флойда-Уоршелла Вычисление кратчайших расстояний между всеми парами вершин графа Warshall, Stephen (January 1962). "A theorem on Boolean matrices". Journal of the ACM 9 (1): 11–12 Floyd, Robert W. (June 1962). "Algorithm 97: Shortest Path". Communications of the ACM 5 (6): 345

Слайд 25





Алгоритм Флойда-Уоршелла -- схема
// Нумеруем вершины числами от 1 до N
// Вычисляем dmin[i, j] = кратчайшее расстояние от вершины i до
// вершины j
// Сложность по времени O(N^3)
// Вычисляем кратчайшие расстояния d[k, i, j] от вершины i до вершины j
// для путей с промежуточными вершинами из множества {1,…,k}
Для i, j = 1, …, N d[0, i, j] =
0, если i=j
w(i, j),  если (i, j)  E 
∞ ,  если (i, j)  E 
Для k = 1, …, N
Для i, j = 1, …, N
d[k, i, j] = min(d[k-1, i, j], d[k-1, i, k] + d[k-1, k, j])
// dmin[i, j] == d[N, i, j]
Описание слайда:
Алгоритм Флойда-Уоршелла -- схема // Нумеруем вершины числами от 1 до N // Вычисляем dmin[i, j] = кратчайшее расстояние от вершины i до // вершины j // Сложность по времени O(N^3) // Вычисляем кратчайшие расстояния d[k, i, j] от вершины i до вершины j // для путей с промежуточными вершинами из множества {1,…,k} Для i, j = 1, …, N d[0, i, j] = 0, если i=j w(i, j), если (i, j)  E ∞ , если (i, j)  E Для k = 1, …, N Для i, j = 1, …, N d[k, i, j] = min(d[k-1, i, j], d[k-1, i, k] + d[k-1, k, j]) // dmin[i, j] == d[N, i, j]

Слайд 26





Топологическая сортировка
Топологической сортировкой ориентированного графа G = (V, E) называется нумерация Т вершин V такая, что для каждой дуги (v, u) графа G верно T(v) < T(u)
Если возможна топологическая сортировка G, то в G нет циклов
Почему?
Если в G нет циклов, то возможна топологическая сортировка G
Алгоритм топологической сортировки
Описание слайда:
Топологическая сортировка Топологической сортировкой ориентированного графа G = (V, E) называется нумерация Т вершин V такая, что для каждой дуги (v, u) графа G верно T(v) < T(u) Если возможна топологическая сортировка G, то в G нет циклов Почему? Если в G нет циклов, то возможна топологическая сортировка G Алгоритм топологической сортировки

Слайд 27





Алгоритм топологической сортировки
Вход
	Ориентированный граф G = (V, E)
Выход
	Топологическая сортировка G – нумерация Т такая, что что для каждой дуги (v, u) графа G верно T(v) < T(u)
t = 1;
Для i = 1, …, N
Найти вершину v такую, что нет дуг входящих в v
	Если нет такой вершины, то граф содержит цикл – почему?
T[v] = t;
t = t+1;
Удалить из E все дуги исходящие из v, удалить v из V
Описание слайда:
Алгоритм топологической сортировки Вход Ориентированный граф G = (V, E) Выход Топологическая сортировка G – нумерация Т такая, что что для каждой дуги (v, u) графа G верно T(v) < T(u) t = 1; Для i = 1, …, N Найти вершину v такую, что нет дуг входящих в v Если нет такой вершины, то граф содержит цикл – почему? T[v] = t; t = t+1; Удалить из E все дуги исходящие из v, удалить v из V

Слайд 28





Топологическая сортировка -- пример
Описание слайда:
Топологическая сортировка -- пример

Слайд 29





Топологическая сортировка -- пример
Описание слайда:
Топологическая сортировка -- пример

Слайд 30





Топологическая сортировка с матрицей смежности
Описание слайда:
Топологическая сортировка с матрицей смежности

Слайд 31





Топологическая сортировка с 
иерархическими списками
1< 2; 3< 1; 4<1; 2< 5; 2< 6;
Описание слайда:
Топологическая сортировка с иерархическими списками 1< 2; 3< 1; 4<1; 2< 5; 2< 6;

Слайд 32





Топологическая сортировка – связь с частичным порядком
Частичным порядком на множестве А называется отношение R на А такое, что
верно a R b, верно b R c => верно a R c (транизтивность)
не верно a R а (иррефлексивность)
Следствие свойств (1) и (2)
если верно a R b, то не верно b R a (антисимметричность)
Описание слайда:
Топологическая сортировка – связь с частичным порядком Частичным порядком на множестве А называется отношение R на А такое, что верно a R b, верно b R c => верно a R c (транизтивность) не верно a R а (иррефлексивность) Следствие свойств (1) и (2) если верно a R b, то не верно b R a (антисимметричность)

Слайд 33





Топологическая сортировка – связь с частичным порядком
Примеры частичных порядков
Зависимость по записи/чтению данных между операторами в программе без циклов
Зависимость курсов в учебной программе по излагаемому материалу
Зависимость строительных и т.п. работ
Томас Хэрриот (англ. Thomas Harriot) (1560 год — 2 июля 1621 года) — английский астроном, математик, этнограф и переводчик
Придумал знаки для операций сравнения: «>» (больше) и «<» (меньше)
Впервые привез картофель в Великобританию и Ирландию
Описание слайда:
Топологическая сортировка – связь с частичным порядком Примеры частичных порядков Зависимость по записи/чтению данных между операторами в программе без циклов Зависимость курсов в учебной программе по излагаемому материалу Зависимость строительных и т.п. работ Томас Хэрриот (англ. Thomas Harriot) (1560 год — 2 июля 1621 года) — английский астроном, математик, этнограф и переводчик Придумал знаки для операций сравнения: «>» (больше) и «<» (меньше) Впервые привез картофель в Великобританию и Ирландию

Слайд 34





Топологическая сортировка – связь с частичным порядком
Если G = ( V, E ) -- ациклический граф, то отношение R = E -- частичный порядок на множестве V
Если отношение R частичный порядок на конечном множестве A, то G = ( A, R ) -- ациклический граф
Пример
1 < 8, 1 < 5, 5 < 8,
5 < 9, 6 < 9, 3 < 6,
3 < 7
Описание слайда:
Топологическая сортировка – связь с частичным порядком Если G = ( V, E ) -- ациклический граф, то отношение R = E -- частичный порядок на множестве V Если отношение R частичный порядок на конечном множестве A, то G = ( A, R ) -- ациклический граф Пример 1 < 8, 1 < 5, 5 < 8, 5 < 9, 6 < 9, 3 < 6, 3 < 7

Слайд 35





Топологическая сортировка – связь с частичным порядком
Линейный порядок R на множестве А -- это такой частичный порядок, что для любые a и b из А сравнимы
либо a R b, либо b R a, либо a = b
Линейный порядок на конечном множестве А = {a1, a2,..., an} можно задать перестановкой ap1, ap2,..., apn такой, что api R api+1
Описание слайда:
Топологическая сортировка – связь с частичным порядком Линейный порядок R на множестве А -- это такой частичный порядок, что для любые a и b из А сравнимы либо a R b, либо b R a, либо a = b Линейный порядок на конечном множестве А = {a1, a2,..., an} можно задать перестановкой ap1, ap2,..., apn такой, что api R api+1

Слайд 36





Топологическая сортировка – связь с частичным порядком
Частичный порядок R на множестве А вложен в линейный порядок R', если R' – это линейный порядок и RR', т. е. a R b влечет a R' b для всех а и b из А
Алгоритм топологической сортировки вычисляет линейный порядок, в который вложен данный частичный порядок
Описание слайда:
Топологическая сортировка – связь с частичным порядком Частичный порядок R на множестве А вложен в линейный порядок R', если R' – это линейный порядок и RR', т. е. a R b влечет a R' b для всех а и b из А Алгоритм топологической сортировки вычисляет линейный порядок, в который вложен данный частичный порядок

Слайд 37





Заключение
Кратчайшие пути
Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла
Топологическая сортировка
Алгоритм, связь с отношениями порядка
Описание слайда:
Заключение Кратчайшие пути Алгоритмы Дейкстры, Беллмана-Форда, Флойда-Уоршелла Топологическая сортировка Алгоритм, связь с отношениями порядка

Слайд 38





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

Слайд 39





Построение транзитивного замыкания графа. Пример
Описание слайда:
Построение транзитивного замыкания графа. Пример

Слайд 40





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

Слайд 41





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

Слайд 42





Пусть 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).
Описание слайда:
Пусть 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).

Слайд 43





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

Слайд 44





Релаксация ребра (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;
	}
}
Описание слайда:
Релаксация ребра (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; } }

Слайд 45


Кратчайшие пути в графе топологическая сортировка, слайд №45
Описание слайда:

Слайд 46





Алгоритм Дейкстры
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);
	}
}
Описание слайда:
Алгоритм Дейкстры 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); } }

Слайд 47


Кратчайшие пути в графе топологическая сортировка, слайд №47
Описание слайда:

Слайд 48





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

Слайд 49





Пример
№ 	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
Описание слайда:
Пример № 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

Слайд 50






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

Слайд 51


Кратчайшие пути в графе топологическая сортировка, слайд №51
Описание слайда:

Слайд 52





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);
}
Описание слайда:
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); }

Слайд 53


Кратчайшие пути в графе топологическая сортировка, слайд №53
Описание слайда:

Слайд 54


Кратчайшие пути в графе топологическая сортировка, слайд №54
Описание слайда:



Похожие презентации
Mypresentation.ru
Загрузить презентацию