3.2. Жадные алгоритмы

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

При каждом повторе жадный алгоритм выбирает «самый привлекательный» вариант. Например, самый большой номинал из доступных монет. В случае с американскими деньгами Change использует номиналы четвертак (25 центов), дайм (10 центов), никель (5 центов) и пенни (1 цент), чтобы выдать сдачу, в данном порядке. Разумеется, мы показывали, как такой «жадный» подход приводит к неправильным результатам при добавлении монет некоторых новых номиналов.

В примере с телефоном «жадная» стратегия состояла бы в том, чтобы идти на звук, пока вы его не найдете. Но есть проблема: между вами и телефоном может оказаться стена (или хрупкая ваза). К сожалению, такие сложности часто возникают и в реальных задачах. Во многих случаях «жадный» подход выглядит естественным и очевидным, но может оказаться неправильным.

В задаче «Бронирование переговорки» вам дается несколько временных отрезков, и нужно выбрать как можно больше отрезков таким образом, чтобы ни один из них не пересекался с другим (отрезки пересекаются, если у них есть общая точка). Название задачи основано на следующей гипотетической ситуации. Представьте, что у вас есть зал для переговоров, и вам присылают заявки на бронирование 11 компаний.

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

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

💡 Остановитесь и подумайте:
Всегда ли это приведет к оптимальному решению?

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

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

💡 Остановитесь и подумайте:
Всегда ли это приведет к оптимальному решению?

Увы, но нет.

💡 Остановитесь и подумайте:
Может, есть и другие «жадные» подходы?

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

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

✒️ Упражнение:
Докажите, что если набор непересекающихся отрезков не содержит чемпионский отрезок, то при замене первого отрезка в этом наборе на чемпионский мы получаем набор непересекающихся отрезков.

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

В нашем примере алгоритм работает следующим образом.

• Выбрать сегмент и отбросить сегменты , , , и .
• Выбрать сегмент и отбросить сегменты и .
• Выбрать сегмент .
• Выбрать сегмент .
• Выбрать сегмент .