🗊Презентация Алгоритм фронта волны

Категория: Математика
Нажмите для полного просмотра!
Алгоритм фронта волны, слайд №1Алгоритм фронта волны, слайд №2Алгоритм фронта волны, слайд №3Алгоритм фронта волны, слайд №4Алгоритм фронта волны, слайд №5Алгоритм фронта волны, слайд №6Алгоритм фронта волны, слайд №7Алгоритм фронта волны, слайд №8Алгоритм фронта волны, слайд №9Алгоритм фронта волны, слайд №10Алгоритм фронта волны, слайд №11Алгоритм фронта волны, слайд №12
Скачать
Вы можете ознакомиться и скачать презентацию на тему Алгоритм фронта волны. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1


Лекция 2. Алгоритм фронта волны Иванилова Т.Н.
Описание слайда:
Лекция 2. Алгоритм фронта волны Иванилова Т.Н.

Слайд 2


Поиск путей (маршрутов) с минимальным числом дуг (ребер) Путь (маршрут) в орграфе D (графе G) из v в w (v ≠ w) называется минимальным, если он имеет минимальную длину среди всех путей D (маршрутов G) из v в w. Теорема 3.3 Любой минимальный путь (маршрут) является простой цепью
Описание слайда:
Поиск путей (маршрутов) с минимальным числом дуг (ребер) Путь (маршрут) в орграфе 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.
Описание слайда:
Алгоритм фронта волны ( нахождения минимального пути в орграфе 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
Описание слайда:
Шаг 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) конец алгоритма.
Описание слайда:
Шаг 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.
Описание слайда:
Шаг 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.
Описание слайда:
Замечания Множество FWk(v) в алгоритме называется фронтом волны k-го уровня. Вершины w1 w2 … wk-1 могут быть выделены неоднозначно. Эта неоднозначность соответствует случаям, когда существует несколько различных минимальных путей из v в w.

Слайд 8


Пример Найти минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности A.
Описание слайда:
Пример Найти минимальный путь из v1 в v6 в орграфе D, заданном матрицей смежности A.

Слайд 9


Алгоритм фронта волны, слайд №9
Описание слайда:

Слайд 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}; v6FW3(v1), значит существует путь из v1 в v6 длины 3 и этот путь является минимальным.
Описание слайда:
Прямой ход алгоритма. Определение фронтов волны. 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
Описание слайда:
Обратный ход алгоритма. Нахождение вершин минимального пути. Нахождение вершин ведется от последней к первой. 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
Описание слайда:
Так как результатом 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

Скачать

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