Поиск кратчайших путей в графе. Динамическое программирование

Цель урока

Разобрать известные алгоритмы для поиска кратчайших путей в графе.

Планируемый

результат обучения,

в том числе

формирование УУД

Предметные              

умение находить оптимальное решение при использовании различных алгоритмов;

Метапредметные

Познавательные УУД:  формирование представления о графе как о наглядном средстве представления состава и структуры системы;   формирование представления о способе реализации решения задач оптимизации с помощью различных алгоритмов;

Коммуникативные УУД: организация самостоятельной работы, работы в группе (самостоятельно определять цели, роли, задавать вопросы, вырабатывать решения). Учет разных мнений и стремление к координации различных позиций в сотрудничестве;

Личностные УУД: выработка культуры общения, взаимопомощь обучающихся, формирование интеллектуальной и эмоциональной активности обучающихся, воспитание чувства ответственности за результаты своего труда;

Регулятивные УУД:  определение целей, проблемы в своей деятельности. Выдвижение версии, выбор средства достижения цели. Работа по плану, сверяясь с целью, нахождение и исправление ошибки, в т.ч. самостоятельно.

Личностные

Выработка уважительно-доброжелательных отношений между обучающимися, учет различных мнений, творческое отношение к процессу обучения.

Этапы урока

Деятельность учителя

Орг. момент

Приветствие

Актуализация знаний

Давайте вспомним, с какими основными понятиями и определениями вы познакомились при изучении темы

Вернемся в  10 класс. Мы учились решать задачи на поиск количества путей в графе и анализ информационных моделей. Это задания № 3 и15 в ЕГЭ по информатике. Давайте вспомним, как мы это делали. Для этого  выполним следующие задание:.

постановка цели деятельности (постановка учебной задачи)

Запишем тему урока: « Поиск кратчайших путей в графе»

Виды алгоритмов:

1)     «жадный алгоритм» -  алгоритм состоит в том, чтобы на каждом шаге многоходового процесса выбирать наилучший в данный момент вариант, не думая о том, что впоследствии этот выбор может привести к худшему решению

(алгоритм, который, на каждом шагу принимают локально оптимальное решение, не заботясь о том, что будет дальше)

2)     сформулируйте алгоритм Прима-Крускала - это «жадный» алгоритм, который всегда приводит к правильному решению. В теории графов – это построение минимального основного дерева, т.е. дерева, связывающего все вершины

1.начальное дерево – пустое

     2.на каждом шаге добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла

3)     в чем заключается алгоритм Дейкстра? - алгоритм, нахождения кратчайшего расстояния от одной из вершин графа до всех остальных

Вывод: не всякий алгоритм дает оптимальное решение.

Решим следующую задачу: граф рисую на доске

требуется найти кратчайшее расстояние от 1-й вершины до 6 используя «жадный алгоритм».     

1) Жадный алгоритм             

Жадные алгоритмы – это общее название подхода к решению задач оптимизации. Вопрос: в какой области науки решают задачи по оптимизации?

2)Алгоритм Прима-Крускала

Общая длина равна 33.

 3)

Результат работы алгоритма: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

      Займемся выводом кратчайшего пути. Мы знаем длину пути для каждой вершины, и теперь будем рассматривать вершины с конца. Рассматриваем конечную вершину (в данном случае — вершина 5), и для всех вершин, с которой она связана, находим длину пути, вычитая вес соответствующего ребра из длины пути конечной вершины.
Так, вершина 5 имеет длину пути 20. Она связана с вершинами 6 и 4.
Для вершины 6 получим вес 20 — 9 = 11 (совпал).
Для вершины 4 получим вес 20 — 6 = 14 (не совпал).
Если в результате мы получим значение, которое совпадает с длиной пути рассматриваемой вершины (в данном случае — вершина 6), то именно из нее был осуществлен переход в конечную вершину. Отмечаем эту вершину на искомом пути.
Далее определяем ребро, через которое мы попали в вершину 6. И так пока не дойдем до начала.
Если в результате такого обхода у нас на каком-то шаге совпадут значения для нескольких вершин, то можно взять любую из них — несколько путей будут иметь одинаковую длину.

Реализация построенного проекта

Задание:  Используя алгоритм Прима-Крускала найдите на графе минимальное основное дерево. Является ли оно универсальным?

Ответ (решение не универсально)

Задание: используя алгоритм Дейкстра найдите кратчайшие расстояния между вершиной А и всеми другими вершинами.

Чему равен порядок графа и что это такое? (Ответ: порядок графа – это число вершин, равно 5)

Чему равен размер графа и что это такое (Ответ: размер – это количество дуг или ребер, равно 8)

закрепление

Задание: используя алгоритм Дейкстра, найдите кратчайшие расстояния между вершиной, а всеми другими вершинами. Определите порядок и размер графа.

Ответ:

Порядок – 9, размер – 14

Самостоятельно: используя алгоритм Прима-Крускала, постройте минимальное основное дерево.

Вернемся снова к заданию ЕГЭ и решим его применив алгоритм Дейкстра

Между населёнными пунктами A, B, C, D, E, F построены дороги, протяжённость которых приведена в таблице. Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.

Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).

Задание: используя алгоритм Прима-Крускала найдите на графе минимальное основное дерево.  Является ли оно универсальным?

Ответ: (является)

Используя жадный алгоритм и алгоритм Дейкстра найдите кратчайшее расстояние от А до К. Сделайте вывод.

1) Жадный:  ответ - 69

2) Алгоритм Дейкстра

Задача: имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна? Является ли решение универсальным?

Ответ: (не является)

 Суммарный вес дерева равен 37. Это минимальное остовное дерево не уникально: удалением ребра (c,d) и добавлением ребра (a,b) получается новое минимальное остовное дерево.

Задача: удалите лишние ребра и получите минимальное остовное дерево.

                                                                                            Ответ:

Домашнее задание

Подведем итоги нашего урока. 

1. Сообщение А4, тема: «Использование графов для анализа данных в Интернете» - защита

2. кратчайший путь, порядок графа, размер (16, 16, 21, 16)