орграфе D (графе G) из v в w (v ≠
w) называется минимальным, если он имеет минимальную длину среди всех путей D (маршрутов G) из v в w.Теорема 3.3
Любой минимальный путь (маршрут) является простой цепью
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Лекция 2. Алгоритм фронта волны
Содержание
- 1. Лекция 2. Алгоритм фронта волны
- 2. Поиск путей (маршрутов) с минимальным числом дуг
- 3. Алгоритм фронта волны ( нахождения минимального пути
- 4. Шаг 1. Помечаем v индексом 0. Помечаем
- 5. Шаг 3. IF w FWk(v), THEN
- 6. Шаг 4. 1) Помечаем индексом (k+1) все
- 7. ЗамечанияМножество FWk(v) в алгоритме называется фронтом волны
- 8. ПримерНайти минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности A.
- 9. Слайд 9
- 10. Прямой ход алгоритма. Определение фронтов волны.FW1(v1)={v4,v5}; v6
- 11. Обратный ход алгоритма. Нахождение вершин минимального пути.Нахождение
- 12. Так как результатом FWk(v)D-1(w) являются множества, состоящие
- 13. Скачать презентанцию
Поиск путей (маршрутов) с минимальным числом дуг (ребер)Путь (маршрут) в орграфе D (графе G) из v в w (v ≠ w) называется минимальным, если он имеет минимальную длину среди всех путей
Слайды и текст этой презентации
Слайд 2Поиск путей (маршрутов) с минимальным числом дуг (ребер)
Путь (маршрут) в
Теорема 3.3
Любой минимальный путь (маршрут) является простой цепью
Слайд 3Алгоритм фронта волны
( нахождения минимального пути в орграфе D)
Рассмотрим орграф
D = (V, X), n 2. И пусть заданы
вершины v и w, причем v w.Обозначим:
D(v) = {wV | (v, w) X} – образ v.
D -1(v) = {wV | (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.
Слайд 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 FW2(v1)
FW3(v1)=D(FW2(v1))\{v1,v4,v5,v2,v3}={v1,v2,v4,v5,v6} \{v1,v4,v5,v2,v3}={v6};
v6FW3(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
Слайд 12Так как результатом FWk(v)D-1(w) являются множества, состоящие более чем из
одного элемента, то минимальных путей длины k=3 будет несколько. Первый
путь мы определили. Определим следующие.2. Выберем другую вершину из найденного множества – v4.
Тогда минимальный путь v1,v4,v3,v6
3. FW2 (v1) D-1(v6) = {v2,v3}{v2,v3} = {v2,v3} – выберем v2;
FW1(v1)D-1(v2)={v4,v5}{v3,v4,v5,v6}={v4,v5} – выберем v5.
Тогда минимальный путь v1,v5,v2,v6
4. выберем v4. Тогда минимальный путь v1,v4,v2,v6
