Урок по теме "Жадные алгоритмы (задача Прима-Крускала)"
план-конспект урока по информатике и икт (11 класс)

Тема урока

Жадные алгоритмы (задача Прима-Крускала)

Тип урока

Урок решения частных задач с применением открытого способа

Цель урока

Разобрать алгоритм Крускала для поиска в графе остовного связанного дерева минимального веса

Планируемый

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

в том числе

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

Предметные        

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

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

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

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

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

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

Личностные

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

Основные понятия

• понятия «жадный» алгоритм, минимальное остовное дерево, алгоритм Прима-Крускала;
• программирование «жадного» алгоритма;
• граф, ребро, дуга, дерево, цикл.

Межпредметные связи

 Экономика, математика

Ресурсы

интерактивная доска, мультимедийный проектор, ЭОР для интерактивной доски,   тестовые задания на ПК, приложения.

Этапы урока

Формируемые УУД

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

Деятельность учащегося

Оргмомент

личностные

Приветствие

Настраиваются на урок

Целеполагание и мотивация

регулятивные

Прежде, чем мы начнем наш урок, хочу напомнить слова выдающегося немецкого философа и драматурга Г.Э.Лессинга «Спорьте, заблуждайтесь, ошибайтесь, но ради бога, размышляйте, и хотя и криво, да сами».

Я бы хотела, чтобы вы об этом помнили, не смущались, если что-то сразу не получится.

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

регулятивные

Давайте вспомним, с какими основными понятиями и определениями вы познакомились при изучении темы «Графы».  Для этого предлагаю выполнить тест.

Пока идет выполнение теста, мы послушаем небольшое сообщение о семи мостах Кенигсберга. (Приложение 2)

Если учесть, что Эйлер родился в самом начале XVIII века (1707 г.), то конечно можно сделать вывод о том, что уже в те времена существовала теория графов . В настоящее время существует целый раздел науки о  Эйлеровых графах, циклах и цепях.

Итак, закончили выполнять тест, посмотрим на доску и выполним задание: на доске представлены три графа. Вам необходимо определить виды этих графов.

(неориентированный, орграф, взвешенный)

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

(Ответ: 12)

Двое обучающихся выполняют тест. (Приложение 1)

Слушают выступление.

Выполняют задания на интерактивной доске.

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

регулятивные

Задача. Предложите способ нахождения кратчайшего маршрута из города А в город F, если известна схема дорог между несколькими городами и расстояния между ними (дороги не прямые, поэтому неравенство треугольника может нарушаться).

Первая мысль – это конечно выбор кратчайших маршрутов до ближайшего города, в котором мы еще не были. Это путь А-С-Е-D-F=9. Какой алгоритм мы применили?

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

Итак, применяя тот же алгоритм, мы пришли к выводу, что кратчайший путь равен 10.

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

Запишем тему урока с небольшой поправкой: «Жадные алгоритмы (задача Прима-Крускала)»

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

Итак, еще раз о решенных задачах: обе ли они дают оптимальное решение?

Какой вывод мы можем сделать о использовании жадного алгоритма при нахождении кратчайшего маршрута?

Однако есть такие задачи, в которых жадный алгоритм приводит к правильному решению. Одна из таких задач (ее называют задачей Прима-Крускала) формулируется так: Между какими городами нужно проложить линии связи, чтобы все города были связаны в одну систему и общая длина линий связи была наименьшей? (Приложение 3)

В теории графов эта задача называется задачей построения минимального остовного дерева, т.е. дерева связывающего все вершины. Остовное дерево для связного графа с N вершинами имеет N-1 ребро.

Рассмотрим жадный алгоритм решения этой задачи предложенный Крускалом:

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

Здесь такая последовательность добавления ребер: CE, DF, AB, EF, AC. После добавления ребра EF, следующее минимальное ребро DE, но оно образует цикл с ребрами DF и EF, поэтому не включено в дерево.

Предположения детей.

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

А-В-D-F=10

Предположения детей (Алгоритм нахождения кратчайшего расстояния между вершинами)

В экономике для достижения максимальной прибыли при наименьших затратах.

Нет, во второй задаче есть более короткий маршрут А-С-Е-F-7.

Жадный алгоритм не всегда дает оптимальное решение.

Физкультминутка (Приложение 4)

Выполняют  Аутомануальный комплекс

Построение проекта выхода из затруднения («открытие» детьми нового знания

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

коммуникативные

Познавательные

При программировании этого алгоритма возникает вопрос: как определить, что ребро еще не включено в дерево и не образует цикла в нем? Существует очень красивое решение этой проблемы, основанное на «раскраске» вершин.

Сначала все вершины раскрашиваются в разные цвета (т.е. им присваиваются разные числовые коды):

for i:=1 to N do col[i]:= i;

N – количество вершин;

сol -   целочисленный массив с индексами от 1 до N.

В цикле  N-1 раз (столько ребер нужно включить в дерево) выполняем следующие операции:

• ищем ребро минимальной длины среди всех рёбер, концы которых окрашены в разные цвета;
• найденное ребро (iMin,jMin) добавляется в список выбранных, и все вершины, имеющие цвет col[jMin], перекрашиваются в цвет col[iMin].

Фрагменты программы:

{Данные}

const N = 6;

var   { весовая матрица } 

    W: array[1..N,1..N] of integer;

      { цвета вершин } 

    col: array[1..N] of integer;

      { номера вершин для выбранных ребер } 

    ostov: array[1..N-1,1..2] of integer;

    i, j, k, iMin, jMin, min: integer;

{Вывод результата – ребер из массива  ostov }

for i:=1 to N-1 do

  writeln('(', ostov[i,1], ',',

               ostov[i,2], ')');        

{Основной цикл программы}

for k:= 1 to N-1 do begin

    { поиск ребра с минимальным весом }

  min:= MaxInt;

{ MaxInt – константа для максимального значения типа  Integer (32767) }

  for i:= 1 to N do

    for j:= 1 to N do

      if (col[i] <> col[j]) and

         (W[i,j] < min) then begin

        iMin:= i; jMin:= j; min:= W[i,j]

      end;   { добавление ребра в список выбранных}

  ostov[k,1]:= iMin;

  ostov[k,2]:= jMin;   c:= col[jMin];

    { перекрашивание вершин }

for i:= 1 to N do

    if col[i] =  c then

      col[i]:= col[iMin]

end;

Здесь:

W – целочисленная матрица размером NxN (индексы строк и столбцов начинаются с 1);

ostov – целочисленный массив из N-1 строк и двух столбцов для хранения выбранных ребер (для каждого ребра хранятся номера двух вершин, которое оно соединяет).

Слушают учителя

Комментарии в фигурных скобках должны давать учащиеся.

закрепление

познавательные

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

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

Ответ:

Самостоятельно:   (Приложение 5)

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

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

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

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

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

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

Ответ:

С графами связаны некоторые классические задачи. Самая известная из них – задача коммивояжёра.

Коммивояжёр (фр. commis voyageur) — бродячий торговец. Задача коммивояжёра — важная задача транспортной логистики, отрасли, занимающейся планированием транспортных перевозок. Коммивояжёру, чтобы распродать нужные и не очень нужные в хозяйстве товары, следует объехать n пунктов и в конце концов вернуться в исходный пункт. Требуется определить наиболее выгодный маршрут объезда. В качестве меры выгодности маршрута (точнее говоря, невыгодности) может служить суммарное время в пути, суммарная стоимость дороги, или, в простейшем случае, длина маршрута. 

Выполняют задание

Сообщение учащегося, владеющего навыками решения задачи.

(Приложение 6)

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

§ 44 стр. 109-112, № 2 стр. 119

Дополнительно: сформулируйте критерий минимальности остова.

(Ответ: Критерий минимальности остова: остов является минимальным тогда и только тогда, когда для любого ребра, не принадлежащего остову, цикл, образуемый этим ребром при добавлении к остову, не содержит рёбер тяжелее этого ребра. В самом деле, если для какого-то ребра оказалось, что оно легче некоторых рёбер образуемого цикла, то можно получить остов с меньшим весом (добавив это ребро в остов, и удалив самое тяжелое ребро из цикла). Если же это условие не выполнилось ни для одного ребра, то все эти рёбра не улучшают вес остова при их добавлении.)

записывают домашнее задание

Включение в систему знаний и повторение.

Рефлексия.

коммуникативные

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

Предлагаю устно закончить следующие предложения.

"На сегодняшнем уроке я понял, я узнал, я разобрался…";

 "Я похвалил бы себя…";

  "После урока мне захотелось…";

  "Сегодня мне удалось…";

 "Я сумел…";

"Было интересно…";

"Было трудно…";

"Я понял, что…";

"Теперь я могу…";

"Я научился…".

Закончить наш урок хочу словами Шарля де Голля, французского генерала второй мировой войны и выдающегося политика: "Всегда выбирайте самый трудный путь, на нем вы не встретите конкурентов!".

Ответы детей