algorithm - 找到 DAG 的 k 个随机拓扑类型

Question

我想要一个可以返回 k (k>=1) 随机拓扑类型的 DAG 的函数。大多数图形库中的内置算法只有一个返回一个拓扑排序的函数（topological_sort(G)）或一个返回所有拓扑排序的函数（all_topological_sorts(G)）。

我尝试过的一个选项是首先生成 all_topological_sorts(G) 并从中随机选择 k 个结果。但是当 G 很大（>20 个节点）时，函数 all_topological_sorts(G) 的时间复杂度太高了。

如果我调整函数 topological_sort(G) 以允许它找到随机拓扑排序。我可以多次重复这个过程。每次它返回一个结果，如果它与以前的结果不同，我将它添加到返回列表中。但是，当图 G 有 N 个节点时，这意味着它可能有最大 M 个结果（M = N 的排列）。如果 M>k，但实际可能的拓扑排序是 M'<k。因此，我可能会陷入无限循环，试图满足 k 结果的要求，这是不可能的。

那么，是否有一种更智能、更有效的算法来找到 DAG 的 k 个不同的随机拓扑类型？

标签： algorithmgraphtopological-sort

Answer 1

这是一个简单的方法。

如果你采用像卡恩算法这样的算法，你通常在一个节点上有一组选择。您所做的就是拥有一组部分拓扑排序，为每个排序添加一个节点，为每个选择分支并复制它们。如果超过k，则遍历集合并选择其中的一个随机子集k。重复。

前几个选择将快速增加排序数量。如果少于k总数，您将找到它们。如果有超过k你的随机修剪将导致找到k。

也就是说，请注意，这并不能找到所有具有相同可能性的拓扑排序。为什么不？假设在某个时候您可以选择添加v或w下一步。如果添加vthen w, x, y, 和z可能在下一个节点中。如果没有，只有v可能。如果你选择一个随机排序，它更有可能v去那里而不是w. 但是在进行修剪时，您同样可能会选择v或w。:-(

我指出缺陷是因为你应该意识到这一点，而不是因为我反对我的算法。您可以通过将每个排序向前运行几个步骤来减少偏差，随机挑选一个孙子来确定这个节点应该是什么，然后重复。这种“前瞻”策略将显着减少偏差，但不会消除偏差。