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

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

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

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

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


graph directed-acyclic-graphs algorithm language-agnostic
person mikera    schedule 19.08.2010    source источник
comment
Насколько велик он, есть ли у вас ограничения памяти и можно ли дешево найти ссылающиеся узлы?   -  person Eiko    schedule 19.08.2010
comment
p.s. Обоснование этого состоит в том, что я хочу случайным образом добавить новое ребро к A, но мне нужно избегать образования каких-либо циклов ...   -  person mikera    schedule 19.08.2010
comment
@Eiko Я ожидаю около миллиона узлов, поэтому ограничения памяти / кеша потенциально могут стать проблемой. Ссылающиеся узлы в настоящее время нельзя найти дешево, хотя добавление обратных указателей может быть вариантом.   -  person mikera    schedule 19.08.2010
comment
можно ли перемещать края в обратном направлении? (т.е. являются ли узлы дважды связанными)   -  person aioobe    schedule 19.08.2010
comment
В настоящее время узлы не связаны с двойной / обратной связью, хотя их добавление может быть вариантом, если это необходимо для обеспечения эффективного выполнения.   -  person mikera    schedule 19.08.2010

Ответы (2)


arrow_upward
2
arrow_downward

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

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

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

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

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

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

person aioobe    schedule 19.08.2010

arrow_upward
0
arrow_downward

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

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

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

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

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

person The Alchemist    schedule 19.08.2010
comment
Спасибо за интересные ссылки! Однако я больше люблю не столько общую теорию и инструменты выборки, сколько конкретный алгоритм выборки DAG. - person mikera; 19.08.2010
comment
Извини за это! Я думаю, что у aioobe есть довольно хорошее решение, которое представляет собой базовое решение цепи Монте-Карло Маркова, IIRC. Если у вас большой график, выбор хорошего генератора случайных чисел для шага 3 aioobe будет становиться все более важным. - person The Alchemist; 19.08.2010