|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[146] Рис. 22.5 Рис. 22.4 Сжатие путей в процессе операции Find-Set. а) Дерево перед выполнением операции Find-Set(o). Треугольниками обозначены поддеревья с корнями в изображенных вершинах, б) После исполнения Find-Set(o). 22.2.1. Программы Приводимые ниже программы операций Make-Set, Find-Set и Union включают в себя индуктивное определение ранга, но для удобства мы перескажем его словесно. При создании множества с помощью Make-Set единственной вершине дерева присваивается ранг 0. Операция Find-Set (со сжатием путей) не меняет рангов. При выполнении операции Union с деревьями, ранги корней которых различны, проводится новая стрелка от корня меньшего ранга к корню большего ранга, а ранги опять-таки не меняются. Если, наконец, операция Union проводится с деревьями, ранги корней которых равны, то от одного из корней (все равно, какого) проводится стрелка к другому, и при этом ранг корня объединённого дерева увеличивается на единицу (остальные ранги не меняются). Легко видеть, что определённый таким образом ранг вершины является верхней оценкой для высоты поддерева с корнем в этой вершине. Ниже р[х] обозначает родителя вершины ж, a rank[x] - ее ранг; параметрами процедуры Link, вызываемой из процедуры Union, являются корни двух деревьев. Make-Set(х) 1р[х] \gets х 2rank[x] \gets О Union(x,y) 1 Link(Find-Set(x),Find-Set(у)) Link(x,y) 1if rank[x] > rank[у] 2then p[y] \gets x 3else p[x] \gets у 4if rank[x]=rank[y] 5then rank[y] \gets rank[y]+l Find-Set(x) 1if x \ne p[x] 2then p[x] \gets Find-Set(p[x]) 3return p[x] Рекурсивная процедура Find-Set работает в два прохода: сначала она идет к корню дерева, а затем проходит этот путь в обратном порядке, «переводя стрелки» у встречающихся вершин на корень дерева. Если ж - не корень, то Find-Set вызывает саму себя, но уже с параметром - родителем ж, после чего делает родителем ж корень дерева, найденный этим новым вызовом Find-Set (строка 2). Если же ж - корень, то строка 2 не исполняется, и сразу возвращается указатель на ж. Что дают эвристики Даже будучи применёнными по отдельности, объединение по рангу и сжатие путей дают выигрыш во времени. Если применить объединение по рангу без сжатия путей, то оценка времени работы будет примерно такой же, как при списочной реализации с весовой эвристикой, а именно О (га lgra) (то - общее количество операций, га -количество операций Make-Set (упр. 22.4-3). Эта оценка не-улучшаема (упр. 22.3-3). Если применить сжатие путей без объединения по рангу, то время исполнения последовательности операций, включающей га операций Make-Set и / операций Find-Set, есть (в худшем случае) 0(/ log1+j jn га) при / гаи 0(га + / lg га) при / < га (эти оценки мы доказывать не будем). Еще большая экономия получится, если применить обе эвристики совместно. При этом время работы в худшем случае есть 0(та(т, га)), где а - чрезвычайно медленно растущая «обратная функция Аккермана», определяемая ниже в разделе 22.4. В любых мыслимых приложениях выполнено неравенство си (га, га) 4, так что на практике можно считать время работы линейным по га. В разд. 22.4 мы докажем чуть более слабую оценку 0(ralg* га). Упражнения 22.3-1 Сделайте упражнение 22.2-2, пользуясь реализацией с помощью леса со сжатием путей и объединением по рангам. 22.3-2 Напишите нерекурсивный вариант процедуры Find-Set. 22.3-3 Приведите пример последовательности га операций Make-Set, Union и Find-Set (в том числе га операций Make-Set, для которой время работы (при использовании объединения по рангу без сжатия путей) будет Q(гаlgra). 22.3-4* Рассмотрим последовательность га операций Make-Set, Link и Find-Set, в которой все операции Find-Set идут после всех операций Link. Докажите, что при использовании объединения по рангам со сжатием путей время работы этой последовательности операций есть О (га). Что будет, если пользоваться только сжатием путей? 22.4* Объединение по рангам со сжатием путей: анализ В этом разделе мы дадим определение «обратной функции Аккермана» а(га,га), входящей в оценку 0(та(т, га)) для стоимости га операций с системой непересекающихся множеств, реализован- Рис. 22.5 22.6. Значения A(i,j) для малых г и j. Переводы: row - строка, column - столбец Рис. 22.6 Рис. 22.7. Рост функции Аккермана. В таблице значений (рис. 22.6) соединены равные числа. Масштаб по горизонтали соблюсти невозможно (из-за очень быстрого роста). ной с помощью леса с объединением по рангам и сжатием путей (здесь п - число операций Make-Set). Эту оценку мы доказывать не будем, ограничившись более слабой оценкой 0(тlg* п). Функция Аккермана и обратная к ней Функцией Аккермана (Ackermanns function) называется функция A(i,j) двух целых положительных переменных, определённая так: Значения A(i,j) для малых г и j изображены на рис. 22.6. В таблице значений функции Аккермана каждая следующая строка есть подпоследовательность предыдущей (начинающаяся со второго члена); отсюда следует, что A(i,j) увеличивается при увеличе- нии г или j. Эта функция растёт очень быстро: уже первая строка в таблице её значений растёт экспоненциально, а каждая последующая строка есть (весьма редкая) подпоследовательность предыдущей. Именно, в к + 1-ой строке таблицы записана последо- вательность, каждый следующий член которой получается из преды- дущего применением функции, записанной в к-оъ строке. В частности, во второй строке каждый следующий член есть двойка, возведённая в степень предыдущего члена. Взаимоотношения между различными строками таблицы значений функции Аккермана схематически изображены на рис. 22.7. Определим, наконец, обратную функцию Аккермана а(т,п). Строго говоря, а не является обратной к функции Аккермана А (тем более что последняя имеет два аргумента), но можно сказать, что функция а растет столь же медленно, сколь быстро растет А. (Детали определения а существенны для доказательства оценки 0(та(т, п)), которое выходит за рамки нашей книги.) Итак, при т > п > 1 полагаем: если j 1; если г 2; если i,j 2. а(т, п) = min { г 1 : A(i, [т/п\) > lg п } . Легко видеть, что при фиксированном п функция а(т, п) монотонно убывает с ростом то. Это согласуется с (не доказываемым |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||