Графы. Основные понятия | Некоторые задачи (11_68_pol) (68 часов в уч. год)

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


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



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

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

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

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

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

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

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

Задачи


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


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

Задача 3. Бродячий торговец должен посетить N городов по одному разу и вернуться в город, откуда он начал путешествие. Известны расстояния между городами (или стоимость переезда из одного города в другой). В каком порядке нужно посещать города, чтобы суммарная длина пути (или стоимость) оказалась наименьшей?

Эта задача оказалась одной из самых сложных задач оптимизации. По сей день известно только одно надёжное решение — полный перебор вариантов, число которых равно факториалу значения N - 1. Это число с увеличением N растёт очень быстро, быстрее, чем любая степень N. Уже для N = 20 такое решение требует огромного времени вычислений: компьютер, проверяющий 1000 вариантов в секунду, будет решать задачу «в лоб» около четырёх миллионов лет. Поэтому математики прилагали большие усилия для того, чтобы сократить перебор — не рассматривать те варианты, которые заведомо не дают лучших результатов, чем уже полученные. В реальных ситуациях нередко оказываются полезными приближённые решения, которые не гарантируют точного оптимального решения, но позволяют получить приемлемый вариант.

Приведём формулировки ещё некоторых задач, которые решаются с помощью теории графов. Алгоритмы их решения вы можете найти в литературе или в Интернете.

Задача 4 (о максимальном потоке). Есть система труб, которые имеют соединения в N узлах. Один узел S является источником, ещё один Т — стоком. Известны пропускные способности каждой трубы. Надо найти наибольший поток от источника к стоку.

Задача 5. Имеются N населённых пунктов, в каждом из которых живут pi школьников (i = 1, ..., N). В каком пункте нужно разместить школу, чтобы общее расстояние, проходимое всеми учениками по дороге в школу, было минимальным?

Задача 6 (о наибольшем паросочетании). Есть М мужчин и N женщин. Каждый мужчина указывает несколько женщин (от О до N), на которых он согласен жениться. Каждая женщина указывает несколько мужчин (от 0 до М), за которых она согласна выйти замуж. Требуется заключить наибольшее количество моногамных браков.

Следующая страница Вопросы и задания



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







Наверх