Алгоритм - объединение
Cтраница 2
Этот алгоритм можно эффективно реализовать с помощью алгоритма объединения непересекающихся множеств и обрабатывать им множества концов у составных ребер. [16]
В данном параграфе сделана попытка изложить методы и алгоритмы объединения статистических данных применительно к следующей весьма распространенной ситуации. [17]
Здесь отображен результат обработки случайных пар 100 объектов алгоритмом взвешенного быстрого объединения с сжатием пути. Все узлы этого дерева, за исключением двух, находятся на расстоянии одного-двух шагов от корня. [18]
Для формирования приближенного решения задачи из решений подзадач применяются алгоритмы объединения решений подзадач с локальной оптимизацией в процессе их объединения. [19]
Промоделируем а с помощью алгоритма 4.3. Начальная последовательность множеств для работы алгоритма объединения строится так: если в последовательности о, встречается операция ВСТАВИТЬ ( г), то считаем, что множество с именем /, IsQ fe l, содержит элемент i. Для того чтобы для тех значений /, для которых существует множество с именем /, образовать дважды связанный упорядоченный список, пользуемся двумя массивами ПРЕД и СЛЕД. [20]
Лемма 1.3 Для определения того, связаны ли два из N объектов, алгоритму взвешенного быстрого объединения требуется отследить максимум lg TV указателей. [21]
Следующий алгоритм, который мы рассмотрим - метод дополнительный к предшествующему, названный алгоритмом быстрого объединения. В его основе лежит та же структура данных - индексированный по именам объектов массив - но в нем используется иная интерпретация значений, что приводит к более сложной абстрактной структуре. Каждый объект указывает на другой объект в этом же наборе, структуре, которая не содержит циклов. Для определения того, находятся ли два объекта в одном наборе, мы следуем указателям для каждого из них до тех пор, пока не будет достигнут объект, который указывает на самого себя. Объекты находятся одном наборе тогда и только тогда, когда этот процесс приводит их к одному и тому же объекту. [22]
Вычислите среднее расстояние от узла до корня в худшем случае в дереве, построенном алгоритмом взвешенного быстрого объединения из 2я узлов. [23]
Вычислите среднее расстояние от узла до корня в худшем случае в дереве, построенном алгоритмом взвешенного быстрого объединения из 2 узлов. [24]
Эта информация, дополняющая данные о времени работы подсистемы, будет использована позже, в алгоритмах объединения. [25]
Лемма 1.2 При наличии М пар N объектов, когда М N, для решения задачи связности алгоритму быстрого объединения может потребоваться выполнение более чем М N / 2 инструкций. [26]
Время работы этого алгоритма ( как функция от числа состояний n S1 S2) определяется в основном работой алгоритма объединения множеств. Операций ОБЪЕДИНИТЬ может быть не более п - 1, поскольку каждая такая операция уменьшает на единицу число множеств, входящих в НАБОР, а вначале было только п множеств. Число операций НАЙТИ пропорционально числу пар, помещенных в СПИСОК. Это число не больше и /, так как всякая пара, кроме начальной ( sb s2), попадает в СПИСОК только после операции ОБЪЕДИНИТЬ. [27]
 |
Результаты экспериментального исследования. [28] |
Эти сравнительные значения времени, затрачиваемого на решение случайных задач связности с использованием алгоритмов объединения-поиска, демонстрируют эффективность взвешенной версии алгоритма быстрого объединения. Дополнительный выигрыш благодаря использованию сжатия пути менее очевиден. Здесь М - количество случайных соединений, генерируемых до тех пор, пока все Л / объектов не оказываются связанными. Этот процесс требует значительно больше операций find, чем операций union, поэтому быстрое объединение выполняется существенно медленнее быстрого поиска. Ни быстрый поиск, ни быстрое объединение не годятся для случая, когда значение Л / очень велико. Время выполнения при использовании взвешенных методов явно пропорционально значению Л /, поскольку оно уменьшается вдвое при уменьшении Л / вдвое. [29]
Разработайте полную структуру данных для МШ-задачи в свободном режиме, включающую представление деревьев массивами, и напишите программу, в которой употребляются массивы, а не команды высокого уровня, используемые алгоритмом объединения непересекающихся множеств. [30]
Страницы: 1 2 3