Ремонт принтеров, сканнеров, факсов и остальной офисной техники


назад Оглавление вперед




[108]

Формально говоря, заявки с номерами г и j совместны (compatible), если интервалы [s8,/8) и [sj,fj) не пересекаются (иными словами, если /г- Sj или fj s8). Задача о выборе заявок (activity-selection problem) состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Жадный алгоритм работает следующим образом. Мы предполагаем, что заявки упорядочены в порядке возрастания времени окончания:

Если это не так, то можно отсортировать их за время О (га log га); заявки с одинаковым временем конца располагаем в произвольном порядке.

Тогда алгоритм выглядит так (/ив - массивы):

Greedy-Activity-Selector(s, /) 1 га <- length[s]

8 return А

Работа этого алгоритма показана на рис. 17.1. Множество А состоит из номеров выбранных заявок, j - номер последней из них; при этом

поскольку заявки отсортированы по временам окончания. Вначале А содержит заявку номер 1, и j = 1 (строки 2-3). Далее (цикл в строках 4-7) ищется заявка, начинающаяся не раньше окончания заявки номер j. Если таковая найдена, она включается в множество А и переменной j присваивается её номер (строки 6-7).

Алгоритм Greedy-Activity-Selector требует всего лишь О(га) шагов (не считая предварительной сортировки). Как и подобает жадному алгоритму, на каждом шаге он делает выбор так, чтобы остающееся свободным время было максимально.

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

Не для всех задач жадный алгоритм даёт оптимальное решение, но для нашей даёт. Убедимся в этом.

Теорема 17.1. Алгоритм Greedy-Activity-Selector даёт набор из наибольшего возможного количества совместных заявок.

Л h <k <k fn-

2A{1}

3Jl

4for i <r- 2

5do i

6 7

fj = max{ fk: k e A}


$i fi

11 4

23 5

30 6

45 7

53 8

65 9

76 10

88 11

98 12

102 13

1112 14

Рис. 17.1 Работа алгоритма greedy-activity-selector для 11 заявок (таблица слева). Каждая строка на рисунке соответствует одному проходу цикла в строках 4-7. Серые заявки уже включены в А, белая сейчас рассматривается. Если левый конец белого прямоугольника левее правого конца правого серого (стрелка идёт влево), то заявка отвергается. В противном случае она добавляется к А.


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

После того как мы договорились рассматривать только наборы, содержащие заявку номер 1, все несовместные с ней заявки можно выкинуть, и задача сводится к выбору оптимального набора заявок из множества оставшихся заявок (совместных с заявкой номер 1). Другими словами, мы свели задачу к аналогичной задаче с меньшим числом заявок. Рассуждая по индукции, получаем, что, делая на каждом шаге жадный выбор, мы придём к оптимальному решению.□

Упражнения

17.1-1 Задачу о выборе заявок можно решать с помощью динамического программирования, вычисляя последовательно (для г = 1, 2,..., п) число тог- - максимально возможное число совместных заявок среди заявок с номерами 1, 2,..., г (считая, что неравенство (17.1) выполнено). Сравните время работы такого алгоритма и алгоритма Greedy-Activity-Selector.

17.1-2 Пусть по-прежнему имеется множество заявок на проведение занятий (каждая заявка указывает начало и конец), но аудиторий сколько угодно. Нужно распределить заявки по аудиториям, используя как можно меньше аудиторий. Разработайте эффективный жадный алгоритм, решающий эту задачу.

Эта задача известна также как задача о раскраске интервального графа (interval-graph coloring problem). Рассмотрим граф, вершинами которого являются заявки, причём вершины соединены ребром тогда и только тогда, когда соответствующие заявки несовместны. Наименьшее количество цветов, необходимое для раскраски вершин графа таким образом, чтобы вершины одного цвета не были соединены, и есть наименьшее количество аудиторий, необходимое для выполнения всех заявок.

17.1-3 Для задачи о выборе заявок возможно несколько способов жадного выбора, и не все они годятся. Покажите на примере, что



[стр.Начало] [стр.1] [стр.2] [стр.3] [стр.4] [стр.5] [стр.6] [стр.7] [стр.8] [стр.9] [стр.10] [стр.11] [стр.12] [стр.13] [стр.14] [стр.15] [стр.16] [стр.17] [стр.18] [стр.19] [стр.20] [стр.21] [стр.22] [стр.23] [стр.24] [стр.25] [стр.26] [стр.27] [стр.28] [стр.29] [стр.30] [стр.31] [стр.32] [стр.33] [стр.34] [стр.35] [стр.36] [стр.37] [стр.38] [стр.39] [стр.40] [стр.41] [стр.42] [стр.43] [стр.44] [стр.45] [стр.46] [стр.47] [стр.48] [стр.49] [стр.50] [стр.51] [стр.52] [стр.53] [стр.54] [стр.55] [стр.56] [стр.57] [стр.58] [стр.59] [стр.60] [стр.61] [стр.62] [стр.63] [стр.64] [стр.65] [стр.66] [стр.67] [стр.68] [стр.69] [стр.70] [стр.71] [стр.72] [стр.73] [стр.74] [стр.75] [стр.76] [стр.77] [стр.78] [стр.79] [стр.80] [стр.81] [стр.82] [стр.83] [стр.84] [стр.85] [стр.86] [стр.87] [стр.88] [стр.89] [стр.90] [стр.91] [стр.92] [стр.93] [стр.94] [стр.95] [стр.96] [стр.97] [стр.98] [стр.99] [стр.100] [стр.101] [стр.102] [стр.103] [стр.104] [стр.105] [стр.106] [стр.107] [стр.108] [стр.109] [стр.110] [стр.111] [стр.112] [стр.113] [стр.114] [стр.115] [стр.116] [стр.117] [стр.118] [стр.119] [стр.120] [стр.121] [стр.122] [стр.123] [стр.124] [стр.125] [стр.126] [стр.127] [стр.128] [стр.129] [стр.130] [стр.131] [стр.132] [стр.133] [стр.134] [стр.135] [стр.136] [стр.137] [стр.138] [стр.139] [стр.140] [стр.141] [стр.142] [стр.143] [стр.144] [стр.145] [стр.146] [стр.147] [стр.148] [стр.149] [стр.150] [стр.151] [стр.152] [стр.153] [стр.154] [стр.155] [стр.156] [стр.157] [стр.158] [стр.159] [стр.160] [стр.161] [стр.162] [стр.163] [стр.164] [стр.165] [стр.166] [стр.167] [стр.168] [стр.169] [стр.170] [стр.171] [стр.172] [стр.173] [стр.174] [стр.175] [стр.176] [стр.177] [стр.178] [стр.179] [стр.180] [стр.181] [стр.182] [стр.183] [стр.184] [стр.185] [стр.186] [стр.187] [стр.188] [стр.189] [стр.190] [стр.191] [стр.192] [стр.193] [стр.194] [стр.195] [стр.196] [стр.197] [стр.198] [стр.199] [стр.200] [стр.201] [стр.202] [стр.203] [стр.204] [стр.205] [стр.206] [стр.207] [стр.208] [стр.209] [стр.210] [стр.211] [стр.212] [стр.213] [стр.214] [стр.215] [стр.216] [стр.217] [стр.218] [стр.219] [стр.220] [стр.221] [стр.222] [стр.223] [стр.224] [стр.225] [стр.226] [стр.227] [стр.228] [стр.229] [стр.230] [стр.231] [стр.232] [стр.233] [стр.234] [стр.235] [стр.236] [стр.237] [стр.238] [стр.239] [стр.240] [стр.241] [стр.242] [стр.243] [стр.244] [стр.245] [стр.246] [стр.247] [стр.248] [стр.249] [стр.250] [стр.251] [стр.252] [стр.253] [стр.254] [стр.255] [стр.256] [стр.257] [стр.258] [стр.259] [стр.260] [стр.261] [стр.262] [стр.263] [стр.264] [стр.265] [стр.266] [стр.267] [стр.268] [стр.269] [стр.270] [стр.271] [стр.272] [стр.273] [стр.274] [стр.275] [стр.276] [стр.277] [стр.278] [стр.279] [стр.280] [стр.281] [стр.282] [стр.283] [стр.284] [стр.285] [стр.286] [стр.287] [стр.288] [стр.289] [стр.290] [стр.291] [стр.292] [стр.293] [стр.294]