在DAG的所有拓扑类型上的随机算法？

Question

有没有人知道用于生成DAG的拓扑排序的随机算法,其中算法的每次调用都具有生成DAG的每个有效拓扑类型的非零概率.

至关重要的是,算法不排除任何有效的拓扑排序,因为它是更大算法的一部分,在给定足够的迭代的情况下,必须能够证明能够探索给定DAG的所有拓扑类型.

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

(或者,如果有人知道一个合理有效的算法可以保证生成给定DAG的所有拓扑类型,我可以调整它以获得我需要的东西.)

Answer 1

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

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

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