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

Теорема 17.12. Пусть S - множество заказов равной длительности со сроками, аХ - семейство независимых множеств заказов. Тогда пара (S,X) является матроидом.

Доказательство. Очевидно, каждое подмножество независимого множества также независимо, и остаётся проверить выполнение свойства замены. Пусть А и В - независимые множества, причём \В\ > А. Будем сравнивать числа Nt(B) и Nt(A) при различных t. При t = п первое число больше; уменьшая t, дождёмся момента, когда они сравняются, и назовём его к (если этого не произойдет до самого конца, считаем к = 0). При этом Nk(A) = Nk(B) (если к > 0) и Nk+i(B) > Nk+i(A). Следовательно, есть хотя бы один заказ х £ В \ А со срокомПоложим А = A U {ж}. Если

t к, то Nt(A) = Nt(A) t в силу независимости множества А; если t > к, то Nt(A) = Nt(A)-\-l Nt(B) f в силу независимости множества В; стало быть, множество А независимо по лемме 17.11, и для пары (S,X) выполнено свойство замены. Всё доказано. □

Из доказанной теоремы следует, что для нахождения оптимального множества А независимых заказов можно воспользоваться жадным алгоритмом, а затем составить расписание, начинающееся с заказов из множества А, расставленных в порядке возрастания сроков - это и будет решением задачи о расписании. Если пользоваться алгоритмом Greedy, то время работы будет О (га2), так как в процессе работы этого алгоритма надо сделать га проверок независимости множества, и каждая такая проверка требует О (га) операций (упр. 17.5-2). Более быстрый алгоритм приведён в задаче 17-3.

На рис. 17.7 приведён пример задачи о расписании. Жадный алгоритм отбирает заказы 1, 2, 3 и 4, затем отвергает заказы 5 и 6 и отбирает заказ 7. Оптимальное расписание:

(2,4,1,3,7,5,6).

Сумма штрафов равна w$ + wq = 50.

Упражнения

17.5-1 Решите задачу о расписании для семи заказов, в которой сроки те же, что на рис. 17.7, но каждый штраф w{ заменён на 80 - wt.

Задачи к главе 17

355

Заказ

Рис. 17.7 Пример задачи о расписании для заказов равной длительности с единственным исполнителем, сроками и штрафами.

17.5-2 Как, используя условие (2) из леммы 17.11, выяснить за время 0(А), будет ли данное множество заказов А независимым?

Задачи

17-1 Сдача с доллара

Пусть требуется набрать сумму в п центов, используя наименьшее количество монет.

а.Опишите жадный алгоритм, набирающий п центов с помощью монет достоинством в 25, 10, 5 и 1 цент. [Именно такие монеты используются в США.] Докажите, что алгоритм находит оптимальное решение.

б.Пусть в нашем распоряжении имеются монеты достоинством с0, с1,..., ск центов, где с > 1 и fc 1 - целые числа. Докажите, что жадный алгоритм даст в этом случае оптимальное решение.

е. Приведите пример набора типов монет, для которого жадный алгоритм оптимума не даст.

17-2 Ацикличные подграфы

а.Пусть G = (V, Е) - неориентированный граф. Покажите, что пара (Е,1), где А £ I тогда и только тогда, когда множество А ациклично, является матроидом.

б.Матрицей инцидентности (incidence matrix) неориентированного графа G = (V, Е) называется \V\ X -матрица М, в которой Mve равно единице, если вершина v инцидентна ребру е, и нулю в противном случае. (Столбец, соответствующий ребру, содержит ровно две единицы, соответствующие концам этого ребра.) Докажите, что набор столбцов этой матрицы линейно независим [над полем вычетов из двух элементов] тогда и только тогда, когда соответствующий набор ребер ацикличен. Пользуясь результатом упражнения 17.4-2, докажите теперь другим способом, что пара (Е,1) является матроидом.

е. Пусть в неориентированном графе G = (V, Е) для каждого ребра е £ Е задан неотрицательный вес w(e). Разработайте эффективный алгоритм для нахождения ацикличного подмноже-

ства множества Е с наибольшей суммой весов рёбер.

г.Пусть G = (V, Е) - ориентированный граф, и пусть X - семейство всех ацикличных подмножеств множества рёбер (в данном случае слово «ацикличный» означает «не содержащий ориентированных циклов»). Приведите пример, когда пара (Е,Х) не будет матроидом. Какое из условий в определении матроида будет нарушено?

д.Матрица инцидентности для ориентированного графа G = (V, Е) - это \V\ X £-матрица М, в которой Mve равно -1, если вершина v является началом ребра е, равно 1, если вершина v является концом ребра е, и равно нулю в остальных случаях. Докажите, что множество рёбер графа, соответствующее линейно независимому (над К.) набору столбцов матрицы инцидентности, не содержит ориентированного цикла.

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

17-3 Ещё о расписаниях

Рассмотрим следующий алгоритм для решения задачи из раздела 17.5 (оптимальное расписание для заказов равной длительности с единственным исполнителем, сроками и штрафами). Будем перебирать заказы в порядке убывания штрафов и заполнять расписание так: если для заказа номер j существует хотя бы одно свободное место в расписании, позволяющее выполнить его не позднее требуемого срока dj, то поставим его на самое позднее из таких мест; в противном случае поставим его на самое позднее из свободных мест.

а.Докажите, что этот алгоритм даёт оптимум.

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

Замечания

Дополнительные сведения о жадных алгоритмах и матроидах можно найти у Лоулера [132] или Пападимитриу и Стайглица [154].

Первой работой по комбинаторной оптимизации, содержащей жадный алгоритм, была работа Эдмондса [62], датированная 1971 годом, хотя само понятие матроида было введено в 1935 году в