random - DAG的所有拓扑类型的随机算法？

Question

有谁知道用于生成 DAG 的拓扑排序的随机算法，其中算法的每次调用具有生成 DAG 的每个有效拓扑排序的非零概率。

至关重要的是，该算法不排除任何有效的拓扑排序，因为它是一个更大算法的一部分，如果有足够的迭代，必须证明能够探索给定 DAG 的所有拓扑排序。

有谁知道是否已经开发了这样的算法？

（或者，如果有人知道一种相当有效的算法，可以保证生成给定 DAG 的所有拓扑类型，我可能会对其进行调整以获得我需要的东西。）

Answer 1

它有助于思考说你涵盖了所有可能的拓扑类型意味着什么。在拓扑排序过程中，您会从有效候选者的子集中选择要处理的候选者，每个候选者都是有效选择。根据您实现 TS 的方式，它可能是从一组边缘跟随的边缘，每个边缘都是候选（一组传出边缘）或选择哪个节点作为起点（一组汇/源）或随机选择的起始节点。

您想要的是确保选择过程产生的分布不会显示出压倒性地偏向候选人的特定子集。

您可以调整您的选择过程以实现更均匀的分布，而无需运行无限时间。例如，您可以为集合中的每个候选者分配权重。每次选择候选人时，您都会将该候选人的权重减少“X”的数量，并将其他候选人的权重增加“X/(k-1)”的数量，其中 k 是候选集的大小. 这将导致在下一次迭代中选择未被选中的候选者的机会更大，并导致更快地收敛到更均匀的分布。