Оптимальность для подзадач

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

Примеры

Размен монет

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

Жадный алгоритм решения этой задачи таков. Берётся наибольшее возможное количество монет достоинства : . Таким же образом получаем, сколько нужно монет меньшего номинала, и т. д.

Для данной задачи жадный алгоритм не всегда даёт оптимальное решение. Например, сумму в 24 копейки монетами в 1, 5 и 7 коп. жадный алгоритм разменивает так: 7 коп. — 3 шт., 1 коп. — 3 шт., в то время как правильное решение — 7 коп. — 2 шт., 5 коп. — 2 шт. Тем не менее, на всех реальных монетных системах жадный алгоритм даёт правильный ответ.

Выбор заявок

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

Формулировка № 2. На конференции, чтобы отвести больше времени на неформальное общение, различные секции разнесли по разным аудиториям. Учёный с чрезвычайно широкими интересами хочет посетить несколько докладов, проходящих в разных секциях. Известно начало и конец каждого доклада. Определить, какое максимальное количество докладов можно посетить.

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

Activity-Selector(s,f)

1. length[s]

2.

3.

4. for to n

o do if

then ∪ {i}

§

5. return A

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает ее номер.

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

Доказательство. Заметим, что все заявки отсортированы по неубыванию времени окончания. Заявка номер 1, очевидно, входит в оптимум (если нет, то заменим самую раннюю заявку в оптимуме на нее, от этого хуже не станет). Выкинув все заявки, противоречащие первой, получим исходную задачу с меньшим количеством заявок. Рассуждая по индукции, аналогичным образом приходим к оптимальному решению.