Введение. Задача о составлении расписания

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

Задачи нахождения оптимального значения называются экстремальными, а процесс решения таких задач — оптимизацией. Методы оптимизации — отдельная область математики. Некоторые задачи можно решить не применяя серьёзную математику.

Эта глава посвящена жадным алгоритмам. Их используют для решения экстремальных задач. Жадные алгоритмы состоят из итераций. На каждом шаге они выбирают оптимальное по определённому критерию решение, не заглядывая в будущее. За это они и получили своё название. На самом деле, такое решение может быть глобально не оптимальным.

Обычно жадные алгоритмы работают быстро. Так что если вы нашли для задачи корректное жадное решение, вам повезло.

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

Например, их иногда применяют для поиска приближённого решения NP-полных задач (англ. non-deterministic polynomial). Так называют задачи, которые не могут быть решены за полиномиальное время.

Рассмотрим пример. Учительница Васи снова обратилась к Алле за помощью. На этот раз ей нужно помочь составить расписание.

В школьном кабинете нужно провести как можно больше уроков. Вот список предметов:

Провести все уроки в классе не получится, так как некоторые из них накладываются друг на друга по времени.

Нужно составить такое расписание, в соответствии с которым получится провести как можно больше уроков в классе.

Как отбирать предметы, чтобы получить список с их максимальным количеством?

Есть несколько стратегий решения этой задачи.

Например, выбрать самые короткие отрезки. Кажется, такая стратегия действительно позволит провести в классе больше предметов.

Отсортируем отрезки по этому критерию. Возьмём самый короткий урок и удалим те, которые с ним пересекается. Например, урок химии длится меньше физкультуры, и они пересекаются по времени. Значит, оставим химию в расписании, а физкультуру удалим. Повторим эти действия с остальными тремя уроками.

В результате получим:

Другая идея — отсортировать отрезки по левой границе и придерживаться алгоритма, который мы применили в предыдущей стратегии. То есть в этом случае мы выбираем занятие, которое начинается раньше остальных.

Результат сортировки:

Третий вариант — отсортировать отрезки по правой границе, то есть выбрать предметы, которые заканчиваются раньше всех.

Итоговая расстановка:

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

Сначала самые короткие:

По левой и по правой границе:

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

Разберём ещё один вариант расположения отрезков:

Упорядочивание по началу отрезка даёт нам:

Получаем ответ:

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

В этом случае количество уроков больше.

Упорядочивание по концу отрезка даёт нам:

Итоговая расстановка:

Для приведённых примеров последний алгоритм верно решает задачу. Значит ли это, что он будет корректно работать на всех входных данных?

Докажем его корректность.

Для этого воспользуемся методом математической индукции.

Идея метода математической индукции в следующем. Сначала проверяется истинность утверждения с номером 1 — база индукции, а затем доказывается, что если верно утверждение с номером n, то верно и следующее утверждение с номером n + 1 — индукционный переход.

Вернёмся к алгоритму. Сначала убедимся в том, что оптимальных решений этой задачи может быть несколько. Покажем, что существует оптимальное подмножество отрезков, которое содержит первый отрезок, получившийся при применении этого алгоритма.

Поменяем отрезок с минимальным значением конца на первый, выбранный нами на данном шаге алгоритма. Количество отрезков в результирующем подмножестве не изменится — то есть подмножество останется решением. Это основано на предположении, что функция f(x) оптимального решения на диапазоне от [x;+∞) — невозрастающая. Аргумент функции х — это время, начиная с которого мы ищем решение. Иными словами, если будем сдвигать направо время начала отсчёта, то отрезков больше точно не станет.

Можно сделать вывод, что существует оптимальное подмножество, содержащее первый отрезок. На втором шаге удаляем из множества отрезков первый отрезок и все отрезки, пересекающиеся с первым. Третий шаг — повторяем алгоритм для усечённого множества, в котором снова находим первый отрезок. Таким образом, с помощью метода математической индукции установили, что предложенный жадный алгоритм приводит к одному из оптимальных решений задачи.

Найденный алгоритм поможет Алле выполнить просьбу учительницы. Для этого нужно:

Если следовать этому алгоритму, получится верный ответ.

Рассмотрим подробнее:

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

Вторым шагом нужно найти предмет, который начинается после 9:50 и заканчивается раньше всех таких уроков

Физика не подходит, так как она пересекается с алгеброй. Берём химию.

Физкультура не подходит, так как она начинается раньше, чем заканчивается химия. Берем биологию. Она подходит.

Получилось, что в классе пройдут уроки алгебры, химии и биологии.

Для этой задачи мы смогли найти жадное решение. Так бывает не всегда. Далее вы в этом убедитесь.

А пока что напишите код для решения этой и нескольких похожих задач. Решите задачи A, B и C: https://contest.yandex.ru/contest/18360/enter/