Задача на кратчайший путь

Содержание

Слайд 2

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

Задача «Кратчайший путь»

Дано: Орграф G, веса c: E(G) → R и

две вершины s, t ∈V(G) .
Найти s-t-путь минимального веса.
Слайд 3

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

Консервативные веса

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

→ R . Функция c называется консервативной если не существует цикла отрицательного веса.
Слайд 4

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

Принцип оптимальности Белмана

Предложение 5.2
Дан орграф 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) + c(e)

Доказательство

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

w∉Q, то Q + e короче, чем P.
Противоречие ⇒ w ∈ Q.
Слайд 6

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

Доказательство (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).
Противоречие.

s

v

w

Q

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 с произвольными весами c: E(G)

Упражнение 7.1

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

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

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

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

Input: Орграф G, веса c: E(G) → 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]) Алгоритм Дейкстры находит оптимальное

Алгоритм Дейкстры (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+ и

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

Input: Орграф G, веса c: E(G) → 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.
Слайд 13

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

a) Для всех v ∈ R и всех 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) ― длина кратчайшего s-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) ― длина кратчайшего s-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]) Алгоритм Дейкстры находит оптимальное решение

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

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

за O(n2) элементарных операций (n = |V(G)|).
Слайд 17

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

Алгоритм Мура-Беллмана-Форда

Input: Орграф G, консервативные веса c: 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 [1956]) Алгоритм

Алгоритм Мура-Беллмана-Форда(2)

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

находит оптимальное решение за O(nm) операций.
Слайд 19

Скетч доказательства На каждой итерации алгоритма пусть R := {v∈ V(G):

Скетч доказательства

На каждой итерации алгоритма пусть 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

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 имеет отрицательный суммарный вес.

x

y

v

w

Слайд 22

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

c) Если функция весов c консервативная, то (R, 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-путь с не более чем k дугами

Индукция

Пусть P кратчайший s-x-путь с не более чем 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]) Алгоритм

Алгоритм Мура-Беллмана-Форда

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

находит оптимальное решение за O(nm) операций.
Покажем, что этот алгоритм также может быть использован для проверки есть ли в орграфе циклы отрицательного веса.
Попутно определим полезное понятие допустимого потенциала, введенное Эдмондсом и Карпом [1972].
Слайд 25

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

Допустимый потенциал

Определение 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 ― орграф с весами

Допустимый потенциал (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)

Допустимый потенциал

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

E(G) → R. Алгоритм Мура-Беллмана-Форда за время O(nm) либо находит допустимый потенциал, либо отрицательный цикл.
Слайд 29

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

Задача «Все Пары Кратчайших путей»

Дано: орграф 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) = {1,...,n} и консервативные

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

Input: Орграф G с V(G) = {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

Шаг 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

j

i

k

pjk

Слайд 33

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

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

за время O(n3).
Слайд 34

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

Идея доказательства

Пусть алгоритм использовал во внешнем цикле (For) вершины 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 + 1

j=j0+1

i

k

{1, 2, …, j0}

Для любых i

и k при выполнения шага 2
для j = j0 + 1: lik заменяется на lij + ljk ,
если lik > lij + ljk .

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

Q

P

Слайд 36

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

Метрическое замыкание

Определение 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: E(G) →

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

цикл C, усредненный вес которого c(E(C))/|E(C)| минимален, или показать что G ― ациклический.
Слайд 39

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

Как решать?

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

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

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

Теорема Карпа

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

E(G) → R. Пусть s ∈V(G) так,
что каждая вершина достижима из s. Для x ∈V(G) и k ∈ Z+
Пусть
будет последовательность дуг минимального веса из s в
x длины k (и ∞, если не существует). Пусть μ(G) ― значение
минимального усредненного цикла в G. Тогда
Слайд 41

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

Идея доказательства

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

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

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

Доказательство

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

⇒ существует цикл C нулевого веса.
Пусть w ∈ C и P кратчайший s-w-путь.

P

С

n раз

w

x

s

Слайд 43

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

Алгоритм «Минимальный усредненный Цикл»

Input: Орграф G, веса c: 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)),…
Слайд 44

Алгоритм «Минимальный усредненный Цикл» Следствие 5.13(Karp [1978]) Алгоритм «Минимальный усредненный Цикл» находит решение за время O(n(m+n)).

Алгоритм «Минимальный усредненный Цикл»

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

находит решение за время O(n(m+n)).
Слайд 45

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

Упражнение 7.2

Дан орграф G с произвольными весами c: E(G) → R

и s, t ∈ V(G).
Найти s-t-путь у которого вес максимального ребра минимален.
Слайд 46

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

Упражнение 7.3

Дан орграф G с s, t ∈ V(G). Пусть для

каждого ребра e∈ E(G) задано число r(e) (надежность ребра e), 0 ≤ r(e) ≤ 1. Надежность пути P определяется произведением надежности его ребер.
Найти s-t-путь максимальной надежности.
Слайд 47

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

Упражнение 7.4

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

R . Пусть s, t ∈ V(G), так что t достижимо из s.
Доказать, что минимум длины s-t-пути в G равен максимуму величины π(t) − π(s), где π ― допустимый потенциал.
- Предыдущая
Физические явления
Следующая -
Ультразвуковой дальномер

Похожие презентации

Алгоритм решения задач Прочитайте несколько раз Определите известные данные Определите что требуется найти. Определите скр
Правила дифференцирования
Масса тела и ее измерение
Несобственные интегралы
Перпендикулярность прямой и плоскости
Подготовительный этап к изучению нумерации в программе Дорофеева Г.В
Арифметический квадратный корень. Задания для устного счета. 8 класс
Загадки пирамиды
Решение задач по теме «Перпендикулярность прямой и плоскости» (10 класс)
Возведение в квадрат суммы и разности двух выражений
Треугольники. Пространственные фигуры, состоящие из треугольников
Способы решения квадратных уравнений. 8 класс
История геометрии. 2 часть. Геометрические фигуры вокруг
Десятичные и натуральные логарифмы. Формула перехода к другому основанию
Математические модели
Презентация по математике "Старинные единицы измерения" - скачать бесплатно
Математика на палочках
Цікаві задачі з математики
Лог-линейный анализ
Равенство. Неравенство
Задачи на построение с помощью циркуля и линейки
Виды симметрии в архитектуре
Игра-тренажер по математике «Сложение и вычитание в пределах 20»
Параллелограмм, трапеция, прямоугольник, ромб, квадрат
Решение уравнений
Шаровый сегмент
Доля
Письмове додавання і віднімання багатоцифрових чисел
Вы можете прислать нам Вашу презентацию и мы опубликуем ее на сайте.
Обратная связь
Для правообладателей
Email: Нажмите что бы посмотреть