Комментарии 29
Жму вашу сильную руку, уже на условие крепко задумался.
Серьезно так. Спасибо за проделанную работу, вы заставили мой мозг задуматься и дали ему пищу на ближайшие пару дней.
Как говорил Альберт Эйнштейн:«Сделай настолько просто, насколько это возможно, но не проще.»
Хорошо, когда используют такой подход
Хорошо, когда используют такой подход
однако я пока так и не понял необходимости хранить множества в виде дерева. Этого требуют дополнительные какие-то условия?
Нет, просто именно такой способ обеспечивает наилучшую скорость работы. Можно хранить списками, можно настоящими множествами (set<T>), но тогда в любом случае какая-нибудь из операций окажется O(log2 N), O(N) и т.д. — слишком медленно.
Вам виднее какую в вашем случае операцию стоит оптимизировать. Но если операций чтения(поиска) будет меньше, чем операций создания(слияния), то алгоритмы стоит применять уже другие, которые так же имеют время работы О(1), но при этом используют меньше функций.
А еще я не могу понять как в теории это работает:
>Достаточно выбирать корень для переподвешивания случайным образом
можно поподробнее на русском языке?
А еще я не могу понять как в теории это работает:
>Достаточно выбирать корень для переподвешивания случайным образом
можно поподробнее на русском языке?
В принципе там есть исходник, однако я не против объяснить и здесь.
У вас есть два элемента, X и Y. Вы стандартными операциями Find нашли корни их деревьев: пускай это RX и RY. Чтобы слить два дерева, достаточно один из корней подвесить к другому непосредственным сыном, то есть сделать просто либо
В стандартной реализации для этого используется массив рангов, и мы выбираем вариант из принципа «дерево меньшей высоты подвешивать к дереву большей высоты». Однако можно обойтись и без этого. Просто принимаем решение случайно: каждый раз генерируем местным
Время работы такой реализации в среднем оценить достаточно проблемно. Однако если её действительно написать и протестировать на многих разнообразных данных, окажется, что она почти не уступает варианту с рангами.
У вас есть два элемента, X и Y. Вы стандартными операциями Find нашли корни их деревьев: пускай это RX и RY. Чтобы слить два дерева, достаточно один из корней подвесить к другому непосредственным сыном, то есть сделать просто либо
P[RX] = Y, либо P[RY] = X. Встает вопрос, какой из двух вариантов выбирать?В стандартной реализации для этого используется массив рангов, и мы выбираем вариант из принципа «дерево меньшей высоты подвешивать к дереву большей высоты». Однако можно обойтись и без этого. Просто принимаем решение случайно: каждый раз генерируем местным
rand() случайное целое число от 0 до 1. Если это 0, подвешиваем RY к RX, если же 1 — то RX к RY.Время работы такой реализации в среднем оценить достаточно проблемно. Однако если её действительно написать и протестировать на многих разнообразных данных, окажется, что она почти не уступает варианту с рангами.
а что мы делаем с рангами? Они какую роль играют в таком случае?
Никакую, они в такой реализации вообще не нужны, их можно не считать и не хранить.
Я малость запутался уже, так что буду уточнять. Т.е. дерево у вас хранится в виде одномерного массива? И все?
Да именно так. И все.
Но ведь вы так же писали
>Будем хранить помимо предков еще один массив Rank.
Он уже стал не нужен?
>Будем хранить помимо предков еще один массив Rank.
Он уже стал не нужен?
Вот именно!
Это два разных варианта реализации одной и той же функции Unite.
В одной нам нужно хранить массив Rank — мы пользуемся им при принятии решения о переподвешивании.
В другой мы принимаем это решение случайным образом, а значит, массив Rank в ней нам не нужен.
Я привел обе реализации, потому что первая является классической, для неё доказана оценка скорости O(α(N)), а вторую проще писать, а на практике она работает почти так же быстро.
Это два разных варианта реализации одной и той же функции Unite.
В одной нам нужно хранить массив Rank — мы пользуемся им при принятии решения о переподвешивании.
В другой мы принимаем это решение случайным образом, а значит, массив Rank в ней нам не нужен.
Я привел обе реализации, потому что первая является классической, для неё доказана оценка скорости O(α(N)), а вторую проще писать, а на практике она работает почти так же быстро.
За дальнейшими техническими подробностями отсылаю читателей к <a href=''file///E:/Informatic@NeXT/10.1.1.79.8494.pdf''>оригинальной статье</a>.спасибо, как-нибудь к вам заедем :)
Периодически использую этот алгоритм. Подробный анализ временной оценки сложности можно найти у самого Тарьяна в его замечательной книге Data Structures and Network Algorithms, отрывки из которой разбросаны по всей сети.
Автор, Вы разбираетесь в математике, да? Можете разъяснить, что такое многомерные множества?
Множество, имеющее размерность n (имеется ввиду размерность Хаусдорфа). Например, множество всех точек прямой одномерно, множество всех точек квадрата двумерно и т.д.
Разумеется, разговор о размерности множества в метрическом пространстве. Метрическое пространство — всего лишь множество, на котором определено расстояние между двумя соседними элементами.
Разумеется, разговор о размерности множества в метрическом пространстве. Метрическое пространство — всего лишь множество, на котором определено расстояние между двумя соседними элементами.
В случае векторных пространств, множество имеет размерность n если в нем существует базис (максимальный набор линейно независимых векторов) размера n.
Но не каждое множество имеет размерность.
Но не каждое множество имеет размерность.
За иллюстрации спасибо. Все равно большинство забудет через пару дней текст, а вот картинки вспомнят и через неделю, может и смутно.
Спасибо огромное, особенно за популяризацию деревьев!
Продолжайте!
Продолжайте!
НЛО прилетело и опубликовало эту надпись здесь
наконец смогу написать быстрое решение задачки 1003 с тимуса :-)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Система непересекающихся множеств и её применения