случайный алгоритм для всех топологических видов DAG?

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

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

Кто-нибудь знает, был ли разработан такой алгоритм?

(В качестве альтернативы, если кто-нибудь знает достаточно эффективный алгоритм, который гарантированно генерирует все топологические виды данной DAG, я, вероятно, смогу настроить его, чтобы получить то, что мне нужно.)

6
задан Christian Convey 10 July 2012 в 20:06
поделиться