激活 AND 节点和 OR 节点

Question

考虑一个包含 AND 节点和 OR 节点的有向图。只有当进入它的所有输入边都被激活时，AND 节点才会被激活。如果至少其中一个 in 边被激活，则 OR 节点被激活。如何设计一个高效的算法来决定是否可以激活所有节点？我想到了一些天真的算法，但它需要 O(n^3) 时间。我还假设没有内边的顶点被激活 initially.I 相信 n^3 不是一个有效的算法，而且我缺少一些方法。标记问题可能有解决方案的域。

Answer 1

您可以对图进行预处理以计算每个节点的入度。

将所有入度为0的节点入栈，并准备一个数组A，其中包含每个节点的激活计数（初始等于0）。

然后执行如下伪代码

visited = set(stack)
while stack:
   node = stack.pop()
   for dest in node.neighbours():
      A[dest] += 1
      if ((Type[dest]==AND and A[dest]==indegree[dest]) or
          (Type[dest]==OR and A[dest]>0)):
         if node not in visited:
            visited.add(node)
            stack.append(dest)

这将最多访问每条边和每个节点一次，因此具有线性复杂度。

完成该过程后，已访问包含激活节点集。

Answer 2

维护一组 A 个已激活节点、一个 Q 个节点队列和 C 每个节点的入边计数器。

从计算入边开始：

for each n in nodes {
    for each n2 adjacent to n {
        C[n2] += 1
    }
}

然后用没有入边的节点初始化Q:

for each n in nodes {
    if C[n] == 0 {
        add n to Q
    }
}

现在重复这个过程，直到队列为空：

take q from Q
for each n adjacent to q {
   if n is in A { continue }
   if n is OR {
      add n to A
      add n to Q
   } else { // n must be AND
      C[n] -= 1
      if C[n] is 0 {
          add n to A
          add n to Q
      }
   }
}

[这是一种拓扑排序的变体，解决了OR和AND节点之间的差异]。

当此进程终止时，集合 A 包含所有激活的节点。

运行时间为 O(V+E)，其中 V 是图中的节点数，E 是边数。

Answer 3

在O(n) 中是可能的。这是一个可能的算法。

n节点总数

s已经激活的节点总数

a数组表示节点n是否已经激活

c 数组，用于计算节点 n

的传入边数

遍历节点，如果它们没有传入边，则用它调用你的传播函数，例如propagate(i);.

如果s == n所有节点都已激活。

propagate 函数的伪代码：

function propagate(idx) {
    if (a[idx]) // is node activated already
        return; // return because node was already propagated
    a[idx] = true; // activate
    s++; // increase the number of activated nodes
    for (var j = 0; j < outEdges[idx].length; j++) { // iterate through the outgoing edges
        var idx2 = outEdges[idx][j]; // the node the edge is pointing to
        if (isOrNode[idx2]) {
            propagate(idx2);
        } else { // AND node
            c[idx2]++; // increase the count of incoming activated edges
            if (inEdges[idx2].length == c[idx2]) // all incoming edges have been activated
                propagate(idx2);
        }
    }
}

激活 AND 节点和 OR 节点

Activating AND nodes and OR nodes

algorithm

workflow

time-complexity

computation-theory

graph-algorithm