Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 98

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 98)

После того как в процедуре Окнноу множество А приобретет вид (х), все остальные действия этой процедуры можно интерпретировать как действия над матроидом М' = (У,Х'). Это утверждение справедливо благодаря тому, что любое множество В а 1' — независимое подмножество матроида М' тогда и только тогда, когда множество В О (х) независимо Часть 1Ч. Усовершенствованные методы разработки и анализа 474 в матроиде М.

Таким образом, в ходе последующей работы процедуры Окивпт будет найдено независимое подмножество с максимальным весом для матроила М', а в результате полного выполнения этой процедуры будет найдено независимое подмножество с максимальным весом для матроида М. Упражнения 16.4-1. Покажите, что если Я вЂ” произвольное конечное множество, а 2~ — множество всех подмножеств Я, размер которых не превышает Й < ~Я~, то (Я, Хь) — матроид. * 16.4-2. Пусть Т вЂ” матрица размером тп х и над некоторым полем (например, действительных чисел). Покажите, что если о — множество столбцов Т, а А е Х, то (о, Х) является матроидом тогда и только тогда, когда столбцы матрицы А линейно независимы.

* 16.4-3. Покажите, что если (Я, Х) — матроид, то матроидом является и (Я, Т), где 2" = (А': Я вЂ” А' содержит некоторое максимальное А е Х1, т.е. максимальные независимые множества матроида (Я, Х') представляют собой дополнения максимальных независимых множеств матроила (о,2). * 16.4-4. Пусть Я вЂ” конечное множество, а Яп Яз,..., Яь — разбиение этого множества на непустые непересекающиеся подмножества. Определим структуру(Я,Х) спомощьюусловияХ = (А: 1А П Я,! < 1 для г = 1,2,...,Ц.

Покажите, что (Я, Х) — матроид. Другими словами, семейство всех множеств А, содержащих не более одного члена в каждом блоке разбиения, определяет независимые множества матроида. 16.4-5. Покажите, как можно преобразовать весовую функцию в задаче о взвешенном матроиде, в которой оптимальное решение представляет собой максимальное независимое подмножество с минимальным весам, чтобы преобразовать ее в стандартную задачу о взвешенном матроиде.

Обоснуйте корректность преобразования. * 16.5 Планирование заданий Интересная задача, которую можно решить с помощью матроидов, — задача по составлению оптимального расписания единичных заданий, выполняющихся на одном процессоре. Каждое задание характеризуется конечным сроком выпол- Глава 16. Жадные алгоритмы 475 пения, а также штрафом при пропуске этого срока. Эта задача кажется сложной, однако она на удивление просто решается с помощью жадного алгоритма. Единичное задание (цп11-бэппе )оЪ) — это задание (например, компьютерная программа), для выполнения которого требуется единичный интервал времени.

Если имеется конечное множество Я таких заданий, расписание (зсЪедп!е) для этого множества представляет собой перестановку элементов множества Я, определяющую порядок их выполнения. Первое задание в расписании начинается в нулевой момент времени и заканчивается в момент времени 1, второе задание начинается в момент времени 1 и заканчивается в момент времени 2 и т.д.

Входные данные в задаче по планированию на одном процессоре единичных заданий, «арактеризующихся конечным сроком выполнения и иапрафом, имеют следующий вид: ° множество Я = (ам аз,..., а„), состоящее из и единичных заданий; ° множество Ыы Нз,..., Ы„конечных сроков выполнения, представленных целыми числами 1 < с(, < и; предполагается, что задание оя должно завершиться к моменту времени 4; ° множество из и неотрицательных весов или ииира4вных сумм юм таз,..., и„; если задание а; не будет выполнено к моменту времени д„изымается штраф ю;; если это задание будет выполнено в срок, штрафные санкции не применяются.

Для множества заданий Я нужно найти расписание, минимизирующее суммарный штраф, который накладывается за все просроченные задания. Рассмотрим произвольное расписание. Говорят„что задание в нем просрочено, если оно завершается позже конечного срока выполнения. В противном случае задание своевременное. Произвольное расписание всегда можно привести к виду с первоочередньими своевременными заданиями (еаг1у-бгз! Гопп), когда своевременные задания выполняются перед просроченными. Чтобы продемонстрировать это, заметим, что если какое-нибудь своевременное задание ал следует после некоторого просроченного задания ау, то задания а; и а можно поменять местами, причем задание а; все равно останется своевременным, а задание а — просроченным. Аналогично, справедливо утверждение, согласно которому произвольное расписание можно привести к каноническому виду (сапошса1 Гопп), в котором своевременные задания предшествуют просроченным и расположены в порядке монотонного возрастания конечных сроков выполнения.

Для этого сначала приведем расписание к виду с первоочередными своевременными заданиями. После этого, до тех пор пока в расписании будут иметься своевременные задания а; и ау, которые заканчиваются в моменты времени Й и Й + 1 соответственно, но при этом ад < с(о мы будем менять их местами. Поскольку задание а до перестановки Часть!Ч. Усовершенствованные методы разработки н анализа 476 было своевременным, к+ 1 < с1 . Таким образом, й+ 1 < 4, и задание ен остается своевременным и после перестановки.

Задание а сдвигается на более раннее время, поэтому после перестановки оно тоже остается своевременным. Приведенные выше рассуждения позволяют свести поиск оптимального расписания к определению множества А, состоящего из своевременных заданий в оптимальном расписании. Как только такое множество будет определено, можно будет создать фактическое расписание, включив в него элементы множества А в порядке монотонного возрастания моментов их окончания, а затем — перечислив просроченные задания (Я вЂ” А) в произвольном порядке.

Таким образом будет получено канонически упорядоченное оптимальное расписание. Говорят, что множество заданий А независимое, если для него существует расписание, в котором отсутствуют просроченные задания. Очевидно, что множество своевременных заданий расписания образует независимое множество заданий. Обозначим через 2 семейство всех независимых множеств заданий. Рассмотрим задачу, состоящую в определении того, является ли заданное множество заданий А независимым. Обозначим через Ф~(А) количество заданий множества А, конечный срок выполнения которых равен г или наступает раньше (величина 1 может принимать значения О, 1, 2,..., и).

Заметим, что Хо (А) = 0 для любого множества А. Лемма 16Л2. Для любого множества заданий А сформулированные ниже утвер- ждения эквивалентны. 1. Множество А независимое. 2. Для всех 1 = О, 1, 2,..., и выполняются неравенства Ф~ (А) < 1. 3. Если в расписании задания из множества А расположены в порядке монотонного возрастания конечных сроков выполнения, то ни одно из них не является просроченным.

Доказа~пельство. Очевидно, что если для некоторого г )У~ (А) > г, то невозможно составить расписание таким образом, чтобы в множестве А не оказалось просроченных заданий, поскольку до наступления момента 1 остается более 1 незавершенных заданий. Таким образом, утверждение (1) предполагает выполнение утверждения (2).

Если выполняется утверждение (2), то (-й по порядку срок завершения задания не превышает 1, так что при расстановке заданий в этом порядке все сроки будут соблюдены. Наконец, из утверждения (3) тривиальным образом следует справедливость утверждения (1). С помощью свойства (2) леммы 16.12 легко определить, является ли независимым заданное множество заданий (см. упражнение 16.5-2). Глава 16. Жадные алгоритмы 477 Задача по минимизации суммы штрафов за просроченные задания — это то же самое, что задача по максимизации суммы штрафов, которых удалось избежать благодаря своевременному выполнению заданий.

Таким образом, приведенная ниже теорема гарантирует, что с помощью жадного алгоритма можно найти независимое множество заданий А с максимальной суммой штрафов. Теорема 16.13. Если  — множество единичных заданий с конечным сроком выполнения, а 2 — семейство всех независимых множеств заданий, то соответствующая система (В,2) — матроид. Доказательство. Ясно, что любое подмножество независимого множества заданий тоже независимо. Чтобы доказать, что выполняется свойство замены, предположим, что В и А — независимые множества заданий, и что (В( > )А(. Пусть й— наибольшее 1, такое что Х~ (В) < Жр (А) (такое значение 1 существует, поскольку Мо(А) = Хо(В) = 0.) Так как Ф„(В) = (В~ и Ф„(А) = )А), но (В) > (А), получается, что Й < и, и для всех з в диапазоне Й + 1 < з < п должно выполняться соотношение Жу (В) > Х (А). Таким образом, в множестве В содержится больше заданий с конечным сроком выполнения й + 1, чем в множестве А.

Пусть ги — задание из множества  — А с конечным сроком выполнения й + 1, и пусть А' = А 1.1 (гм). Теперь с помощью второго свойства леммы 16.12 покажем, что множество А' должно быть независимым. Поскольку множество А независимое, для любого 0 < 1 < 1с выполняется соотношение М~ (А') = 21г~ (А) < 1. Для lс < 1 < и„ поскольку  — независимое множество, имеем Ж~ (А') < М, (В) < 1. Следовательно, множество А' независимое, что и завершает доказательство того, что (Я, Х) — матроид. И С помощью теоремы 16.11 можно сформулировать жадный алгоритм, позволяющий найти независимое множество заданий А с максимальным весом.

После этого можно будет создать оптимальное расписание, в котором элементы множества А будут играть роль своевременных заданий. Этот метод дает эффективный алгоритм планирования единичных заданий с конечным сроком выполнения и штрафом для одного процессора. Время работы этого алгоритма, в котором используется процедура бквппу, равно О (тР), поскольку каждая из О (и) проверок независимости, выполняющихся в этом алгоритме, требует времени О (и) (см. упражнение 16.5-2). Более быструю реализацию этого алгоритма предлагается разработать в задаче 16-4.

В табл. 16.2 приводится пример задачи по планированию на одном процессоре единичных заданий с конечным сроком выполнения и штрафом. В этом примере жадный алгоритм выбирает задания ам аз, аз и ая, затем отвергает задания иь и ае, и наконец выбирает задание ат. В результате получается оптимальное рас- Часть !Ч. Усовершенствованные методы разработки н аналим 478 Таблица 16.2.

Характеристики

Список файлов книги