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

begin

СПИСОК (Si, S,); НАБОР 0;

for sSUS do добавить {s} в НАБОР;

comment Мы только что образовали исходные множества для

каждого состояния из SjUSj; wfiile есть пара (s, s), входящая в СПИСОК do begin

удалить (s, s) из множества СПИСОК;

пусть А и А обозначают HAflTH(s) и НАЙТИ (s) соответственно;

if АфА tlien begin

ОБЪЕДИНИТЬ (Л, А, Л); for а g / do добавить (6(s, а), 6(s, а)) в СПИСОК

Рис. 4.25. Алгоритм для нахождения множеств эквивалентных состояний в предположении, что «1 и эквивалентны.

Чтобы узнать, эквивалентны ли два конечных автомата Mi= = (5i, /, б,, Si, Fi) и Ma= (Sa, /, 62, S2, Fa). МЫ поступаем так:

1. С помощью программы на рис. 4.25 находим все множества состояний, которые должны быть эквивалентными, если эквивалентны Si и Sa. СПИСОК содержит такие пары состояний (s, s), что S и s оказались эквивалентными, а следующие за ними состояния (S(s, а), 8(s, а)) еще не рассматривались. Вначале СПИСОК содержит только пару (su Sa). Чтобы найти множества эквивалентных состояний, программа применяет алгоритм объединения непересекающихся множеств. НАБОР представляет некоторое семейство множеств. Вначале каждое состояние из Si (jSa образует одноэлементное множество. (Без потери общности можно считать, что множества Si и Sa не пересекаются.) Затем всякий раз, когда s и s оказываются эквивалентными, содержащие их множества Л и Л, входящие в НАБОР, сливаются, и новое множество получает имя Л.

2. После выполнения этой программы множества, входящие в НАБОР, представляют разбиение множества SiUSj на блоки



состояний, которые должны быть эквивалентными. Mi а М2 эквивалентны тогда и только тогда, когда никакой блок не содержит допускающего состояния вместе с недопускающим.

Время работы этого алгоритма (как функция от числа состояний n=5ilH-52) определяется в основном работой алгоритма объединения множеств. Операций ОБЪЕДИНИТЬ может быть не более п-1, поскольку каждая такая операция уменьшает на единицу число множеств, входящих в НАБОР, а вначале было только п множеств. Число операций НАЙТИ пропорционально числу пар, помещенных в СПИСОК. Это число не больше п/, так как всякая пара, кроме начальной (Si, Sa), попадает в СПИСОК только после операции ОБЪЕДИНИТЬ. Таким образом, при постоянном размере входного алфавита на распознавание эквивалентности конечных автоматов Mi и М тратится время 0(nG{n)).

4.9. СХЕМЫ СБАЛАНСИРОВАННЫХ ДЕРЕВЬЕВ

При решении ряда важных классов задач, аналогичных задаче ОБЪЕДИНИТЬ - НАЙТИ, мы, по-видимому, вынуждены вернуться к способам, при которых последовательность из л операций выполняется за время O(nlogn) (в худшем случае). В один такой класс входят задачи, в которых последовательность из операций ПРИНАДЛЕЖАТЬ, ВСТАВИТЬ и УДАЛИТЬ выполняется в случае, когда допускается гораздо больше элем нтов, чем используется на самом деле. В этом случае нельзя выбрать элемент, обращаясь прямо в массив указателей. Надо применять расстановку или дерево двоичного поиска.

Если п элементов уже вставлены, то в методе расстановки один выбор осуществляется за постоянное время в среднем и 0{п) в худшем случае. Дерево двоичного поиска дает среднее время О (log л) на один выбор, но в худшем случае может тоже дать плохое время выбора, если множество имен изменяется. Если же просто добавлять имена к дереву, не имея никакого механизма для поддержания его сбалансированности, то можно в результате придти к дереву с л узлами, глубина которого близка к л. Поэтому в худшем случае производительность дерева двоичного поиска будет О (л) шагов на операцию. Методом, изложенным в этом разделе, можно уменьшить сложность в худшем случае до О (log л) шагов на операцию.

Другой класс задач, требующих О (л log л) времени, образуют задачи выполнения последовательности из л операций, включающих ВСТАВИТЬ, УДАЛИТЬ и MIN, в префиксном режиме. Еще один, третий, класс задач возникает, когда нужно представлять упорядоченные списки и уметь сцеплять и расцеплять их.

В настоящем разделе мы познакомимся с техникой, позволяющей выполнять в префиксном режиме последовательности, содер-



жащие важные подмножества семи основных операций на множествах, введенных в разд. 4.1. Структурой данных, лежащей в основе метода, является сбалансированное дерево, под которым мы понимаем дерево с высотой, приблизительно равной логарифму числа его узлов.

Вначале сбалансированное дерево строится легко. Трудно не дать ему в процессе выполнения последовательности операций ВСТАВИТЬ и УДАЛИТЬ превратиться в несбалансированное. Например, если периодически не делать перебалансировку, то при выполнении последовательности операций УДАЛИТЬ, которые удаляют узлы только из левой части дерева, получается дерево, смещенное вправо.

Известно много способов перебалансировки дерева в случае необходимости. Некоторые из них оставляют структуру дерева достаточно гибкой, так что число узлов в дереве высоты h может изменяться от 2 до 2*+i или 3*. В них позволяется по меньшей мере удвоить число узлов в поддереве, прежде чем что-то менять выше его корня.

Мы обсудим два метода этого рода, называемые методами 2-3-деревьев и АвЛ-деревьев. Алгоритмы, работающие с 2-3-деревь-ями, понять легче, и сейчас мы обсудим их. Алгоритмы с АВЛ-деревьями похожи на них, и потому вынесены в упражнения.

Определение. 2-3-деревом называется дерево, в котором каждый узел, не являющийся листом, имеет двух или трех сыновей, а длины всех путей из корня в листья одинаковы. Заметим, что дерево, состоящее из единственного узла, является 2-3-деревом. На рис. 4.26 приведены два 2-3-дерева с шестью листьями.

В следующей лемме показана связь числа узлов и числа листьев в 2-3-дереве с его высотой.

Лемма 4.6. Пусть Т будет 2-3-деревом высоты h. Число узлов дерева Т заключено жжду 2*""i-1 и (З*"""!-1)/2, а число листьев - между 2* и 3*.

Доказательство. Элементарная индукция по h. □


Рис. 4.26. 2-З-деревья,





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.0062