Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть

Презентация на тему Задача на кратчайший путь

Содержание

2. Задача «Кратчайший путь»Дано: Орграф G, веса c:
3. Консервативные весаОпределение 5.1 Пусть G ― граф
4. Принцип оптимальности Белмана Предложение 5.2
5. ДоказательствоПусть s-v-путь Q короче пути P[s,v].Тогда c(Q)
6. Доказательство (w ∈ Q)Пусть s-v-путь Q короче
7. ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов
8. Упражнение 7.1Дан ациклический орграф G с произвольными
9. Алгоритм ДейкстрыInput: Орграф G, веса c: E(G)
10. Алгоритм Дейкстры (2)Теорема 5.3 (Дейкстра [1959])
11. Скетч доказательства Докажем, что следующие утверждения
12. Алгоритм ДейкстрыInput: Орграф G, веса c: E(G)
13. a) Для всех v ∈ R и
14. b) Для всех v ∈ R:
15. c) Для всех w ∈ V(G)\R: l(w)
16. Алгоритм Дейкстры Теорема 5.3 (Дейкстра [1959])
17. Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса
18. Алгоритм Мура-Беллмана-Форда(2)Теорема 5.4 (Moore [1959], Bellman [1958],
19. Скетч доказательстваНа каждой итерации алгоритма пусть
20. a) l(y) ≥ l(x) + c((x,y)) для
21. b) Если F содержит цикл C, то
22. c) Если функция весов c консервативная, то
23. ИндукцияПусть P кратчайший s-x-путь с не более
24. Алгоритм Мура-Беллмана-ФордаТеорема 5.4 (Moore [1959], Bellman [1958],
25. Допустимый потенциалОпределение 5.5. Пусть G ― орграф
26. Допустимый потенциал (2)Теорема 5.6 Пусть
27. ДоказательствоЕсли π допустимый потенциал, то для каждого
28. Допустимый потенциал Следствие 5.7 Дан
29. Задача «Все Пары Кратчайших путей»Дано: орграф G,
30. Задача «Все Пары Кратчайших путей» (2)Теорема 5.8
31. Алгоритм Флойда-Уоршелла Input: Орграф G с V(G)
32. Шаг 2 For j :=
33. Алгоритм Флойда-Уоршелла (2)Теорема 5.9(Floyd [1962], Warshall [1962]) Алгоритм Флойда-Уоршелла находит решение за время O(n3).
34. Идея доказательстваПусть алгоритм использовал во внешнем цикле
35. Индукция: j0 → j0 + 1j=j0+1ik{1, 2,
36. Метрическое замыканиеОпределение 5.10 Дан связный граф G
37. Метрическое замыкание (2)Следствие 5.11 Пусть G
38. Задача «Минимальный усредненный Цикл»Дано: орграф G, веса
39. Как решать?Задача «Минимальный усредненный Цикл» может быть
40. Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ―
41. Идея доказательстваДокажем, что если μ(G) = 0
42. ДоказательствоПокажем, что существует такое x, что Fn(x)
43. Алгоритм «Минимальный усредненный Цикл»Input: Орграф G, веса
44. Алгоритм «Минимальный усредненный Цикл» Следствие 5.13(Karp
45. Упражнение 7.2Дан орграф G с произвольными весами
46. Упражнение 7.3Дан орграф G с s, t
47. Упражнение 7.4Пусть G ― орграф с консервативными
48. Скачать презентацию
49. Похожие презентации

Задача «Кратчайший путь»Дано: Орграф G, веса c: E(G) → R и две вершины s, t ∈V(G) .Найти s-t-путь минимального веса.

Консервативные весаОпределение 5.1 Пусть G ― граф с весами c: E(G) →

Принцип оптимальности Белмана Предложение 5.2 Дан орграф G с

ДоказательствоПусть s-v-путь Q короче пути P[s,v].Тогда c(Q) + c(e) < c(P).Если w∉Q,

Доказательство (w ∈ Q)Пусть s-v-путь Q короче пути P[s,v].c(Q) + c(e) <

ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами и для

Упражнение 7.1Дан ациклический орграф G с произвольными весами c: E(G) → R

Алгоритм ДейкстрыInput: Орграф G, веса c: E(G) → R+ и вершина s∈

Алгоритм Дейкстры (2)Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит оптимальное решение

Скетч доказательства Докажем, что следующие утверждения верны каждый раз когда выполняется

$a) Для всех v ∈ R и всех w∈V(G)\R: l(v) ≤ l(w)Пусть$ b) Для всех v ∈ R: l(v) ― длина кратчайшего s-v-пути

$c) Для всех w ∈ V(G)\R: l(w) ― длина кратчайшего$ Алгоритм Дейкстры Теорема 5.3 (Дейкстра [1959]) Алгоритм Дейкстры находит оптимальное решение

Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) → R и

Алгоритм Мура-Беллмана-Форда(2)Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм Мура-Беллмана-Форда находит

Скетч доказательстваНа каждой итерации алгоритма пусть

a) l(y) ≥ l(x) + c((x,y)) для всех (x,y) ∈ FF :=

b) Если F содержит цикл C, то C имеет отрицательный суммарный весПусть

c) Если функция весов c консервативная, то (R, F) ― ордерево с

ИндукцияПусть P кратчайший s-x-путь с не более чем k дугами и пусть

Алгоритм Мура-Беллмана-ФордаТеорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм Мура-Беллмана-Форда

Допустимый потенциалОпределение 5.5. Пусть G ― орграф с весами c: E(G) →

Допустимый потенциал (2)Теорема 5.6 Пусть G ― орграф с весами

ДоказательствоЕсли π допустимый потенциал, то для каждого цикла C:⇒ веса консервативны.Пусть веса

Допустимый потенциал Следствие 5.7 Дан орграф G с весами c:

Задача «Все Пары Кратчайших путей»Дано: орграф G, веса c: E(G) → R.Найти

Задача «Все Пары Кратчайших путей» (2)Теорема 5.8 Задача «Все Пары Кратчайших путей»

Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и консервативные веса

Алгоритм Флойда-Уоршелла (2)Теорема 5.9(Floyd [1962], Warshall [1962]) Алгоритм Флойда-Уоршелла находит решение за время O(n3).

Идея доказательстваПусть алгоритм использовал во внешнем цикле (For) вершины j = 1,

Индукция: j0 → j0 + 1j=j0+1ik{1, 2, …, j0}Для любых i и

Метрическое замыканиеОпределение 5.10 Дан связный граф G с весами c: E(G) →

Метрическое замыкание (2)Следствие 5.11 Пусть G ― связный граф и c:

Задача «Минимальный усредненный Цикл»Дано: орграф G, веса c: E(G) → R.Найти цикл

Как решать?Задача «Минимальный усредненный Цикл» может быть решена динамическим программированием.Можно рассматривать только

Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ― орграф с весами c: E(G)

Идея доказательстваДокажем, что если μ(G) = 0 тоПусть G ― орграф с

ДоказательствоПокажем, что существует такое x, что Fn(x) = l(x).μ(G) = 0 ⇒

Алгоритм «Минимальный усредненный Цикл»Input: Орграф G, веса c: E(G) → R. Output:

Алгоритм «Минимальный усредненный Цикл» Следствие 5.13(Karp [1978]) Алгоритм «Минимальный усредненный

Упражнение 7.2Дан орграф G с произвольными весами c:

Упражнение 7.3Дан орграф G с s, t ∈ V(G). Пусть для каждого

Упражнение 7.4Пусть G ― орграф с консервативными весами c: E(G) → R

Упражнение 7.5Пусть G полный граф и c: E(G) → R+. Показать, что

Слайды презентации

Слайд 2 Задача «Кратчайший путь»
Дано: Орграф G, веса c: E(G)

Задача «Кратчайший путь»Дано: Орграф G, веса c: E(G) → R и

→ R и две вершины s, t ∈V(G) .
Найти

s-t-путь минимального веса.

Слайд 3 Консервативные веса
Определение 5.1 Пусть G ― граф с

весами c: E(G) → R . Функция c называется

консервативной если не существует цикла отрицательного веса.

Слайд 4 Принцип оптимальности Белмана
Предложение 5.2

Принцип оптимальности Белмана Предложение 5.2 Дан орграф G с консервативными

Дан орграф G с консервативными весами c: E(G) →

R, и две его вершины s и w. Если e=(v, w) ― последняя дуга некоторого кратчайшего пути P из s в w, тогда P[s,v] (P без ребра e) ― кратчайший путь из s в v.

Слайд 5 Доказательство
Пусть s-v-путь Q короче пути P[s,v].
Тогда c(Q) +

ДоказательствоПусть s-v-путь Q короче пути P[s,v].Тогда c(Q) + c(e) < c(P).Если

c(e) < c(P).
Если w∉Q, то Q + e короче,

чем P.
Противоречие ⇒ w ∈ Q.

Слайд 6 Доказательство (w ∈ Q)
Пусть s-v-путь Q короче пути

P[s,v].
c(Q) + c(e) < c(P)
c(Q[s,w]) = c(Q) + c(e)

– c(Q[v,w]+e) < < c(P) – c(Q[v,w]+e)
Так как Q[v,w]+e является циклом, то c(Q[s,w]) < c(P) – c(Q[v,w]+e) ≤ c(P).
Противоречие.

Слайд 7 Замечание
Принцип оптимальности Белмана выполняется для всех орграфов с

ЗамечаниеПринцип оптимальности Белмана выполняется для всех орграфов с неотрицательными весами и

неотрицательными весами и для всех орграфов без циклов.

dist(s,s) =

0.
dist(s,w) = min{dist(s,v) + c((v,w)): (v,w) ∈ E(G)}
для всех w ∈ V(G)/s.

Слайд 8 Упражнение 7.1
Дан ациклический орграф G с произвольными весами

Упражнение 7.1Дан ациклический орграф G с произвольными весами c: E(G) →

c: E(G) → R и s, t ∈

V(G).
Показать, как найти кратчайший s-t-путь в G за линейное время.

Слайд 9 Алгоритм Дейкстры
Input: Орграф G, веса c: E(G) →

Алгоритм ДейкстрыInput: Орграф G, веса c: E(G) → R+ и вершина

R+ и вершина s∈ V(G).
Output: Кратчайшие пути из

s во все v ∈ V(G) и их длины.

Set l(s) := 0. Set l(v) := ∞ для всех v∈ V(G)\{s}. Set R := ∅.
Найти вершину v ∈ V(G)\R такую, что l(v) = min w∈ V(G)\{R}l(w).
Set R := R⋃{v}.
For всех w∈ V(G)\R таких, что (v,w) ∈ E(G) do:
If l(w) > l(v) + c((v,w)) then
l(w) := l(v) + c((v,w)) и p(w) := v.
5) If R ≠ V(G) then go to 2.

Слайд 10 Алгоритм Дейкстры (2)
Теорема 5.3 (Дейкстра [1959])
Алгоритм

Дейкстры находит оптимальное решение за O(n2) элементарных операций (n=|V(G)|).

Слайд 11 Скетч доказательства
Докажем, что следующие утверждения верны

каждый раз когда выполняется шаг 2 алгоритма.
a) Для

всех v ∈ R и всех w∈ V(G)\R: l(v) ≤ l(w).
b) Для всех v ∈ R: l(v) ― длина кратчайшего s-v-пути в G. Если l(v) < ∞, существует s-v- путь длины l(v), последняя дуга которого есть (p(v),v) и все вершины которого принадлежат R.
c) Для всех w∈ V(G)\R: l(w) ― длина кратчайшего s-w- пути в G[R⋃{w}]. Если l(w) ≠ ∞, то p(w) ∈ R и l(w) = l(p(w)) + c((p(w), w)).

Слайд 12 Алгоритм Дейкстры
Input: Орграф G, веса c: E(G) →

R+ и вершина s∈ V(G).
Output: Кратчайшие пути из

Слайд 13 a) Для всех v ∈ R и всех

$a) Для всех v ∈ R и всех w∈V(G)\R: l(v) ≤$

w∈V(G)\R: l(v) ≤ l(w)
Пусть v вершина выбранная на шаге

2.
Для любых x ∈ R и y ∈ V(G)\R: l(x) ≤ l(v) ≤ l(y).
⇒ a) выполняется после шагов 3 и 4.

Слайд 14 b) Для всех v ∈ R: l(v)

b) Для всех v ∈ R: l(v) ― длина кратчайшего

― длина кратчайшего s-v-пути в G. Если l(v)

∞, существует s-v- путь длины l(v), последняя дуга которого есть (p(v),v) и все вершины которого принадлежат R.

Так как c) справедливо до шага 3, достаточно показать, что никакой s-v-путь в G, содержащий вершины из V(G)\R не имеет длины короче чем l(v).
Пусть ∃ s-v-путь P в G содержащий w ∈ V(G)\R, длина которого меньше l(v).
Пусть w будет первая вершина за R на этом пути.
c) ⇒ l(w) ≤ с(P[s,w])
Так как веса дуг неотрицательны, то с(P[s,w]) ≤ с(P) < l(v).
⇒ l(w) < l(v), противоречие с выбором v.

Слайд 15 c) Для всех w ∈ V(G)\R: l(w) ―

$c) Для всех w ∈ V(G)\R: l(w) ― длина кратчайшего$

длина кратчайшего

s-w- пути в G[R⋃{w}]. Если l(w) ≠ ∞, то p(w) ∈ R и l(w) = l(p(w)) + c((p(w), w)).

Пусть после шагов 3 и 4 существует s-w-путь P в G[R⋃w] длины меньше чем l(w) для некоторого w∈V(G)\R.
Тогда P должен содержать v (в противном случае с) нарушалось уже до выполнения шагов 3 и 4).
Пусть (x,w) ∈ P.
x ∈ R & a) ⇒ l(x) ≤ l(v).
Шаг 4 ⇒ l(w) ≤ l(x) + c((x,w)) ≤ l(v) + c((x,w)).
b) ⇒ l(v) длина кратчайшего s-v-пути.
P содержит s-v-путь и (x,w) ⇒ l(w) ≤ l(x) + c((x,w)) ≤ c(P).
Противоречие.

Слайд 16 Алгоритм Дейкстры
Теорема 5.3 (Дейкстра [1959])
Алгоритм

Дейкстры находит оптимальное решение за O(n2) элементарных операций (n

= |V(G)|).

Слайд 17 Алгоритм Мура-Беллмана-Форда
Input: Орграф G, консервативные веса c:

Алгоритм Мура-Беллмана-Форда Input: Орграф G, консервативные веса c: E(G) → R

E(G) → R и вершина s∈ V(G).
Output: Кратчайшие

пути из s во все v ∈ V(G) и их длины.

Set l(s) := 0 и l(v) := ∞ для всех v∈ V(G)\{s}.
For i := 1 to n – 1 do:
For каждой дуги (v,w) ∈ E(G) do
If l(w) > l(v) + c((v,w)) then
l(w) := l(v) + c((v,w)) и p(w) := v.

Слайд 18 Алгоритм Мура-Беллмана-Форда(2)
Теорема 5.4 (Moore [1959], Bellman [1958], Ford

Алгоритм Мура-Беллмана-Форда(2)Теорема 5.4 (Moore [1959], Bellman [1958], Ford [1956]) Алгоритм Мура-Беллмана-Форда

[1956])
Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm) операций.

Слайд 19 Скетч доказательства
На каждой итерации алгоритма пусть

R := {v∈ V(G): l(v) < ∞} и F := {(x,y) ∈ E(G): x = p(y)}.
Тогда
a) l(y) ≥ l(x) + c((x,y)) для всех (x,y) ∈ F ;
b) Если F содержит цикл C, то C имеет отрицательный суммарный вес;
c) Если функция весов c консервативная, то (R, F) ― ордерево с корнем в s.

Слайд 20 a) l(y) ≥ l(x) + c((x,y)) для всех

(x,y) ∈ F
F := {(x,y) ∈ E(G): x =

p(y)}
Рассмотрим последнюю итерацию, когда p(y) присвоили x.
В этот момент l(y) = l(x) + c((x,y)).
На последующих итерациях l(y) не менялась, а l(x) могла только уменьшиться.

Слайд 21 b) Если F содержит цикл C, то C

b) Если F содержит цикл C, то C имеет отрицательный суммарный

имеет отрицательный суммарный вес
Пусть на некоторой итерации в F

образовался цикл C добавлением дуги (x,y).
Тогда при проверки в операторе if выполнялось l(y) > l(x) + c((x,y)).

a) ⇒ l(w) ≥ l(v) + c((v,w)) для всех (v,w)∈E(С)/{(x,y)}.

Cуммируя по всем неравенствам, получаем, что C имеет отрицательный суммарный вес.

Слайд 22 c) Если функция весов c консервативная, то (R,

c) Если функция весов c консервативная, то (R, F) ― ордерево

F) ― ордерево с корнем в s.
b) ⇒ F

― ациклический.
Для всех x∈R\{s}: p(x)∈R ⇒ (R,F) ― ордерево с корнем в s.
l(x) ― длина s-x-пути в (R,F) для любого x и на всех шагах алгоритма.
Докажем, что после k итераций l(x) не превосходит длину кратчайшего s-x-пути среди всех путей, имеющих не больше k дуг.

Слайд 23 Индукция
Пусть P кратчайший s-x-путь с не более чем

ИндукцияПусть P кратчайший s-x-путь с не более чем k дугами и

k дугами и пусть (w,x) последняя дуга в P.
Тогда

P[s,w] кратчайший s-w-путь с не более чем k –1 дугой.
По индукции l(w) ≤ c(P[s,w]) после k –1 итерации.
Проверяя на итерации k дугу (w,x) имеем
l(x) ≤ l(w) + c((w,x)) ≤ c(P[).
Так как любой путь имеет не более n – 1 дуги, то после n –1 итерации алгоритм находит оптимальное решение.

Слайд 24 Алгоритм Мура-Беллмана-Форда
Теорема 5.4 (Moore [1959], Bellman [1958], Ford

[1956])
Алгоритм Мура-Беллмана-Форда находит оптимальное решение за O(nm)

операций.

Покажем, что этот алгоритм также может быть использован для проверки есть ли в орграфе циклы отрицательного веса.
Попутно определим полезное понятие допустимого потенциала, введенное Эдмондсом и Карпом [1972].

Слайд 25 Допустимый потенциал
Определение 5.5. Пусть G ― орграф с

весами c: E(G) → R, и пусть π :

V(G) → R. Тогда для любой (x,y) ∈ E(G) определим пониженную стоимость (x,y) относительно π через cπ((x,y)) := c((x,y)) + π(x) – π(y). Если cπ(e) ≥ 0 для всех e ∈ E(G), π называется допустимым потенциалом.

Слайд 26 Допустимый потенциал (2)
Теорема 5.6
Пусть G

― орграф с весами c: E(G) → R. Допустимый

потенциал для (G,c) существует тогда и только тогда, когда функция весов c консервативная.

Слайд 27 Доказательство
Если π допустимый потенциал, то для каждого цикла

ДоказательствоЕсли π допустимый потенциал, то для каждого цикла C:⇒ веса консервативны.Пусть

C:

⇒ веса консервативны.
Пусть веса консервативны, добавим новую вершину s

и соединим ее со всеми вершинами выходящими дугами нулевого веса.
Применим алгоритм Мура-Беллмана-Форда к полученному примеру и найдем величины l(v) для всех v ∈ V(G).
l(v) длина кратчайшего s-v-пути для всех v ∈ V(G).
⇒ l(w) ≤ l(v) + c((v,w)) для всех (v,w) ∈ E(G).
l(v) ― допустимый потенциал.

Слайд 28 Допустимый потенциал
Следствие 5.7
Дан орграф

G с весами c: E(G) → R. Алгоритм Мура-Беллмана-Форда

за время O(nm) либо находит допустимый потенциал, либо отрицательный цикл.

Слайд 29 Задача «Все Пары Кратчайших путей»
Дано: орграф G, веса

Задача «Все Пары Кратчайших путей»Дано: орграф G, веса c: E(G) →

c: E(G) → R.
Найти число lst и вершины pst

для всех s, t ∈V(G) с s ≠ t, такие что lst есть длина кратчайшего s-t-пути, и (pst , t) есть последнее ребро такого пути (если оно существует).

Слайд 30 Задача «Все Пары Кратчайших путей» (2)

Теорема 5.8
Задача

Задача «Все Пары Кратчайших путей» (2)Теорема 5.8 Задача «Все Пары Кратчайших

«Все Пары Кратчайших путей» может быть решена за время

O(n3), где n = |V(G)|.

Слайд 31 Алгоритм Флойда-Уоршелла
Input: Орграф G с V(G) =

Алгоритм Флойда-Уоршелла Input: Орграф G с V(G) = {1,...,n} и консервативные

{1,...,n} и консервативные веса c: E(G) →

R.
Output: Матрицы (lij)1≤i,j≤n и (pij)1≤i,j≤n ,где lij ― длина кратчайшего пути из i в j и (pij , j) ― последняя дуга в таком пути (если он существует).

Set lij := c((i, j)) для всех (i, j)∈ E(G). Set lij := ∞ для всех (i, j)∈ (V(G)× V(G))\ E(G) с i≠j. Set lii := 0 для всех i. Set pik := i для всех i, k∈ V(G).
For j := 1 to n do:
For i := 1 to n do: If i≠j then:
For k := 1 to n do: If k≠j then:
If lik > lij + ljk then set lik := lij + ljk and pik := pjk

Слайд 32 Шаг 2
For j := 1

to n do:

For i := 1 to n do: If i≠j then:
For k := 1 to n do: If k≠j then:
If lik > lij + ljk then set lik := lij + ljk and pik := pjk

pjk

Слайд 33 Алгоритм Флойда-Уоршелла (2)

Теорема 5.9(Floyd [1962], Warshall [1962])
Алгоритм

Флойда-Уоршелла находит решение за время O(n3).

Слайд 34 Идея доказательства
Пусть алгоритм использовал во внешнем цикле (For)

Идея доказательстваПусть алгоритм использовал во внешнем цикле (For) вершины j =

вершины j = 1, 2, …, j0. Тогда переменные

lik равны длине кратчайшего i-k-пути с внутренними вершинами из множества {1, 2, …, j0} и (pik,k) последняя дуга в таком пути.
Утверждение справедливо для j0 = 0 (шаг 1).
Справедливость утверждения для j0 = n влечет корректность работы алгоритма.

Слайд 35 Индукция: j0 → j0 + 1

j=j0+1
i
k

{1, 2, …,

Индукция: j0 → j0 + 1j=j0+1ik{1, 2, …, j0}Для любых i

j0}

Для любых i и k при выполнения шага 2

для j = j0 + 1: lik заменяется на lij + ljk ,
если lik > lij + ljk .

Пусть lik получило новое значение.
Осталось показать, что в этом
случае i-(j0 + 1)-путь P и (j0 + 1)-k-путь Q
не имеют общих внутренних вершин.

Слайд 36 Метрическое замыкание
Определение 5.10
Дан связный граф G

с весами c: E(G) → R+.
Метрическим замыканием (G,

c) называется пара (Ĝ, ĉ) , где Ĝ ― полный граф на V (G) и ĉ({x,y}) = dist (G, c)(x,y) для всех x, y ∈ V (G).

Слайд 37 Метрическое замыкание (2)
Следствие 5.11
Пусть G

Метрическое замыкание (2)Следствие 5.11 Пусть G ― связный граф и

― связный граф и c: E(G) → R+. Тогда

метрическое замыкание (G, c) может быть вычислено за время O(n3).

Слайд 38 Задача «Минимальный усредненный Цикл»

Дано: орграф G, веса c:

Задача «Минимальный усредненный Цикл»Дано: орграф G, веса c: E(G) → R.Найти

E(G) → R.
Найти цикл C, усредненный вес которого c(E(C))/|E(C)|

минимален, или показать что G ― ациклический.

Слайд 39 Как решать?
Задача «Минимальный усредненный Цикл» может быть решена

Как решать?Задача «Минимальный усредненный Цикл» может быть решена динамическим программированием.Можно рассматривать

динамическим программированием.
Можно рассматривать только сильно связные графы.
Достаточно существования одной

вершины из которой достижимы другие.

Слайд 40 Теорема Карпа
Теорема 5.12 (Karp [1978])

Пусть G ― орграф

Теорема КарпаТеорема 5.12 (Karp [1978])Пусть G ― орграф с весами c:

с весами c: E(G) → R. Пусть s ∈V(G)

так,
что каждая вершина достижима из s. Для x ∈V(G) и k ∈ Z+
Пусть

будет последовательность дуг минимального веса из s в
x длины k (и ∞, если не существует). Пусть μ(G) ― значение
минимального усредненного цикла в G. Тогда

Слайд 41 Идея доказательства
Докажем, что если μ(G) = 0 то

Пусть

Идея доказательстваДокажем, что если μ(G) = 0 тоПусть G ― орграф

G ― орграф с μ(G) = 0. В G

нет отрицательных циклов. Для x ∈ V(G), пусть l(x) длина кратчайшего s-x-пути. Так как c ― консервативны, то

Слайд 42 Доказательство
Покажем, что существует такое x, что Fn(x) =

l(x).
μ(G) = 0 ⇒ существует цикл C нулевого веса.
Пусть

w ∈ C и P кратчайший s-w-путь.

n раз

Слайд 43 Алгоритм «Минимальный усредненный Цикл»
Input: Орграф G, веса c:

Алгоритм «Минимальный усредненный Цикл»Input: Орграф G, веса c: E(G) → R.

E(G) → R.
Output: Цикл C с минимальным усредненным

весом или информация, что G ― ациклический.
Добавим вершину s и ребро (s,x) с c((s,x))=0 для всех x ∈ V(G).
Set n:=|V(G)|, F0(s):=0 и F0(x):=∞ для всех x ∈ V(G)\{s}.
For k := 1 to n do:
For всех x ∈ V(G) do: Fk(x):=∞.
For всех (w, x) ∈ δ−(x) do:
If Fk−1(w)+ c((w,x)) < Fk(x) then:
Set Fk(x) := Fk−1(w)+ c((w,x)) и pk(x):=w.
If Fn(x)=∞ для всех x ∈ V(G) then stop (G ― ациклический).
Пусть x ― вершина:
минимален.

6. Пусть C ― любой цикл, заданный ребрами
pn(x), pn−1 (pn(x)),…