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

4.6. ПРОСТОЙ АЛГОРИТМ ДЛЯ НАХОЖДЕНИЯ

ОБЪЕДИНЕНИЯ НЕПЕРЕСЕКАЮЩИХСЯ МНОЖЕСТВ

Рассмотрим обработку узлов в алгоритме для нахождения остовного дерева (пример 4.1). Возникающая здесь задача преобразования множеств обладает следующими тремя особенностями.

1. Всякий раз сливаются только непересекающиеся множества.

2. Элементы множеств можно считать целыми числами от 1 до п.

3. Операциями над множествами являются ОБЪЕДИНИТЬ и НАЙТИ

В этом и следующем разделах мы изучим структуры данных для задач такого типа. Пусть даны п элементов, которые мы будем считать целыми числами 1,2, . . ., п. Предположим, что вначале каждый элемент образует одноэлементное множество. Пусть надо выполнить последовательность операций ОБЪЕДИНИТЬ и НАЙТИ. Напомним, что операция ОБЪЕДИНИТЬ имеет вид ОБЪЕДИНИТЬ (Л, В, С), указывающий, что два непересекающихся множества с именами А В надо заменить их объединением и назвать это объединение С. В приложениях часто неважно, что выбирается в качестве имени множества, так что мы будем предполагать, что множества можно именовать целыми числами от 1 до п. Кроме того, мы будем предполагать, что никакие два множества ни в один момент не названы одинаково.

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

Заметим, что в алгоритмах поиска, изложенных в разд. 4.2- 4.5, предполагалось, что элементы выбираются из универсального

Теперь должно быть ясно, как доказать по индукции, что процедура ПОСТРДЕРЕВА (i, j) правильно строит оптимальное дерево для aj}. □

В алгоритме 4.2 можно ограничить поиск т в строке 8 рис. 4.9 областью между положениями корней деревьев Tij-i и Tt+i,j, при этом гарантируется нахождение минимума. Тогда алгоритм 4.2 сможет находить оптимальное дерево за время 0{п).



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

По-видимому, простейшей структурой данных для задачи типа ОБЪЕДИНИТЬ - НАЙТИ служит массив, представляющий набор множеств в данный момент. Пусть R - массив размера п, а Rli] - имя множества содержащего элемент i. Так как вид имен множеств не существен, можно вначале взять Rli]=i, lin, к выразить тем самым факт, что перед началом работы набором множеств является {{1}, {2}, . . ., {п}} и множество {i} имеет имя /.

Операция НАЙТИ (i) выполняется путем печати значения R[i\ в данный момент. Поэтому сложность выполнения операции НАЙТИ постоянна, а это лучшее, на что можно надеяться.

Чтобы выполнить операцию ОБЪЕДИНИТЬ (Л, В, С), надо последовательно просмотреть массив R и заменить каждую его компоненту, равную А или В, на С. Поэтому сложность выполнения такой операции есть О (п). Последовательность из п операций ОБЪЕДИНИТЬ могла бы потребовать 0{п) времени, что нежелательно.

Этот безыскусный алгоритм можно улучшить несколькими способами. Для одного улучшения можно воспользоваться преимуществом связанных списков. Для другого - понять, что всегда эффективнее влить меньшее множество в большее. Чтобы сделать это, надо отличать "внутренние имена", используемые для идентификации множеств в массиве R, от "внешних имен", упоминаемых в операциях ОБЪЕДИНИТЬ. И те, и другие предполагаются числами от 1 до п, но не обязательно одинаковыми.

Рассмотрим следующую структуру данных для этой задачи. Как и ранее, возьмем такой массив R, что RU] содержит "внутреннее" имя множества, которому принадлежит элемент i. Но теперь для каждого множества А мы построим связанный список СПИ-С0К1Л ], содержащий его элементы. Для реализации этого связанного списка применяются два массива СПИСОК и СЛЕДУЮЩИЙ. СПИСОК [Л] представляет собой целое число /, указывающее, что / - первый элемент в множестве с внутренним именем Л. СЛЕДУЮЩИЙ [/] дает следующий элемент в Л, СЛЕДУЮЩИЙ [СЛЕДУЮ ЩИЙ [/]] - следующий за ним элемент, и т. д.

Кроме того, возьмем еще массив, называемый РАЗМЕР, такой, что РАЗМЕР [Л] - число элементов в множестве Л. Множества будут переименовываться по внутренним именам, а два массива ВНУТР ИМЯ и ВНЕЩ ИМЯ будут устанавливать соответствие между внутренними и внешними именами. Иными словами, ВНЕШ. ИМЯ [Л] - это настоящее имя (диктуемое операциями ОБЪЕДИНИТЬ) множества с внутренним именем Л. ВНУТР ИМЯ [/]- это внутреннее имя множества с внешним именем /. Внутренние имена - это имена, используемые в массиве R.



R следующий

список

РАЗМЕР

ВНЕШ. ИМЯ

Множества (с внешними именами)

ВНУТР ИМЯ

1={1,3,5,7>

2 = {2. 4, 8}

3 = {6>

Рис. 4.13. Структуры данных для алгоритма ОБЪЕДИНИТЬ - НАЙТИ.

procedure ОБЪЕДИНИТЬ!/, У, К): begin

1. ЛВНУТР ИМЯ[У];

2. В*-ВНУТР ИМЯИ;

3. wig положить PA3MEP[J<PA3MEP[BJ

4. otherwise поменять ролями Л и В in begin

5. ЭЛЕМЕНТ СПИСОК[Л J;

6. while ЭЛЕМЕНТНО do

begin

7. /?[ЭЛЕМЕНТ]В;

8. ПОСЛЕДНИЙ ЭЛЕМЕНТ;

9. ЭЛЕМЕНТ СЛЕДУЮ1ДИЙ[ЭЛЕМЕНТ] end;

10. СЛЕДУЮЩИЙ[ПОСЛЕДНИЙ] СПИСОК[В];

11. СПИСОК[В]*-СПИСОК[Д];

12. РАЗМЕР[В] РАЗМЕР[Л] + PA3MEP[BJ;

13. ВНУТР.ИМЯ \К\ - В;

14. ВНЕШ ИМЯ[В]-/С end

Рис. 4,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.0021