Доказательство. Независимые в S множества, содержащие ж, получаются добавлением элемента ж к независимым в S подмножествам. При этом их веса отличаются ровно на w(x), так что опти-

Теорема 17.10 (правильность жадного алгоритма для матроидов).

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

Доказательство. Пусть М = (S,I) - матроид с весовой функцией w. В силу леммы 17.8 мы можем не принимать во внимание элементы ж £ S, для которых множество {ж} не независимо. Если ж £ S - первый из выбранных алгоритмом элементов, то лемма 17.7 показывает, что существует оптимальное подмножество ACS, содержащее ж. Теперь, согласно лемме 17.9, достаточно найти оптимальное подмножество в матроиде М, полученном из М стягиванием элемента ж (и добавить к нему ж). Дальнейшая работа алгоритма в сущности и представляет собой обработку матро-

[Более формальное рассуждение может быть таким. После любого числа итераций выполнен следующий инвариант цикла: (1) множество А независимо; (2) оптимальное множество можно искать среди множеств, являющихся объединением А с некоторыми из ещё не просмотренных элементов.]

Упражнения

17.4-1 Пусть S - конечное множество, к - натуральное число, Ik - семейство всех подмножеств S, содержащих не более к элементов. Покажите, что (S,Ik) - матроид.

17.4-2* Пусть Т - вещественная матрица, S - множество её столбцов, и подмножество ACS называется независимым, если оно линейно независимо в обычном смысле. Докажите, что получается матроид (называемый матричным, как мы уже говорили).

17.4-3* Пусть (S,I) - матроид. Пусть I - семейство всех таких подмножеств А С S, для которых S \ А содержит некоторое максимальное независимое подмножество ACS. Покажите, что пара (S,Ir) является матроидом. Заметим, что максимальные независимые подмножества (S,Xr) суть дополнения максимальных независимых подмножеств (S,X).

17.4-4* Пусть S = S\ U 5*2 U • • • U Sk - разбиение конечного множества S на непересекающиеся непустые части. Положим X = { А С S : А П Si\ 1 для г = 1, 2,..., к }. Покажите, что пара (S,X) является матроидом.

мальные множества соответствуют оптимальным.

□

ида М.

□

17.4-5 Пусть нам дан взвешенный матроид. Объясните, как надо модифицировать весовую функцию, чтобы свести задачу нахождения максимального независимого подмножества с наименьшим весом к задаче нахождения независимого подмножества с наибольшим весом.

★ 17.5 Задача о расписании

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

Итак, предположим, что имеется конечное множество S, состоящее из заказов (tasks), каждый из которых требует ровно одну единицу времени для своего выполнения. Расписанием (schedule) для S называется перестановка множества S, задающая порядок выполнения заказов: выполнение первого заказа начинается в момент времени 0 и заканчивается в момент 1, выполнение второго заказа начинается в момент времени 1 и заканчивается в момент 2, и т. д.

В задаче о расписании для заказов равной длительности с единственным исполнителем, сроками и штрафами (scheduling unit-time tasks with deadlines and penalties for a single processor) исходными данными являются:

•множество S = { 1, 2,..., п }, элементы которого мы называем заказами;

•последовательность из п целых чисел d\, d2, , dn, называемых сроками (deadlines) (1 dt п для всех г, срок d{ относится к заказу номер г);

•последовательность из п неотрицательных чисел w\, w2, , wn, называемых штрафами (penalties) (если заказ номер г не выполнен ко времени di, взимается штраф гиг-).

Требуется найти расписание для S, при котором сумма штрафов будет наименьшей.

Заказ номер г просрочен (late) для данного расписания, если его выполнение завершается позже момента di, в противном случае заказ считается выполненным в срок (early). Всякое расписание можно, не меняя суммы штрафов, модифицировать таким образом, чтобы все просроченные заказы стояли в нём после выполненных в срок. В самом деле, если просроченный заказ у идёт раньше выполненного в срок заказа ж, то можно поменять их местами в расписании, и статус обоих заказов при этом не изменится.

Более того, каждое расписание можно, не меняя суммы штрафов, представить в каноническом виде (canonical form), а именно, так, чтобы все просроченные заказы стояли после выполненных в срок, а сроки для выполненных в срок заказов шли в неубывающем порядке. В самом деле, как мы видели, можно считать, что все просроченные заказы стоят после выполненных в срок. Если теперь выполнение непросроченных заказов номер г и j завершается в моменты времени к и к + 1 соответственно, но при этом dj < di, то можно поменять заказы местами, и оба по-прежнему не будут просрочены (коль скоро dj к + 1, то и подавно di > dj к + 1; заказу же номер j вообще ничего не грозит, поскольку по новому расписанию его будут выполнять раньше, чем по старому). Конечное число таких обменов приведёт расписание к каноническому виду.

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

Будем говорить, что подмножество ACS является независимым (independent), если для этого множества заказов можно составить расписание, по которому все заказы будут выполнены в срок. Обозначим через X семейство всех независимых подмножеств множества S.

Как выяснить, будет ли данное подмножество ACS независимым? Для каждого t = 1,2,..., га обозначим через Nt(A) количество заказов из множества А, для которых срок не превосходит t.

Лемма 17.11. Для всякого подмножества ACS следующие три условия эквивалентны:

1.множество А независимо,

2.для всех t = 1, 2,..., га имеем Nt(A) t,

3.если расположить заказы из множества А в порядке неубывания сроков, то все заказы будут выполнены в срок.

Доказательство. Если Nt(A) > t для некоторого t, то заказов, которые должны быть выполнены за первые t единиц времени, больше t и один из них непременно будет просрочен. Таким образом, (1) влечёт (2). Если выполнено (2), то г-ж по порядку срок окончания заказа не меньше г, и при расстановке заказов в этом порядке все сроки будут соблюдены. Следовательно, (2) влечёт (3). Импликация (3) => (1) очевидна.□

Условие (2) является удобным критерием независимости множества заказов (см. упражнение 17.5-2).