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


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




[216]

нии любой вершины из V \ V оно перестаёт быть независимым.

Не следует смешивать задачу нахождения такого множества с гораздо более сложной задачей нахождения независимого множества наибольшей мощности (каковое, конечно, является максимальным - но обратное неверно). Для произвольного графа последняя задача является NP-полной (см. главу 36, задача 36.1). Для га-элементного списка независимое множество максимальной мощности состоит из [га/2] объектов - достаточно взять объекты через один, начиная с первого. Это множество, как и соответствующая 2-раскраска, может быть найде)о с помощью параллельной обработки префиксов за время О (lgra).

Заметьте, что в случае списка любое максимальное множество вершин содержит не меньше га/3 элементов. Действительно, из любых трёх подряд идущих объектов хотя бы один должен входить в множество - иначе средний из этих трёх можно добавить, сохранив независимость.

Ниже будет показано, как за время 0(1) построить максимальное независимое множество по 0(1)-раскраске.

30.5.2. Вычисление 6-раскраски

Укажем алгоритм, находящий 6-раскраску списка. Мы считаем, что за каждым элементом х списка закреплён процессор процессор, номер которого (известный процессору) есть Р(х) G {0,1,... , га -

!}•

Алгоритм последовательно строит раскраски Со, С\,... , Ст, постепенно уменьшая число цветов. Начальная раскраска Со является га-раскраской, а Ст - 6-раскраской. На к-ош шаге по раскраске Ск вычисляется раскраска Ck+i- Число шагов т есть 0(lg* га).

Начальная раскраска Со тривиальна: Со[ж] = Р(х) (цвет вершины есть номер соответствующего ей процессора). Поскольку номера процессоров различны, это отображение действительно является раскраской. (Заметьте, что каждый цвет кодируется [lgra] битами и может храниться в памяти, занимая не слишком много места.)

Опишем теперь процесс построения раскраски Ck+i по Ск (см. рис. 30.11). Мы считаем, что каждый цвет кодируется битовой строкой фиксированной (для данной раскраски) длины. Переход от Ck к Cfc+i уменьшает эту длину.

Итак, пусть цвета раскраски С\ записываются г битами и соседние объекты х и next[x] имеют цвета С[ж] = а и С[гаеж£[г]] = Ь, где а = (ar i, ar-2j • • • , ао), b = (br i, frr-2j • • • , bo). Цвета эти различны, поэтому щ ф bi для некоторого г от 0 до г - 1. Мы объявим пару (г, щ) цветом элемента х в новой раскраске (закодировав её последовательностью битов). Цветом последнего элемента в новой


Рис. 30.11 30.11. Построение 6-раскраски и соответствующего максимального независимого множества. Алгоритм использует п процессоров и работает за время 0(lg* п). Вначале список из п = 20 объектов раскрашен в 20 цветов (что требует пяти битов). За два шага эта раскраска сводится к 6-раскраске. Элементы MIS показаны чёрным цветом.

раскраске мы будем считать пару (0,ао)> если (ar i, ar-2j • • • , ао) было его цветом в старой раскраске.

Остаётся понять, почему в новой раскраске цвета соседних вершин будут различны и сколько битов нужно для кодирования её цветов. Начнём с первого; рассмотрим два соседних элемента ж и у = пежж] в нашем списке. Раньше они имели цвета а = (ar i, аг 2, • • • , ао), Ь = (br i, Ьг 2,... , Ьо)> которые различались в бите г, и новый цвет ж есть пара (г,аг-), причём аг- ф Ь{. Пусть новый цвет у есть пара (j, bj). Видно, что пары эти различны: если различны их первые члены, то и доказывать нечего, если же первые члены совпадают [г = j), то различны вторые bj равно bi и не равно аг-.

Теперь о количестве битов: если на к-ом шаге цвета записывались г битами, то на (к А- 1)-ом шаге они будут записываться всего [lg г] + 1 битами. Если г 4, то при этом число битов уменьшается. Если же г = 3, то два цвета могут различаться в разрядах 0, 1 или 2, поэтому на следующем шаге номер любого цвета будет начинаться с (00), (01) или (10) и оканчиваться нулём либо единицей. При этом из восьми цветов получается не более шести, так что мы приходит к 6-раскраске.

Если предположить, что операция поиска может найти нужный индекс и совершить левый сдвиг за время 0(1), то каждый шаг занимает время 0(1). Алгоритм можно реализовать на EREW-машине, так как каждому процессору необходим доступ лишь к двум объектам - ж и next[x].

Покажем теперь, что число шагов до получения 6-раскраски составляет 0(lg* гг). Напомним, что lg* п определялось как число применений к п функции lg, после которых результат будет не больше 1. Более точно, если через lgW п обозначить г-кратное применение логарифма, то

lg* п = min г 0 : lgW п <i 1 j

В нашем случае число битов на каждом шаге тоже логарифмируется, но затем округляется (с избытком) и увеличивается на 1. Проверим, что всё равно число шагов есть 0(lg* п).

Пусть г\ - число битов, которыми записываются цвета перед г-м шагом. Мы докажем по индукции, что гг- [lg та] + 2 при [lgW гг] 2 Изначально r\ [lg гг]. Пусть утверждение верно для


[г - 1)-го шага. Поскольку гг- = [~lgr8 i] + 1, имеем

г,- = rig-il +1 rig(rig(, 1) Ч + 2)1 +1 rig(ig(,-1) п + 3)1 +1

\Ы2- п)] + 1= rig(lg( 1) п) + 1] + 1 = [lgW га] + 2

Четвёртое неравенство получается так: если [lg га] 2, то "lg(8 1) га~ так что увеличение на 3 можно заменить умножением на 2. Поэтому для т = lg* га - 1 имеем rm ~lg(m 1)] + 24, так как lg(m+1) в 1 и lg(m) п 2 по определению lg* га. Значит, rm+i 3, и ещё через шаг процесс закончится. Таким образом, общее количество шагов составляет 0(lg* га).

30.5.3. Получение максимального независимого множества из 6-раскраски

Пусть дан список из га объектов и его раскраска С в с цветов. Опишем EREW-алгоритм, который позволяет найти по этой раскраске максимальное независимое множество (MIS) за время 0(c). В частности, зная 6-раскраску, можно найти максимальное независимое множество за время 0(1).

Идея алгоритма показана на рис. 30.11 (шесть правых колонок). Для каждого объекта х соответствующий процессор хранит бит alive[x]. При этом alive[x] = TRUE означает, что элемент х ещё имеет шанс попасть в MIS. Вначале alive[x] = TRUE для всех объектов х.

Алгоритм на каждом шаге рассматривает элементы одного цвета. Пусть текущий цвет равен г. Каждый процессор проверяет для своего элемента х условия С[х] = г и alive[x] = TRUE. Если оба условия выполнены, то элемент х включается в MIS, а alive-бнты соседних с ним элементов (следующего и предыдущего) устанавливаются равными FALSE (эти элементы нельзя включать в MIS). После с шагов каждый объект либо включён в MIS, либо имеет alive-бнт, равный FALSE.

Покажем, что полученное множество действительно является независимым и максимальным. Предположим, что в множество попали два соседних объекта. В силу свойств раскраски они имеют разные цвета, поэтому включены на разных шагах. Но включённый первым объект должен был установить alive-бнт второго в положение FALSE, и второй элемент уже не мог быть включён.

Максимальность множества очевидна. Действительно, если элемент х не включён в множество, то alive[x] = FALSE, поэтому в множество включён один из его соседей. Поэтому при добавлении элемента х множество перестанет быть независимым.

Каждый шаг алгоритма требует времени 0(1). Алгоритм может быть реализован на EREW-машине, поскольку каждый процессор обращается только к трём объектам - своему и его соседям. Вместе



[стр.Начало] [стр.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]