Правильность алгоритма

Правильность алгоритма. Не для всех задач жадный алгоритм дает оптимальное решение, но для нашей дает. Убедимся в этом. Теорема 1. Алгоритм Greedy-Activity- Selector дает набор из наибольшего возможного количества совместных заявок.

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

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

Рассуждая по индукции, получаем, что, делая на каждом шаге жадный выбор, мы придем к оптимальному решению. i si f i 1 1 4 2 3 5 2 13 0 6 3 14 5 7 4 15 3 8 5 1 46 5 9 6 1 47 6 10 7 1 48 8 11 8 1 49 8 12 9 1 4 810 2 13 10 1 4 811 12 14 11 1 4 8 1 4 8 11 время 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 Рис. 1. Работа алгоритма Greedy-Activity-Selector для 11 заявок.

Каждая строка на рисунке соответствует одному проходу цикла в строках 4-7. Серые заявки уже включены в А, белая сейчас рассматривается. Если левый конец белого прямоугольника левее правого конца правого серого стрелка идет влево, то заявка отвергается. В противном случае она добавляется к А. 3.