Pull to refresh

Comments 17

А разве скрипт Хабра автоматически не перезаливает картинки со сторонних источников на hsto.org?
На практике же его используют чаще для решения комбинаторных задач.

Можно с этого места поподробнее?

Могу предложить такой пример: равновероятно сгенерировать случайное дерево. Кожд Прюфера кажется самым простым решением, как без него добиться равновероятности деревьев — непонятно.

Просто любое случайное дерево? Их же бесконечное количество?
Или дерево определенного размера? Дерево с ограничением на размер сверху? Остовное дерево для заданного графа? k-ичное дерево?
Это все очень разные задачи, уточните пожалуйста, какую именно вы имели в виду.

Сгенерировать произвольное дерево на ровно N пронумерованных вершинах.

При этом, стоит заметить, генерация дерева на не более чем N вершинах через генерацию на ровно N вершинах довольно легко выражается

Мы знаем количество деревьев на 1, 2, 3, ..., N вершинах. Выберем сначала с соответствующими вероятностями число вершин (т.е. выбираем число K с вероятностью, пропорциональной K^{K-2}), а потом сгенерируем дерево на ровно K вершинах.

А можно для тех кто "не в теме", что значит " добиться равновероятности дерева"?

То и значит. Каждое дерево имеет одинаковую вероятность с остальными быть выбранным из всего набора деревьев.

Вот есть множество всех деревьев на N вершинах, их конечно, а точнее — N^{N-2} по теореме Кэли. Давайте их как-нибудь занумеруем, потом выберем случайное число от 1 до N^{N-2} равновероятно (т.е. каждое число выбирается с одинаковой вероятностью), возьмём дерево с таким номером.

Хотелось бы примеры использования данного алгоритма в выч. технике. А то в текущем виде, ИМХО, место этой статье где-нибудь на математических форумах, но не на хабре.
Хм, если я все правильно понял, то этот алгоритм хорошо сочетается с алгоритмом Хаффмана в том плане, что придется хранить как-то дерево таким образом, чтобы оно занимало как можно меньше памяти
Спасибо. Элегантно и достаточно просто. Не слышал ни разу про него(или за три года забыл из курса дискретки). Как только увидел формулировку, подумал что это способ компактного хранения структуры деревьев, хотя сходу не представляется какой-то конкретный пример, где это потребовалось бы.

В шаге про завершение алгоритма опечатка, там нет никакой минимальной вершины в не в коде. Тем более ей не может быть 1.


Основной вопрос, если уж алгоритм обсуждать, а за какую сложность можно этот код построить? А как долго приведенный алгоритм восстановления дерева работает? Можно ли его за линейную сложность реализовать?

Sign up to leave a comment.

Articles