Алгоритм фронта волны - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Алгоритм фронта волны. Доклад-сообщение содержит 12 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

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

Слайд 1

Описание слайда:

Лекция 2. Алгоритм фронта волны Иванилова Т.Н.

Слайд 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}= ={v1,v2,v3,v4,v5} \{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

Слайд 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