В этом параграфе вы разберёте ещё один вариант задачи с ограниченными ресурсами. Но в отличие от предыдущего примера, где критерий выбора был простым и однозначным, здесь придётся искать более тонкую стратегию: оценивать выгоду на единицу ресурса. Это позволяет использовать жадный алгоритм там, где «просто отсортировать» уже недостаточно. Главная цель задачи — научиться доказывать, что выбранный критерий действительно ведёт к оптимальному решению.
Ключевые вопросы параграфа
- Чем задача «Сбор подписей» отличается от других задач с ограниченными ресурсами?
- Почему стратегия «максимальная прибыль на единицу ресурса» оказывается оптимальной?
- Как корректно оформить и проверить такое решение?
Максимальная выгода при ограниченных ресурсах
На этот раз ваша задача — собрать подписи со всех жильцов дома. Вам известно время, в которое каждый из них будет у себя. Естественно, вам хочется собрать все подписи, заходя в дом минимальное количество раз. Для простоты давайте предположим, что вы, зайдя в дом, собираете подписи сразу со всех жильцов, которые на месте.
В дальнейшем под сегментом будем понимать интервал времени нахождения жильца в доме. Количество жильцов будет соответствовать количеству сегментов.
- Входные данные: Количество сегментов в первой строке — . Каждая из следующих строк содержит два целых числа и (разделены пробелом), которые указывают на координаты границ -го сегмента.
- Выходные данные: Минимальное количество точек на первой строке и координаты точек целыми числами (разделены пробелом) на второй строке. Выводить точки можно в любом порядке. При наличии нескольких наборов точек, можно вывести любой из них.
- Ограничения: ; для всех .
Пример 1
|
Ввод |
Вывод |
|
3 |
1 |
Все три сегмента , , содержат точку с координатами 3.
Пример 2
|
Ввод |
Вывод |
|
4 |
2 |
Второй и третий сегменты содержат точку с координатами , в то время как первый и четвертый содержат точку с координатами . Одной точкой покрыть все сегменты нельзя, так как и не пересекаются. В этом случае есть еще одно верное решение — точки 2 и 5.
Решение
Решение заключается в выявлении сегмента с наименьшим значением правой границы.
Самое маленькое значение границы сегмента: . Мы утверждаем, что существует оптимальное решение, включающее в себя точку . Чтобы доказать это, возьмём оптимальное решение . Оно должно покрывать сегмент , поэтому содержит точку , что приводит к . Если , то наша работа закончена. Иначе . В этом случае мы можем заменить на в .
Понятно, что это не меняет размер решения . Чтобы доказать, что всё ещё является решением, подойдём от противного и предположим, что некий сегмент покрывается , но не покрывается . Это означает и противоречит тому, что — самое маленькое значение правой границы.
Таким образом, мы приходим к следующему алгоритму:
- добавить в решение минимальное значение правой границы ,
- отбросить все сегменты, покрытые ,
- повторить.
1SegmentsCover(segments):
2 points←empty set
3 while segments is not empty:
4 r_m = minimum right endpoint of a segment from segments
5 add r_m points
6 remove segments covered by r_m from the set segments
7 return points
На рисунке ниже показан пример.
Время выполнения составит , где , так как используется не более итераций цикла while (при каждой итерации отбрасывается как минимум один сегмент), и каждая итерация сводится к проверке списка (одним сканированием находится значение , а другим убираются сегменты, покрываемые ).
Этот алгоритм уже достаточно быстрый, чтобы успешно пройти оценку. Однако можно дополнительно сократить время выполнения с до , если отсортировать сегменты от малых до больших значений правой границы и затем просто просканировать список один раз.
Что дальше
Теперь вы умеете применять жадные алгоритмы, когда нужно максимизировать результат при ограниченном ресурсе, используя критерий эффективности на единицу ресурса.
Далее — задача с другим типом цели: теперь ресурс нужно распределить так, чтобы увеличить количество получателей. Вы узнаете, как простая сортировка помогает достичь справедливого распределения и почему жадный подход оказывается удачным и в этой ситуации.
А пока вы не ушли дальше — закрепите материал на практике:
- Отметьте, что урок прочитан, при помощи кнопки ниже.
- Пройдите мини-квиз, чтобы проверить, насколько хорошо вы усвоили тему.
- Перейдите к задачам этого параграфа и потренируйтесь.
- Перед этим — загляните в короткий гайд о том, как работает система проверки.
Хотите обсудить, задать вопрос или не понимаете, почему код не работает? Мы всё предусмотрели — вступайте в сообщество Хендбука! Там студенты помогают друг другу разобраться.
Ключевые выводы параграфа
- Жадный алгоритм может работать не только с абсолютными значениями, но и с относительными критериями, например «выгода на единицу ресурса».
- Оптимальность жадного критерия нужно обосновывать — иначе легко получить неверное решение.
- Работа с вещественными числами требует особой аккуратности в сравнении и реализации.