2.44M
Категория: ИнформатикаИнформатика

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

1.

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

2.

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

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.

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

31.

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

32.

Взвешенное быстрое
объединение: анализ
Время выполнения
Find: пропорционально глубине p и q
Union: константа + глубина корней
Утверждение: Глубина любого узла не
превосходит log2N
WQU гарантирует приемлемую
производительность?
Нет

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.

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

41.

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

42.

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

43.

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

44.

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

45.

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

46.

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

47.

Перколяция
Введем две дополнительные точки (сложность
проверки 1)

48.

Перколяция
Как модель открывает новую точку?

49.

Перколяция
Как модель открывает новую точку?
Помечает новую точку как открытую; соединяет с
соседними открытыми точками (если есть) при
помощи 4-х вызовов union()

50.

Пороговое значение
Как насчет порога р*?
Для больших квадратных решеток = 0.592746
English     Русский Правила