Графы. Основные понятия | «Жадные» алгоритмы. Задача 1 (11 кл. 136 ч.)

Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, полный углублённый курс, по 4 часа в неделю)


Уроки 80 - 83
Графы. Основные понятия
(§44. Графы)



Содержание урока

Что такое граф?

«Жадные» алгоритмы. Задача 1

«Жадные» алгоритмы. Задача 2

Кратчайшие маршруты

Некоторые задачи

Вопросы и задания

Задачи


«Жадные» алгоритмы. Задача 1


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

Рис. 6.25

Рис. 6.25

Первая мысль, которая приходит в голову: на каждом шаге выбирать кратчайший маршрут до ближайшего города, в котором мы ещё не были. Для заданной схемы на первом этапе едем в город С (длина 1), далее — в Е (длина 4), затем в D (длина 3) и, наконец, в F (длина 1). Общая длина маршрута равна 9.

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

Для данной схемы «жадный» алгоритм даёт оптимальное решение, но так будет далеко не всегда. Например, для той же задачи с другой схемой (рис. 6.26) «жадный» алгоритм даст маршрут A-B-D-F длиной 10, хотя существует более короткий маршрут A-C-E-F длиной 7.

Рис. 6.26

Рис. 6.26

«Жадный» алгоритм не всегда позволяет получить оптимальное решение.

Однако есть задачи, в которых «жадный» алгоритм всегда приводит к правильному решению. Одна из таких задач (её называют задачей Прима—Крускала в честь Р. Прима и Д. Крускала, которые независимо предложили её в середине XX века) формулируется так.

Следующая страница «Жадные» алгоритмы. Задача 2



Cкачать материалы урока







Наверх