Для проекта, над которым я работаю, я должен генерировать случайные остовные деревья с ограниченной высотой.
В основном я делаю следующее: 1) Создаю связующее дерево. 2) Проверяю осуществимость, если возможно, сохраняю его.
1) Начиная с минимального связующего дерева (Прима или Крускала), я добавляю несуществующее ребро, и это создает цикл, я обнаруживаю этот цикл и удаляю одно из ребер этого цикла, которое дает мне новое связующее дерево, и я продолжаю с это связующее дерево, добавив новый край ...
2) Предположим, что есть особая вершина , Для каждой вершиныдлина пути от в должно быть меньше, чем , где это заданный параметр.
Есть ли лучший (умный) способ сделать это?
PS Я забыл указать другое ограничение (моя ошибка): степень вершин также должна быть ограничена.
Ответы:
Я работал над связанными деревьями ограниченной глубины несколько лет назад, они действительно интересны. Некоторые из моих коллег придумали алгоритмы передачи сообщений, которые отлично поработали, но я не могу найти ни один из их доступных кодов. Мы написали это в физическом стиле здесь: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Они сказали мне, что это также работает с границами степени, хотя это не попало в газету.
Подход, который вы предлагаете, который я бы назвал Марковской цепью Монте-Карло, часто является конкурентом подхода передачи сообщений. Если вас интересует выборка приблизительно равномерно случайным образом из набора охватывающих деревьев ограниченной степени с ограниченной глубиной данного графа, я предлагаю изменить ваш подход, чтобы использовать «мягкие» границы. Т.е. вместо отклонения краевого свопа, который заставляет дерево нарушать границу глубины, принимайте его, но с меньшей вероятностью, чем своп, который не нарушает границу. Если у вас есть параметр, который управляет тем, насколько ниже эта вероятность, вы можете сделать так, чтобы ограничение, нарушающее конфигурации, становилось все менее и менее вероятным до тех пор, пока вы не найдете практически выполнимое решение, которое является почти равномерно случайным.
Большой вопрос в том, как долго вам нужно запустить цепь. Поскольку остовное дерево со степенью не более 2 является гамильтоновым путем, следует ожидать, что любая общая граница будет экспоненциальной по размеру графа. Но, возможно, интересующие вас графики в некотором роде особенные.
источник
Если ваша проблема состоит в том, чтобы равномерно выбрать остовное дерево из набораS , где S множество всех покрывающих деревьев высоты самое большее час для некоторого ввода час , тогда ваша стратегия сработает (т.е. выберите случайное связующее дерево и проверьте, не больше ли оно высоты час ).
Однако я не уверен, что описанный вами алгоритм будет генерировать случайное связующее дерево. Я бы рекомендовал вместо этого взглянуть на стандартные алгоритмы. Существует два алгоритма: алгоритм Уилсона и алгоритм Олдос-Бродера. Вы можете посмотреть здесь . Существует более новый (приближенный) алгоритм, но он довольно сложный.
Кроме того, может быть способ генерировать это связующее дерево с ограниченной высотой напрямую. Но я никогда не слышал о таких алгоритмах.
источник
Используйте поиск в ширину! Сделайте BFS из каждой вершины графа, выберите результирующее дерево наименьшей высоты. BFS всегда находит путь от корня ко всем остальным вершинам с наименьшим количеством прыжков.
источник