2.44M

Category:

informatics

Объединение-поиск (Union-find)

Создание алгоритма
Шаги:
Создание модели
Поиск алгоритма для решения
Работает быстро? Как использует память?
Если нет, то понять почему
Найти способ решения проблем
Повторять до выполнения условий
Научный подход

3.

Объединение-поиск
(Union-find)
Динамическая связность

4.

Динамическая связность
Дается множество из N объектов
Union command: соединяет два объекта
Find/connected query: проверяет, есть ли путь
между двумя объектами

5.

Пример связности
Есть ли путь между p и q?
Да

6.

Моделирование объектов
Приложения включают в себя работу с объектами
всех типов:
Пиксели на цифровых фотографиях
Компьютеры в сети
Люди в социальных сетях
Транзисторы в компьютерных чипах
Элементы в математических множествах
Имена переменных в программах
При программировании, назначай имена объектов
от 0 до N-1

7.

Моделирование связей
Представим выражение «связано с» как эквивалент
отношениям:
– Рефлексивность:
р соединено с р
– Симметричность:
соединено с p
если p соединено с q, то q
– Транзитивность:
Если p соединено q и q
соединено с r, то p соединено с r
Связные компоненты: максимальное множество
одновременно связанных объектов

8.

Реализация операций
Find query. Проверка, принадлежат ли два объекта
одной компоненте
Union command. Объединение двух компонент

9.

Типы данных для Union-find (API)
Цель: создать эффективные структуры данных для
union-find
Количество объектов N может быть огромным
Количество операций М может быть огромным
Запросы на поиск и объединение могут быть
перемешаны

10.

Приложение
Загрузить N объектов из памяти
Повторять:
чтение пар объектов
если они не соединены, то соединить их и
вывести пару на экран

11.

Объединение-поиск
(Union-find)
Быстрый поиск
(Quick-find)

12.

Структуры данных
Целочисленный массив id[] размером N
Интерпретация: p и q объединены если имеют
одинаковое значение в массиве (id)

13.

Структура данных:
Целочисленный массив id[] размером N
Интерпретация: p и q объединены если имеют
одинаковое значение в массиве (id)
Find. Проверка, если p и q имеют одинаковый id
Объединение. Объединение компонент содержащих p и q. Замена всех значений id[p]

14.

Видео 1

15.

Быстрый поиск: реализация (жадный
подход)

16.

Свойства быстрого поиска
Стоимость. Количество обращений к массиву
(чтение или запись)
Проблемы быстрого поиска. Трудоемкая операция
соединения
Квадратичная сложность. N2 обращений — N
union команд на N объектах

17.

Квадратичные алгоритмы
Пример:
109 операций в секунду
109 слов в памяти
Обращение ко всем словам в
памяти за 1 секунду
Большая проблема для quick-find
109 команд для 109 объектов
Нужно около 1018 операций
Более 30 лет работы

18.

Квадратичные алгоритмы не
масштабируемы
Пример:
109 операций в секунду
109 слов в памяти
Обращение ко всем словам в
памяти за 1 секунду
Большая проблема для quick-find
109 команд для 109 объектов
Нужно около 1018 операций
Более 30 лет работы

19.

Объединение-поиск
(Union-find)
Быстрое объединение
(Quick union)

20.

Быстрое объединение (ленивый
подход)
Структура данных
Целочисленный массив id[] размером N
Интерпретация: id[i] родитель i
Корень i — id[id[id[...id[i]...]]]

21.

Структура данных:
– Целочисленный
массив id[] размером N
– Интерпретация:
id[i] родитель i
– Корень
i — id[id[id[...id[i]...]]]
Find. Проверка, если p и q имеют одинаковый корень
Объединение. Объединение компонент содержащих p и q. Замена id у корня p на id у к

22.

Видео 2

23.

Быстрое объединение: реализация

24.

Свойства быстрого объединения
Стоимость. Количество обращений к массиву
(чтение или запись)
Проблемы быстрого поиска
Трудоемкая операция соединения
Дерево низкое, но дорого его поддерживать в
этом состоянии
Проблемы быстрого объединения

25.

Объединение-поиск
(Union-find)
Быстрое объединение
(Quick union)
Улучшения

26.

Улучшение 1: взвешивание
Взвешенное быстрое объединение
Изменить quick-union чтобы уменьшить высоту
дерева
Следить за размерами каждого дерева (за
количество объектов)
Баланс: связывать корень меньшего дерева с
корнем большего дерева

27.

Видео 3

28.

29.

Структура данных:
–
Такая же, как quick-union, плюс дополнительный массив, где sz[i] количество
объектов в дереве с корнем i
Find. Проверка, если p и q имеют одинаковый корень (так же, как quick-union)
Объединение:
–
Связывать корень меньшего дерева с корнем большего дерева
–
Обновить массив sz[]

30.

31.

Взвешенное быстрое
объединение: анализ
Время выполнения
Find: пропорционально глубине p и q
Union: константа + глубина корней
Утверждение: Глубина любого узла не
превосходит log2N
Доказательство: Когда глубина х возрастает?
Возрастает на 1, когда дерево Т1, содержащее х,
объединяется с деревом Т2
Размер дерева Т1 как минимум в два раза

32.

33.

Компрессия пути
Быстрое объединение с компрессией пути. После
того, как мы узнаем корень р, присоединяем
каждый попавшийся узел к корню.
Видео 4

34.

Компрессия пути: реализация
Добавляем одну строку в функцию root()
Нет причин чтобы этого не делать

35.

Взвешенное быстрое
объединение с компрессия пути
Утверждение. [Hopcroft-Ulman, Tarjan]
Начиная с пустой структуры данных,
последовательность из M union-find
операций на N объектах <= c(N + M
log2* N) доступов к массиву
Линейный алгоритм для М union-find
операций на N объектах
Постоянная стоимость обращения к
данным
Теоретически, WQUPC не линеен

36.

Выводы
WQUPC позволяет решать задачи, которые не
могут быть решены иначе
Пример [109 union-find операций над 109
объектами]
WQUPC сокращает время работы с 30 лет до 6

37.

Объединение-поиск
(Union-find)
Применение

38.

Применение Union-find

39.

Модель для многих физических
систем
Массив размером NxN
Каждая ячейка открыта с вероятностью р (закрыта
с вероятностью 1-р)
Просачивание: если есть путь через открытые
ячейки между противоположными сторонами
массива

40.

41.

Вероятность просачивания

42.

Перколяция
Когда N велико, то теория гарантирует резкий
порог p*
р > p*: точно будет просачивание
p < p*: точно не будет
Каково значение р?

43.

Принцип Монте-Карло
Инициализируем весь массив NxN закрытым
В случайном порядке открываем ячейки, до тех
пор, пока не образуется путь от верха до низа
Оцениваем порог р*

44.

Перколяция
Как проверить систему NxN на перколяцию?
Создать объекты для каждой точки и
пронумеровать их от 0 до N2 - 1

45.

Перколяция
Как проверить систему NxN на перколяцию?
Создать объекты для каждой точки и
пронумеровать их от 0 до N2 — 1
Выделяем связные компоненты

46.

Перколяция
Как проверить систему NxN на перколяцию?
Создать объекты для каждой точки и
пронумеровать их от 0 до N2 — 1
Выделяем связные компоненты
Проверяем относится ли, хотя бы одна точка из
верхней и нижней строчки к одной связной
компоненте (квадратичный алгоритм)