使用测试函数从拓扑顺序恢复原始 DAG

Question

让 T 成为一个 DAG（有向无环图），其中树的每个节点都可以处于状态 0 或 1。

我得到一个列表，它表示 DAG 的拓扑顺序，其中所有节点的状态均为 0。我有布尔函数

toggle

，它作用于具有以下语义的节点：

• 如果节点

  n

  的状态为 1，则

  toggle(n)

  将其状态更改为 0 并返回

  true

  。
• 如果节点

  n

  的状态为 0，则当且仅当原始 DAG 上的所有直接和间接父节点现在状态也为 1 时，

  toggle(n)

  才会将其状态更改为 1 并返回

  true

  。否则，

  toggle(n)

  返回

  false

  并且节点的状态不会改变。

在我的问题中，我有列表，但没有原始 DAG，我想通过使用函数

toggle(n)

作为测试函数来恢复原始 DAG。

到目前为止我想到的每个解决方案都有某种形式的组合爆炸。有没有多项式时间的解决方案？这个问题或类似的问题有名称吗？

我最初的方法涉及

toggle(n)

所有节点并“存储”成功的节点。这样我就得到了原始 DAG 的“根源”，但我想出的任何其他东西都涉及某种“尝试每种可能的组合”的组合爆炸。

Answer 1

伪代码：

upstreams = defaultdict(set)  # node -> upstream nodes
upstream_set = set()

while len(upstream_set) < n:
    for current_node not in all_nodes not in upstream_set:
        # at each iteration, find the minimal upstream coverage for current_node

        set_all_upstream_set_nodes_to_one()
        flip current_node to one()
        if current_node flip is unsuccessful:  # returned false
            continue  # upstream is not yet complete for this node

        # minimize upstream for current_node
        for upstream_node in upstream_set:
            flip upstream_node to zero
            flip current node back and forth
            if flip is unsuccessful:
                upstreams[current_node].add(upstream_node)
                flip upstream_node back to one
            # otherwise, upstream_node is not relevant for current_node

        # found minimal upstream coverage
        upstream_set.add(current_node)
        

所得的

upstreams

应足以进行拓扑排序。

复杂度：外部

while+for

最多应为 O(n^2)（最坏情况：单行），内部

for

总体应为 O(n) - O(n^3)。