Главная Промышленная автоматика.

быть 0(п) утончений. Пример 4.13 показывает, что действительно может потребоваться квадратичное число шагов.

Пример 4.13. Пусть S = {1, 2.....п} и Bi={l, 2, . . ., n-l},

Ва={«} - исходное разбиение. Пусть / - такая функция на S, что f{i)=i+\ для 1<г<п и f(n)n. При первой итерации Bi разбиваем на {1, 2, . . ., п-2} и {п-1}. Эта итерация занимает п-1 шагов, поскольку надо просмотреть каждый элемент в В. При следующей итерации разбиваем {1, 2, . . ., п-2} на {1, 2, ... ..., п-3} и {«-2}. Продолжая в том же духе, выполняем всего п-2 итерации, причем t-я итерация занимает п-i шагов. Следовательно, всего требуется

"£(«-0=-1 1=1

шагов. Окончательным разбиением будет Ei={i} для lin. □

Недостаток этого метода состоит в том, что утончение блока может потребовать О (п) шагов, даже если из него удаляется только один элемент. Сейчас мы опишем алгоритм разбиения, который для разделения блока на два подблока требует время, пропорциональное размеру меньшего подблока. Этот подход приводит к алгоритму сложности О (п log п).

Для каждого блока BsS положим/- (В)=={Ь/(6) gB}. Вместо того чтобы разбивать Bj по значениям f(a) для aBt, разобьем относительно Bj те блоки В,, которые содержат хотя бы один элемент из /"(Bj) и один элемент не из f~{Bi). Иными словами, каждый такой блок Bj разбивается на множества {b\bBj и f(b)Bi} и {b\bBj и miBi).

Как только проведено разбиение относительно блока Bj, больше уже не нужно проводить разбиения относительно него, пока он сам не будет расщеплен. Если вначале f{b)Bi для каждого элемента bBjH Bi расщеплен на В] и В], то можно разбить Bj относительно Bi или В] и получить при этом один и тот же результат, поскольку {b\bBj и f(b)Bi} совпадает с Bj-{b\bBj и f{b)B\).

Так как можно выбирать, по отношению к какому из блоков В\ или В\ проводить разбиение, то мы разбиваем относительно того, для которого это сделать проще. Точнее мы выбираем меньшее из множеств /-1 (Bi) и /-1 (В-). Алгоритм приведен на рис. 4.35.

Алгоритм 4.5. Разбиение

Вход. Множество S из п элементов, разбиение я={В[1], . . , .,., В[р]} и функция /: S -> S.

Выход. Грубейшее разбиение л= {В[1], В[2], . . ., B[q\} множества S, совместимое с я и



begin

1. ОЖИДАНИЕ2, .... р\;

2. q-p;

3. while ОЖИДАНИЕ не пусто do

begin

4. выбрать и удалить любое целое число i из множества

ОЖИДАНИЕ;

5. ОБРАЩЕНИЕ /-MB[i]);

6. for /, для которых В [/] П ОБРАЩЕНИЕ 0 и

В ОБРАЩЕНИЕ do begin

7. qq + \\

8. создать новый блок B{q\,

9. B[9l В [/Jn ОБРАЩЕНИЕ;

10. B[j]B{i]-B[q];

11. if / € ОЖИДАНИЕ then

добавить q в ОЖИДАНИЕ

else

12. if II В [/] IK IIВ [9] li then

13. добавить / в ОЖИДАНИЕ

14. else добавить q в ОЖИДАНИЕ end

Рис. 4.35. Алгоритм разбиения.

Метод. К я применяется программа, приведенная на рис. 4.35. В ней опущены некоторые детали, важные для ее реализации. Мы обсудим эти детали при анализе времени работы алгоритма. □

Анализ алгоритма 4.5 начнем с доказательства того, что он разбивает S нужным образом. Пусть я - разбиение множества 5 и / - отображение множества S на себя. Множество TS будем называть безопасным для я, если для любого блока В я либо Bs (Г), либо В п {Т) = 0. Например, на рис. 4.35 строки 9 и 10 гарантируют, что множество B[i\ безопасно для получающегося разбиения, поскольку если В [\f~ (В[1\)Ф0 а.ля некоторого блока В, то либо В= ОБРАЩЕНИЕ и тогда включение B=f- (В[(]) очевидно, либо в строках 9 и 10 В разбивается на два блока, один



ИЗ которых является подмножеством множества а другой

с ним не пересекается.

В доказательство корректности алгоритма 4.5 входит доказательство того, что окончательное разбиение не оказывается слишком грубым. Иными словами, надо доказать следующее.

Лемма 4.7. После окончания работы алгоритма 4.5 каждый блок В в результирующем разбиении п безопасен для я.

Доказательство. На самом деле мы покажем, что для каждого блока ВЦ]

после каждого выполнения цикла в строках 4 -14 на рис. 4.35, если /ОЖИДАНИЕ и lq, формируется такой список q, q, ...,<7й (возможно, пустой), „ что 6ОЖИДАНИЕ, К»</г, и множество

В [/] и -S [qi] и ... и В [7ft] безопасно для разбиения, построенного в данный момент.

Интуитивно это можно изложить так: когда число / удаляется из множества ОЖИДАНИЕ, строки 6-14 делают блок В[1] безопасным для разбиения, которое получается после строки 14. ВЦ] остается безопасным до тех пор, пока он не будет разбит. Когда В[1] разбивается, индекс одного подблока, назовем его B[q], помещается в ОЖИДАНИЕ. Другой подблок по-прежнему называется ВЦ]. Очевидно, что объединение этих двух подблоков, т. е. BU]UBlq], безопасно для рассматриваемого разбиения, поскольку оно совпадает со старым блоком В[Л. Дальнейшее разбиение образует такие блоки В qj, . . ., BlqA, что qi, . . ., q входят в ОЖИДАНИЕ, а объединение RBUiaBlqi]. . .\jBlq] безопасно. Когда qi при некотором i{lik) удаляется из множества ОЖИДАНИЕ, строки 6-14 снова делают Blqt] и R-Blqt] безопасными. Изложим теперь это формально. Докажем справедливость утверждения (4.6) для всех I индукцией по числу выполнений строк 4-14. Когда алгоритм заканчивает работу, множество ОЖИДАНИЕ пусто, и, значит, из (4.6) будет вытекать, что каждый блок окончательного разбиения л безопасен для я.

Для доказательства базиса возьмем О выполнений, тогда (4.6) тривиально, поскольку I g ОЖИДАНИЕ для всех llq=p.

Для проведения шага индукции предположим, что после выполнения строки 14 ОЖИДАНИЕ. Если число / всегда ранее входило в ОЖИДАНИЕ, то оно имеет значение i, которое определялось в строке 4. Легко показать, что цикл в строках 6-14 делает ВШ безопасным для разбиения, получающегося после выполнения строки 14 Это мы уже обосновали после определения понятия "безопасный".

Если число / не входило в ОЖИДАНИЕ во время предыдущего





0 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

0.0038