Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 104
Текст из файла (страница 104)
В этот момент А и В одинаковы, с тем отличием, что А содержит х, а  — некоторый другой элемент у. То есть А =  — (у) со (х) для некоторого элемента у е В, так что вс(А) = и (В) — ес(у) + ес(х) > ес(В) . Поскольку множество В оптимально, множество А, содержащее х, также должно быть оптимальным. Теперь покажем, что если какой-то элемент не может быть добавлен изначально, то он не может быть добавлен и позже. Лемма 1б.б Пусть М = (Я, Х) — произвольный матроид. Если х — элемент Я, представляющий собой расширение некоторого независимого подмножества А множества Я, то х также является расширением пустого множества 9.
Доказательство. Поскольку х — расширение множества А, множество А 0 (х) независимое. Так как семейство Х является наследственным, множество (х) должно быть независимым. Таким образом, х — расширение пустого множества 9. 477 Глаеа !д Жадные алгоритмы Следствие 16.9 Пусть М = (Я,Х) — произвольный матроид. Если х — элемент множества Я, который не является расширением пустого множества в, то этот элемент также не является расширением любого независимого подмножества А множества Я. Доказательство. Это следствие — просто обращение леммы 16.8. В следствии 16.9 утверждается, что любой элемент, который не может быть использован сразу, не может использоваться никогда. Таким образом, в процедуре Океепу не может быть допущена ошибка, состоящая в пропуске какого-нибудь начального элемента из множества Я, который не является расширением пустого множества (), поскольку такие элементы никогда не могут быть использованы.
Лемма 16.10 (Матроиды обладают свойством оптимальной подструктуры) Пусть х — первый элемент множества Я, выбранный алгоритмом Океепт для взвешенного матроида М = (Я, Х). Оставшаяся задача поиска независимого подмножества с максимальным весом, содержащего элемент х, сводится к поиску независимого подмножества с максимальным весом для взвешенного матроида М' = (5', Х'), где Я = (у Е Я: (х, у) Е Х) Х' = (В С Я вЂ” (х): В 0 (х) Е Х) н весовая функция матроида М' совпадает с весовой функцией матроида М, ограниченной множеством У.
(Назовем матроид М' сужением (соп!гасбоп) матроида М иа элемент х,) Доказательство. Если А — произвольное независимое подмножество с максимальным весом матроида М, содержащее элемент х, то А' = А — (х) представляет собой независимое подмножество матроида М'. Справедливо также обратное: из любого независимого подмножества А' матроида М' можно получить независимое подмножество А = А' 0 (х) матроида М. Поскольку в обоих случаях выполняется соотношение нг(А) = гс(А') +за(х), решение с максимальным весом лля матронда М, содержащее элемент х, позволяет получить решение с максимальным весом для матроида М', и наоборот. Теорема 1б.11 ~Корректность жадного алгоритма для матроидов) Если М = (Я,Х) — взвешенный матроид с весовой функцией цг, то процедура Пкеепу(М, нг) возвращает оптимальное подмножество.
Доказательство. Согласно следствию 16.9 обо всех изначально пропущенных процедурой Океепу элементах, не являющихся расширениями пустого множества (), можно забыть, поскольку они никогда больше не понадобятся. Когда выбран первый элемент х, из леммы 16Л следует, что процедура Онеепу не допускает ошибки, добавляя элемент х в множество А, потому что существует оптимальное подмножество, содержащее элемент х. И наконец из леммы 16.! О следует, что в оставшейся задаче требуется найти оптимальное подмножество 478 Часть |К усовершенствованные методы разработки и аназша матроида М', представляющего собой сужение матронда М на элемент х.
После того как в процедуре Океезу множество А приобретет вид (л), все остальные действия этой процедуры можно интерпретировать как действия над матроидом М' = (Я', Х'). Это утверждение справедливо благодаря тому, что любое множество В е Хз — независимое подмножество матроида М тогда и только тогда, когда множество В 0 (х) является независимым в матроиде М. Таким образом, в ходе последующей работы процедуры Окиипу будет найдено независимое подмножество с максимальным весом для матроида М', а в результате полного выполнения этой процедуры будет найдено независимое подмножество с максимальным весом для матроида М.
Упражнения 16.4.1 Покажите, что если Я вЂ” произвольное конечное множество, а Ть — множество всех подмножеств Я, размер которых не превышает Й, где Й < ~Я~, то (Я,Ть) является матроидом. 16.4.2 * Пусть Т вЂ” матрица размером пь х и над некоторым полем (например, действительных чисел). Покажите, что если Я вЂ” множество столбцов Т, а А е Т, то (Я, Т) является матроидом тогда и только тогда, когда столбцы матрицы А линейно независимы. 16.4.3 * Покажите, что если (Я, Т) — матроид, то матроидом является н (Я, Х'), где Т' = (А': Я вЂ” А' содержит некоторое максимальное А е Х) т.е. максимальные независимые множества матроида (Я, Х') представляют собой дополнения максимальных независимых множеств матроида (Я, Т). 16.4.4 * Пусть Я вЂ” конечное множество, а Яы Яз,..., Яь — разбиение этого множества на непустые непересекающиеся подмножества.
Определим структуру (Я,Х) с помощью условия Т = (А: ~А П Яз~ ( 1 для ь' = 1,2,..., Ц. Покажите, что (Я,Х)— матроид. Другими словами, множество всех множеств А, содержащих не более одного члена в каждом подмножестве разбиения, определяет независимые множества матроида.
16.4.5 Покажите, как можно преобразовать весовую функцию в задаче о взвешенном матроиде, в которой оптимальное решение представляет собой максимальное независимое подмножество с миниыальнььм весом, чтобы преобразовать ее в стандартную задачу о взвешенном матроиде. Обоснуйте корректность преобразования. Глана )б. Жадные алгоритмы 479 * 16.5. Планирование заданий как мятроид Интересная задача, которую можно решить с помощью матроидов, — составление оптимального расписания единичных заданий, выполняющихся на одном процессоре. Каждое задание характеризуется конечным сроком выполнения, а также штрафом при пропуске этого срока.
Эта задача кажется сложной, однако она на удивление просто решается с помощью жадного алгоритма. Единичное задание (цпМппе )оЬ) — это задание (например, компьютерная программа), для выполнения которого требуется единичный интервал времени. Если имеется конечное множество Я таких заданий, расписание (зсЬебц1е) для этого множества представляет собой перестановку элементов множества Я, определяюшую порядок их выполнения.
Первое задание в расписании начинается в нулевой момент времени и заканчивается в момент времени 1, второе задание начинается в момент времени 1 и заканчивается в момент времени 2, и т.д. Входные данные в задаче по планированию на одном процессоре единичных заданий, характеризующихся конечным сроком выполнения и штрафам, имеют следующий вид: ° множество Я = (аы оз,..., а„), состоящее из и единичных заданий; множество )(ц г(з,..., г(„из и конечных сроков выполнения, представленных целыми числами 1 < )(, ( и; предполагается, что задание а, должно завершиться до момента времени а„ множество из п неотрицательных весов или иилрафных сумм и)), гоз,..., и)„; если задание а, не будет выполнено к моменту времени )(„изымается штраф ю;, если это задание будет выполнено в срок, штрафные санкции не применяются.
Для множества заданий Я нужно найти расписание, минимизируюшее суммарный штраф, который накладывается за все просроченные задания. Рассмотрим произвольное расписание. Будем называть задание в нем просроченным, если оно завершается позже конечного срока выполнения. В противном случае задание своевременное. Произвольное расписание всегда можно привести к виду с первоочередными своевременными заданиями (еаг!у-йгзг 1Ьпп), когда своевременные задания выполняются перед просроченными. Чтобы продемонстрировать это, заметим, что если какое-нибудь своевременное задание ас следует после некоторого просроченного задания а, то задания а, и а можно поменять местами, причем задание а; все равно останется своевременным„а задание о)— просроченным.
Кроме того, справедливо утверждение, согласно которому произвольное расписание всегда можно привести к «аноническаму виду (салошса1 1опп), в котором своевременные задания предшествуют просроченным и расположены в порядке неубывания конечных сроков выполнения. Для этого сначала приведем расписание к виду с первоочередными своевременными заданиями. После этого, до тех пор пока в расписании будут иметься своевременные задания ас и а), которые заканчиваются в моменты времени )е и )с + 1 соответственно, но при этом 480 Часть ги Усовершенствованные методы разработки и аназиза с( < Ып мы будем менять их местами. Поскольку задание аз до перестановки было своевременным, /с+ 1 < с( .
Таким образом, к+ 1 < 4, и задание а, остается своевременным и после перестановки. Задание а сдвигается на более раннее время, поэтому после перестановки оно также остается своевременным. Приведенные выше рассуждения позволяют свести поиск оптимального расписания к определению множества А, состоящего из своевременных заданий в оптимальном расписании. Как только такое множество будет определено, можно будет создать фактическое расписание, включив в него элементы множества А в порядке монотонного возрастания моментов их окончания, а затем перечислив просроченные задания (Я вЂ” А) в произвольном порядке.
Таким образом будет получено канонически упорядоченное оптимальное расписание. Множество заданий А называется независимым, если для него существует расписание, в котором отсутствуют просроченные задания. Очевидно, что множество своевременных заданий расписания образует независимое множество заданий. Обозначим через Т семейство всех независимых множеств заданий. Рассмотрим задачу, состоящую в определении того, является ли заданное множество заданий А независимым. Обозначим через Юс(А) количество заданий в множестве А, конечный срок выполнения которых равен 1 или наступает раньше (величина 1 может принимать значения О, 1, 2,..., и).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
