제로 - 억압 BDD의 교차 - ZDD를 사용하여 다항식 구현

Question

other question의 주석에서 제안한대로 ZDD를 사용하여 단 변량 다항식을 구현하려고합니다.

S. Minato (here을 다운로드 할 수 있음)의 문서를 읽었지만 이러한 ZDD에서 작업을 구현하는 방법을 이해할 수 없습니다.

다항식은 x^(2^i)을 변수로 사용하여 표현할 수 있습니다. 예를 들어 x^5 + x^3 + x은 x^(2^i) 변수마다 노드를 만들고 함께 곱한 "1- 에지"변수와 함께 추가 된 "0- 에지"변수와 연결하면 그래프를 쉽게 얻을 수 있습니다. x^4x^1 + x^2x^1 + x^1으로 다시 쓸 수 있습니다 그 다항식을 나타냅니다. ZDDs 그래프에서 어떤 조건을 적용 이런 종류의 그래프 (자세한 내용 미나 제 및 판독 위키의 page BDD 계열)에

는 계수 마찬가지로 2의 제곱의 합 (예 5 = 2^2 + 2^0 등을 사용하여 표현 될 수있다 모든 2^i은 변수이고 노드는 동일한 방식으로 1 및 0 에지로 연결됩니다.

내 문제는 두 개의 ZDD를 추가하는 알고리즘입니다. 알고리즘은 매우 간단 보인다 F와 G (ZDDs가) 공통 조합이없는 경우

, 추가 (F + G)는 단지 그들을 병합하여 완료 수 있습니다. 이들이 몇 가지 일반적인 조합을 포함 할 때, 우리는 다음 공식을 계산한다. (F + G) = S + (Cx2), 여기서 C = F ∩ G, S = (F U G) \ C. 이 프로세스를 반복하면 결국 개의 일반적인 조합이 모두 소모되고 절차는 으로 완료됩니다.

"C"와 "S"를 어떻게 효율적으로 찾을 수 있습니까?

작성자는 곱셈을위한 코드를 제공하지만 이전 알고리즘이 구현되면 코드는 실제로 간단한입니다. 그리고 이러한 알고리즘은 제공되지 않기 때문에 곱셈은 "쓸모없는"것입니다.

"병합"ZDD의 개념은 변수의 순서가 일관되어야한다는 사실을 고려해도 그래프를 병합하는 방법은 하나 뿐이며이를 유지하는 규칙이 있습니다 주문은 아마 충분히 간단하다 (나는 아직 공식화하지 않았지만 이것들이 무엇인지에 대한 대략적인 생각을 가지고있다).

Answer 1

"병합"이있는 경우 미나토는 유니온 (algorithm)을 의미합니다. 당신도의 예에서이를 볼 수 있습니다

4 * y  = { { 2^2, y } } 
x   = { { x } } 
4 * y + x = { { 2^2, y }, { x } } 

아이디어를 인 내부 세트는 제품을 대표하고 단지 OR (노동 조합 일명 또는 병합) 경우 전체 ZDD은 일부에 해당 제품의 합계를 나타내는, 그래서 더 많은 세트가 효과적으로 추가됩니다.

완전 합산 알고리즘은 익숙한 비트 추가 알고리즘과 동일한 (A xor B) + 2 * (A and B) (재귀 적으로)을 수행하지만 xor은 (A or B) without (A and B)으로 작성되었습니다.공통 조합이없는 경우 단순히 노동 조합을 복용하는 이유 또한 분명하게

은 OK입니다 - A and B가 비어있는 경우, A xor B는 A or B과 동일하고는 "수행"제로이다.

OR, AND, XOR 및 BUTNOT에 대한 알고리즘은 The Art of Computer Programming 4 권, section 7.1.4에 자세히 설명되어 있습니다 (199 번 질문에 대한 답이 적절 함). 그들 모두에 대한 일반적인 생각은 v 맨 위의 변수 인 경우 모두 하찮게 발견되는 (별도 변수 v없이 변수 v 모든 세트 모든 세트가 나타내는 두 개의 하위 그래프를 고려하는 것이있다 하나 또는 양쪽 모두의 인수에서 하위 및 상위 하위 또는 입력 자체로) 결과를 결합합니다.

Union(F, G) = 
    if (F = ∅) return G 
    if (G = ∅) return F 
    if (F = G) return F 
    if (cache contains "F ∪ G" or "G ∪ F") 
    return cached value 

    if (F.v = G.v) result = MakeNode(F.v, F.lo ∪ G.lo, F.hi ∪ G.hi) 
    if (F.v > G.v) result = MakeNode(G.v, F ∪ G.lo, G.hi) 
    if (F.v < G.v) result = MakeNode(F.v, F.lo ∪ G, F.hi) 

    cache result as "F ∪ G" 
    return result 

Intersect(F, G) = 
    if (F = ∅ or G = ∅) return ∅ 
    if (F = G) return F 
    if (cache contains "F ∩ G" or "G ∩ F") 
    return cached value 

    if (F.v = G.v) result = MakeNode(F.v, F.lo ∩ G.lo, F.hi ∩ G.hi) 
    if (F.v > G.v) result = F ∩ G.lo 
    if (F.v < G.v) result = F.lo ∩ G 

    cache result as "F ∩ G" 
    return result