Выборка случайных узлов из DAG

Question

У меня есть большой ориентированный ациклический граф (DAG), из которого я хотел бы эффективно нарисовать образец узла в соответствии со следующими критериями:

1. Я указываю фиксированный узел A, который никогда не должен бытьвыборка
2. Узлы, которые прямо или косвенно ссылаются на A, никогда не выбираются
3. Все остальные узлы выбираются с равной вероятностью

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

Есть ли хороший алгоритм для этого?В идеале, не требуя большого количества дополнительной памяти, поскольку DAG большой!

Answer 1

Единственное решение, которое я могу придумать, - это

1. поместить узлы в хэш-набор(пройти их от корня, используя, скажем, первый обход в ширину), O (| E | + | V |)

2. начать с узла A и удалить всех предшественников, пройдя краяназад(снова O (| E | + | V |))

3. выбрать случайный узел из оставшихся узлов.

Это приведет калгоритм O (| E | + | V |) с требованием к памяти O (| V |).

Обратите внимание, что вам не нужно копировать узлы на шаге 1, сохраните только ссылку наузел.

Answer 2

Я ни в коем случае не эксперт в этой области, но, думаю, вам может понадобиться метод выборки по методу Монте-Карло Маркова , такой как Метрополис-Гастингс или Алгоритм выборки Гиббса .

Вы можете найти некоторые примеры кода в Интернете, и вам, возможно, придется изменить код, чтобы он выполнял именно то, что вы хотите.На эту тему есть несколько хороших презентаций, таких как this .

Некоторые программы, которые могут вам помочь:

• JAGS
• OpenBUGS

Я не знаю вашего знакомства с теорией графов, поэтому я не уверен, насколько трудно будет вам это реализовать.

Надеюсь, это было полезно ...