DAG 的所有拓扑排序的随机算法？

Question

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

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

有人知道这样的算法是否已经被开发出来了吗？

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

Answer 1

这有助于思考“涵盖所有可能的拓扑类别”的含义。在拓扑排序过程中，有一个点，您可以从有效候选的子集中选择一个候选进行处理，每个候选都是有效的选择。根据实现 TS 的方式，它可能是从一组边开始的边，其中每条边都是候选(传出边的集合)，或者选择哪个节点作为起点(接收器/源的集合)或随机选择起始节点。

您想要的是确保选择过程产生的分布不会表现出对特定候选人子集的压倒性偏见。

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