AND 노드 및 OR 노드 활성화

Question

AND 노드와 OR 노드가있는 유향 그래프를 고려하십시오. AND 노드는 내부의 모서리가 활성화 된 경우에만 활성화됩니다. OR 노드는 적어도 하나의 에지가 활성화되어 있으면 활성화됩니다. 효율적인 알고리즘을 설계하는 방법 모든 노드를 활성화 할 수 있는지 결정하려면? 몇 가지 간단한 알고리즘을 생각해 봤지만 O (n^3) 시간이 걸립니다. 나는 또한 그들에 가장자리가없는 vertex가 초기에 활성화된다고 가정하고있다. 나는 n^3이 효율적인 알고리즘이 될 수 없다고 생각하며, 내가 놓친 몇 가지 방법이 있다고 생각한다. 문제가있는 도메인에 태그를 지정하면 해결책이 될 수 있습니다.

Answer 1

그래프를 전처리하여 각 노드의 학위를 계산할 수 있습니다.

학위가 0 인 모든 노드를 스택에 추가하고 각 노드의 활성화 횟수 (처음에는 0)를 포함하는 배열 A를 준비합니다.

그런 다음이 최대 한 번 각 모서리와 각 노드를 방문, 그래서 선형 복잡도를해야합니다

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) 

다음 의사 코드을 수행하십시오.

프로세스를 완료하면 visited에는 활성화 된 노드 집합이 포함됩니다.

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 노드 N은 수신 수를 카운트

c 배열 활성화되었는지 나타내는

a 어레이 활성화 된 노드들의 합의 총 개수 노드 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); 
     } 
    } 
}