Алгоритм фронта волны

Сентябрь 12, 2022

Главная
Математика
Алгоритм фронта волны

Содержание

2. Поиск путей (маршрутов) с минимальным числом дуг (ребер) Путь (маршрут) в орграфе D (графе G) из
3. Алгоритм фронта волны ( нахождения минимального пути в орграфе D) Рассмотрим орграф D = (V, X),
4. Шаг 1. Помечаем v индексом 0. Помечаем вершину, принадлежащую образу v индексом 1, множество вершин с
5. Шаг 3. IF w ∉ FWk(v), THEN переход к шагу 4. ELSE, существует путь из v
6. Шаг 4. 1) Помечаем индексом (k+1) все непомеченные вершины, которые принадлежат образу множества вершин с индексом
7. Замечания Множество FWk(v) в алгоритме называется фронтом волны k-го уровня. Вершины w1 w2 … wk-1 могут
8. Пример Найти минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности A.
10. Прямой ход алгоритма. Определение фронтов волны. FW1(v1)={v4,v5}; v6 ∉ FW1(v1) FW2(v1)=D(FW1(v1))\{v1,v4,v5}= ={v1,v2,v3,v4,v5} \{v1,v4,v5}= ={v2,v3}; v6 ∉
11. Обратный ход алгоритма. Нахождение вершин минимального пути. Нахождение вершин ведется от последней к первой. FW2 (v1)
13. Скачать презентацию

Слайд 2

Поиск путей (маршрутов) с минимальным числом дуг (ребер)
Путь (маршрут) в орграфе

D (графе G) из v в w (v ≠ w) называется минимальным, если он имеет минимальную длину среди всех путей D (маршрутов G) из v в w.
Теорема 3.3
Любой минимальный путь (маршрут) является простой цепью

Слайд 3

Алгоритм фронта волны ( нахождения минимального пути в орграфе D)
Рассмотрим орграф D

= (V, X), n ≠ 2. И пусть заданы вершины v и w, причем v ≠ w.
Обозначим:
D(v) = {w∈V | (v, w) ∈ X} – образ v.
D -1(v) = {w∈V | (w, v) ∈ X} – прообраз v.

Слайд 4

Шаг 1. Помечаем v индексом 0. Помечаем вершину, принадлежащую образу v

индексом 1, множество вершин с индексом 1 обозначим FW1(v).
Полагаем k = 1.
Шаг 2. IF FWk(v) = ∅ или k = n-1, w∉ FWk(v), THEN w не достижима из v и конец алгоритма.
ELSE

Слайд 5

Шаг 3. IF w ∉ FWk(v), THEN переход к шагу 4.
ELSE,

существует путь из v в w длиной k, и этот путь является минимальным.
Последовательность v w1 w2 … wk-1 w – искомый минимальный путь.
Где wk-1 ∈ FWk-1(v) ∩ D-1(w)
wk-2 ∈ FWk-2(v) ∩ D-1(wk-1)
…………………………….
w1 ∈ FW1(v) ∩ D-1(w2)
конец алгоритма.

Слайд 6

Шаг 4. 1) Помечаем индексом (k+1) все непомеченные вершины, которые принадлежат

образу множества вершин с индексом k.
Множество вершин с индексом (k+1) обозначаем FWk+1(v).
2) k: = k+1
3) переход к шагу 2.

Слайд 7

Замечания
Множество FWk(v) в алгоритме называется фронтом волны k-го уровня.
Вершины w1 w2

… wk-1 могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.

Слайд 8

Пример
Найти минимальный путь из v1 в v6 в орграфе D, заданном

матрицей смежности A.

Слайд 9

Слайд 10

$Прямой ход алгоритма. Определение фронтов волны. FW1(v1)={v4,v5}; v6 ∉ FW1(v1) FW2(v1)=D(FW1(v1))\{v1,v4,v5}=$

Прямой ход алгоритма. Определение фронтов волны.
FW1(v1)={v4,v5}; v6 ∉ FW1(v1)
FW2(v1)=D(FW1(v1))\{v1,v4,v5}= ={v1,v2,v3,v4,v5} \{v1,v4,v5}=

={v2,v3}; v6 ∉ FW2(v1)
FW3(v1)=D(FW2(v1))\{v1,v4,v5,v2,v3}={v1,v2,v4,v5,v6} \{v1,v4,v5,v2,v3}={v6};
v6∈FW3(v1), значит существует путь из v1 в v6 длины 3 и этот путь является минимальным.

Слайд 11

Обратный ход алгоритма. Нахождение вершин минимального пути.
Нахождение вершин ведется от последней

к первой.
FW2 (v1) ∩ D-1(v6) = {v2,v3}∩{v2,v3} = {v2,v3}
Выберем любую вершину из найденного множества, например v3 –это предпоследняя вершина минимального пути.
Определим предыдущую вершину:
FW1(v1)∩D-1(v3)={v4,v5}∩{v4,v5,v6}={v4,v5}
Выберем любую вершину из найденного множества, например v5.
Тогда минимальный путь v1,v5,v3,v6

Алгоритм фронта волны

Содержание

Поиск путей (маршрутов) с минимальным числом дуг (ребер)Путь (маршрут) в орграфе

Алгоритм фронта волны ( нахождения минимального пути в орграфе D)Рассмотрим орграф D

Шаг 1. Помечаем v индексом 0. Помечаем вершину, принадлежащую образу v

Шаг 3. IF w ∉ FWk(v), THEN переход к шагу 4.ELSE,

Шаг 4. 1) Помечаем индексом (k+1) все непомеченные вершины, которые принадлежат

ЗамечанияМножество FWk(v) в алгоритме называется фронтом волны k-го уровня.Вершины w1 w2

ПримерНайти минимальный путь из v1 в v6 в орграфе D, заданном

Прямой ход алгоритма. Определение фронтов волны.FW1(v1)={v4,v5}; v6 ∉ FW1(v1)FW2(v1)=D(FW1(v1))\{v1,v4,v5}= ={v1,v2,v3,v4,v5} \{v1,v4,v5}=

Обратный ход алгоритма. Нахождение вершин минимального пути.Нахождение вершин ведется от последней

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