是否在DAG的所有拓扑类型上使用随机算法? [英] random algorithm over all topological sorts of a DAG?

问题描述

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

Does anyone know of a random algorithm for generating a topological sort of a DAG, where each invocation of the algorithm has a non-zero probability of generating every valid topological sort of the DAG.

至关重要的是，该算法不能排除任何有效的拓扑类别，因为它是较大算法的一部分，如果有足够的迭代次数，则必须证明该算法能够探索给定DAG的所有拓扑类别.

It's crucial that the algorithm does not preclude any valid topological sort, because it's part of a larger algorithm that, given enough iterations, must be demonstrably capable of exploring all topological sorts of a given DAG.

有人知道这种算法是否已经开发出来吗?

Does anyone know if such an algorithm has been developed?

(或者，如果有人知道可以保证生成给定DAG的 all 拓扑类型的合理有效算法，我可能可以对其进行调整以得到我需要的东西.)

(Alternatively, if anyone knows of a reasonably efficient algorithm that's guaranteed to generate all topological sorts of a given DAG, I can probably tweak that to get what I need.)

推荐答案

考虑涵盖所有可能的拓扑类别的含义有助于进行思考.在拓扑排序过程中，有时会从一组有效的候选者中选择要处理的候选者，每个候选者都是有效的选择.根据实现TS的方式，可能是从一组边沿中跟随的边，每个边都是候选(出站边的集合)，或者选择哪个节点作为起点(汇/源的集合)，或者是随机选择的起始节点.

It helps to think in terms of what it means to say that you cover all possible topological sorts. During the topological sort, there is a point where you select a candidate to process from a subset of valid candidates, each of which is a valid choice. Depending on the way you implement the TS, it could be edge to follow from a set of edges each of which is a candidate (set of outgoing edges) or which node to select as the starting point (set of sinks/sources) or the randomly chosen start node.

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

What you want is to ensure that the selection process produces a distribution which does not show an overwhelming biased towards a particular subset of the candidates.

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

You can bias your selection process to achieve a more uniform distribution without running for infinite time. For example, you can assign a weight to each candidate of a set. Every time a candidate is selected you reduce the weight of that candidate by an amount "X" and increase the weight of the other candidates by an amount "X/(k-1)" where k is the size of the set of candidate set. This will result in a greater chance that a candidate which was not selected is selected in the next iteration, and result in a quicker convergence to a more uniform distribution.

这篇关于是否在DAG的所有拓扑类型上使用随机算法?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！