Как я могу случайным образом генерировать деревья с ограниченной высотой?

9

Для проекта, над которым я работаю, я должен генерировать случайные остовные деревья с ограниченной высотой.

В основном я делаю следующее: 1) Создаю связующее дерево. 2) Проверяю осуществимость, если возможно, сохраняю его.

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

2) Предположим, что есть особая вершина vсеNTер, Для каждой вершиныvдлина пути от v в ВсеNTер должно быть меньше, чем δ, где δ это заданный параметр.

Есть ли лучший (умный) способ сделать это?

PS Я забыл указать другое ограничение (моя ошибка): степень вершин также должна быть ограничена.

Arman
источник
Я не уверен, правильно ли я понял. В первом шаге вы удаляете край случайно или так, чтобы высота дерева (возможно) была уменьшена?
Саша
Я случайно добавляю и удаляю края.
Арман
Не могли бы вы выбрать случайные деревья с кратчайшим путем ? Это все упрощает
Ярослав Булатов
у вас есть какие-либо расходы по краям? Вы ищете остовное дерево с высотойδа минимальная стоимость? Как писал @pboothe, вы можете использовать BFS и все. Единственная проблема заключается в том, что BFS использует слишком много памяти. Если вы заботитесь о затратах, вы можете попробовать алгоритм в википедии для евклидовых минимальных остовных деревьев ( en.wikipedia.org/wiki/Euclidean_minimum_spanning_tree ). Имеет время работыО(NжурналN) с О(N) пространства.
Маркос Вильягра
Итак, у вашей задачи есть три ограниченные величины: высота дерева, степень каждой вершины и расстояние от v_center, верно? Только ограниченное ограничение степени само по себе делает проблему NP-сложной, но я полагаю, вы ищете метод, который, скорее всего, быстро найдет решение, а не точный алгоритм.
Джагадиш

Ответы:

7

Я работал над связанными деревьями ограниченной глубины несколько лет назад, они действительно интересны. Некоторые из моих коллег придумали алгоритмы передачи сообщений, которые отлично поработали, но я не могу найти ни один из их доступных кодов. Мы написали это в физическом стиле здесь: http://iopscience.iop.org/1742-5468/2009/12/P12010/ . Они сказали мне, что это также работает с границами степени, хотя это не попало в газету.

Подход, который вы предлагаете, который я бы назвал Марковской цепью Монте-Карло, часто является конкурентом подхода передачи сообщений. Если вас интересует выборка приблизительно равномерно случайным образом из набора охватывающих деревьев ограниченной степени с ограниченной глубиной данного графа, я предлагаю изменить ваш подход, чтобы использовать «мягкие» границы. Т.е. вместо отклонения краевого свопа, который заставляет дерево нарушать границу глубины, принимайте его, но с меньшей вероятностью, чем своп, который не нарушает границу. Если у вас есть параметр, который управляет тем, насколько ниже эта вероятность, вы можете сделать так, чтобы ограничение, нарушающее конфигурации, становилось все менее и менее вероятным до тех пор, пока вы не найдете практически выполнимое решение, которое является почти равномерно случайным.

Большой вопрос в том, как долго вам нужно запустить цепь. Поскольку остовное дерево со степенью не более 2 является гамильтоновым путем, следует ожидать, что любая общая граница будет экспоненциальной по размеру графа. Но, возможно, интересующие вас графики в некотором роде особенные.

Авраам Лексман
источник
2
Подробнее, плюс фильм: healthyalgorithms.wordpress.com/2010/12/23/…
Авраам
3

Если ваша проблема состоит в том, чтобы равномерно выбрать остовное дерево из набора S, где S множество всех покрывающих деревьев высоты самое большее часдля некоторого ввода час, тогда ваша стратегия сработает (т.е. выберите случайное связующее дерево и проверьте, не больше ли оно высоты час).

Однако я не уверен, что описанный вами алгоритм будет генерировать случайное связующее дерево. Я бы рекомендовал вместо этого взглянуть на стандартные алгоритмы. Существует два алгоритма: алгоритм Уилсона и алгоритм Олдос-Бродера. Вы можете посмотреть здесь . Существует более новый (приближенный) алгоритм, но он довольно сложный.

Кроме того, может быть способ генерировать это связующее дерево с ограниченной высотой напрямую. Но я никогда не слышал о таких алгоритмах.

Дан
источник
1

Используйте поиск в ширину! Сделайте BFS из каждой вершины графа, выберите результирующее дерево наименьшей высоты. BFS всегда находит путь от корня ко всем остальным вершинам с наименьшим количеством прыжков.

Питер Бут
источник
Вы определенно правы. Мы начали работать с BFS, но это не сработало из-за ограничения по степени на вершинах. Я забыл упомянуть об этом ограничении (моя ошибка): степень вершин в генерируемом дереве также должна быть ограниченной. Ваш ответ правильный с текущим вопросом, но я думаю, что должен отредактировать свой вопрос.
Арман
Тогда ваша проблема, скорее всего, в том, что NPC уменьшен из Степенного связанного остовного дерева - en.wikipedia.org/wiki/Degree-constrained_spanning_tree
Питер Бут