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

СТРУКТУРЫ ДАННЫХ для ЗАДАЧ, КАСАЮЩИХСЯ РАБОТЫ С МНОЖЕСТВАМИ

Хороший подход к разработке эффективного алгоритма для данной задачи - изучить ее сущность. Часто задачу можно сформулировать на языке основных математических понятий, таких, как множество, и тогда алгоритм для нее можно изложить в терминах основных операций над основными объектами. Преимущество такой точки зрения в том, что можно проанализировать несколько различных структур данных и выбрать из них ту, которая лучше всего подходит для задачи в целом. Таким образом, разработка хорошей структуры данных идет рука об руку с разработкой хорошего алгоритма.

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

4.1. ОСНОВНЫЕ ОПЕРАЦИИ НАД МНОЖЕСТВАМИ

Будем рассматривать следующие основные операции над множествами.

1. ПРИНАДЛЕЖАТЬ (а, S). Устанавливает принадлежность а множеству S; если а g S, печатается "да"; в противном случае- "нет."

2. ВСТАВИТЬ (а, S). Заменяет S на S U {а}-

3. УДАЛИТЬ (а, S). Заменяет S на S-{a}.

4. ОБЪЕДИНИТЬ (Si, Sa, s3). Строит множество s3=SiUS2. Мы будем предполагать, что в тех случаях, когда применяется эта операция, множества Si и Ss не пересекаются; это делается для того, чтобы избежать необходимости удалять повторяющиеся экземпляры одного и того же элемента в Si uSa.

5. НАЙТИ (а). Печатает имя того множества, которому в данный



момент принадлежит а. Если а принадлежит более чем одному множеству, то операция не определена.

6. РАСЦЕПИТЬ (а, S). Здесь предполагается, что множество S наделено линейным порядком Операция разбивает S на два множества Si={b\ba и bS) и Si={b\b>>a и bS}.

7. MIN (S). Выдает наименьший (относительно ) элемент множества S.

Многие задачи, встречающиеся на практике, можно свести к одной или нескольким подзадачам, таким, что каждую подзадачу можно абстрактно сформулировать как последовательность основных команд, которые следует выполнить на некоторой базе данных (универсальном множестве элементов). В данной главе мы будем изучать последовательности о команд, каждая из которых является операцией одного из перечисленных выше семи типов.

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

Здесь возникает много интересных вопросов. Нас будет интересовать главным образом временная сложность выполнения операций в о, т. е. время как функция длины последовательности а и размера базы данных. Мы исследуем временную сложность в худшем случае и в среднем, а также сложность выполнения о в префиксном и свободном режимах.

Определение. Выполнение последовательности операций а в префиксном режиме требует, чтобы операции в о выполнялись в порядке слева направо, причем i-я операция в о должна выполняться без просмотра какой бы то ни было последующей операции. При свободном режиме разрешается просматривать всю последовательность а в любой момент времени.

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

Пусть дана последовательность операций, которую надлежит выполнить. Основной вопрос: какую структуру данных использовать для представления универсальной базы данных? Часто задача будет требовать осторожного взвешивания всех за и против каждого

« А. Ахо, Дж. Хопкрофт. Дж. Ульман 129



») То есть ViUVsU.--UVft=V и V,nV/=0 при f/.

конкретного выбора. В типичной ситуации последовательность будет состоять из нескольких операций, подлежащих многократному выполнению, часто в неизвестном порядке. Может оказаться несколько структур данных, каждая из которых позволяет одну операцию выполнять легко, а другие - с большим трудом. Во многих случаях лучшим решением будет компромисс. Часто мы будем использовать структуру, которая не делает максимально легким выполнение ни одной из операций, но позволяет выполнить всю работу лучше, чем при любом очевидном подходе.

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

Определение. Путь G= {V, Е) - неориентированный граф. Ос-товньш деревом S (для) графа G называется неориентированное дерево вида (V, Т), ТЕ. Остовньш лесом (для) графа (/называется множество неориентированных деревьев вида {{Vu Ti,), (Vt, Т), ... . . ., (Vft, Th)}, в котором Vi образуют разбиение множества») V, а каждое множество Ti является (возможно, пустым) подмножеством в Е.

Функцией стоимости для графа G= (V, Е) называется отображение с из Я в множество вещественных чисел. Стоимостью подграфа G=(V, Е) графа G считается c(G)= 2, с(е).

Пример 4.1. Рассмотрим алгоритм, приведенный на рис. 4.1, для нахождения для данного графа G= (V, Е) остовного дерева S=(V, Т) наименьшей стоимости. Этот алгоритм построения остовного дерева наименьшей стоимости подробно обсуждается в разд. 5.1, а его применение проиллюстрировано в примере 5.1.

В алгоритме на рис. 4.1 участвуют три множества Е, Т и VS. Множество Е содержит ребра данного графа G, а Г используется для сбора ребер окончательного остовного дерева. Работа алгоритма состоит в преобразовании остовного леса для G в единое остовное дерево. Множество VS содержит множества узлов, входящих в деревья этого остовного леса. Вначале VS содержит каждый узел графа G в виде одноэлементного множества.

Можно считать этот алгоритм последовательностью операций с тремя множествами Е,Т и VS. В строке 1 формируется начальное значение для Т, в строках 2 и 3 - для VS (элементы множества VS сами являются множествами). В строке 3 добавляются исходные одноэлементные множества к VS. Строка 4, управляющая основным циклом алгоритма, предполагает наличие счетчика множеств, составляющих VS. В строке 7 выясняется, соединяет ли ребро {v, w) два остовных дерева в остовном лесу. Если да, то в строке 8 эти два





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