Uogólnione prawo dystrybucyjne - Generalized distributive law

Uogólnione prawo rozdzielcze (GDL) jest uogólnieniem rozdzielność co daje podstawę do ogólnego mijania wiadomości algorytmu. Stanowi syntezę prac wielu autorów zajmujących się teorią informacji , komunikacją cyfrową , przetwarzaniem sygnałów , statystykami i społecznościami sztucznej inteligencji . Prawo i algorytm zostały wprowadzone w pół tutorialu przez Srinivasa M. Aji i Roberta J. McEliece o tym samym tytule.

Wprowadzenie

„Prawo podziału w matematyce to prawo odnoszące się do operacji mnożenia i dodawania, wyrażone symbolicznie, to znaczy, że czynnik jednomianowy jest rozdzielany lub oddzielnie stosowany do każdego członu czynnika dwumianowego , co daje iloczyn ”${\ Displaystyle a * (b + c) = a * b + a * c}$${\ displaystyle a}$${\ displaystyle b + c}$${\ Displaystyle a * b + a * c}$ - Britannica

Jak wynika z definicji, zastosowanie prawa dystrybucyjnego do wyrażenia arytmetycznego zmniejsza liczbę operacji w nim zawartych. W poprzednim przykładzie łączna liczba operacji została zmniejszona z trzech (dwa mnożenia i dodawanie w ) do dwóch (jedno mnożenie i jedno dodawanie ). Uogólnienie prawa dystrybucji prowadzi do powstania dużej rodziny szybkich algorytmów . Obejmuje to algorytm FFT i Viterbi . ${\ Displaystyle a * b + a * c}$${\ Displaystyle a * (b + c)}$

Jest to wyjaśnione w bardziej formalny sposób w poniższym przykładzie:

${\ Displaystyle \ alpha (a, \, b) {\ stackrel {\ mathrm {def}} {=}} \ displaystyle \ sum \ limity _ {c, d, e \ in a} f (a, \, c , \, b) \, g (a, \, d, \, e)}$gdzie i są funkcje o wartościach rzeczywistych i (powiedzmy) ${\ displaystyle f (\ cdot)}$${\ Displaystyle g (\ cdot)}$${\ Displaystyle a, b, c, d, e \ w A}$${\ Displaystyle | A | = q}$

Tu jesteśmy „marginalizację out” zmienne niezależne ( , , i ), aby uzyskać wynik. Kiedy obliczamy złożoność obliczeniową, widzimy, że dla każdej pary istnieją wyrazy należące do trójki, która musi brać udział w ocenie, z każdym krokiem mającym jeden dodatek i jedno mnożenie. Dlatego całkowita liczba potrzebnych obliczeń wynosi . Stąd asymptotyczna złożoność powyższej funkcji . ${\ displaystyle c}$${\ displaystyle d}$${\ displaystyle e}$${\ displaystyle q ^ {2}}$${\ displaystyle (a, b)}$${\ displaystyle q ^ {3}}$${\ displaystyle (c, d, e)}$${\ Displaystyle \ alpha (a, \, b)}$${\ Displaystyle 2 \ cdot q ^ {2} \ cdot q ^ {3} = 2q ^ {5}}$${\ Displaystyle O (n ^ {5})}$

Jeśli zastosujemy prawo dystrybucji do prawej strony równania, otrzymamy:

${\ Displaystyle \ alpha (a, \, b) {\ stackrel {\ mathrm {def}} {=}} \ Displaystyle \ suma \ limity _ {c \ in A} f (a, \, c, \, b ) \ cdot \ sum _ {d, \, e \ in A} g (a, \, d, \, e)}$

Oznacza to, że można go opisać jako produkt, w którym i${\ Displaystyle \ alpha (a, \, b)}$${\ displaystyle \ alpha _ {1} (a, \, b) \ cdot \ alpha _ {2} (a)}$${\ Displaystyle \ alfa _ {1} (a, b) {\ stackrel {\ mathrm {def}} {=}} \ Displaystyle \ suma \ limity _ {c \ in A} f (a, \, c, \ ,b)}$${\ Displaystyle \ alfa _ {2} (a) {\ stackrel {\ mathrm {def}} {=}} \ Displaystyle \ suma \ limity _ {d, \, e \ in A} g (a, \, d ,\,mi)}$

Teraz, gdy mamy do obliczania złożoności obliczeniowej, możemy zobaczyć, że istnieją dodatki w i każda i są mnożenia gdy używamy produktu do oceny . Dlatego całkowita liczba potrzebnych obliczeń wynosi . Stąd asymptotycznej złożoności obliczeń zmniejsza się od . Pokazuje to na przykładzie, że zastosowanie prawa dystrybucji zmniejsza złożoność obliczeniową, która jest jedną z dobrych cech „szybkiego algorytmu”. ${\ displaystyle q ^ {3}}$${\ Displaystyle \ alpha _ {1} (a, \, b)}$${\ displaystyle \ alpha _ {2} (a)}$${\ displaystyle q ^ {2}}$${\ displaystyle \ alpha _ {1} (a, \, b) \ cdot \ alpha _ {2} (a)}$${\ Displaystyle \ alpha (a, \, b)}$${\ Displaystyle q ^ {3} + q ^ {3} + q ^ {2} = 2q ^ {3} + q ^ {2}}$${\ Displaystyle \ alpha (a, b)}$${\ Displaystyle O (n ^ {3})}$${\ Displaystyle O (n ^ {5})}$

Historia

Niektóre z problemów, które wykorzystano do rozwiązania prawa dystrybucji, można pogrupować w następujący sposób

1. Algorytmy dekodowania Algorytm
podobny do GDL był używany przez Gallagera do dekodowania kodów kontroli parzystości o niskiej gęstości. Bazując na pracy Gallagera, Tanner przedstawił wykres Tannera i wyraził pracę Gallagera w formie przekazywania wiadomości. Wykres garbarzy pomógł również wyjaśnić algorytm Viterbiego .

Forney zauważa, że ​​dekodowanie kodów splotowych z maksymalnym prawdopodobieństwem Viterbiego również wykorzystywało algorytmy ogólności podobne do GDL.

2. Algorytm do
przodu i do tyłu Algorytm do przodu i do tyłu pomógł jako algorytm śledzenia stanów w łańcuchu markowa . I to też był używany algorytm GDL jak ogólność

3. Sztuczna inteligencja
Pojęcie drzew skrzyżowań zostało wykorzystane do rozwiązania wielu problemów związanych ze sztuczną inteligencją. Wiele pojęć wykorzystano również w koncepcji eliminacji wiadra .

Problem MPF

MPF lub marginalizacja funkcji iloczynu to ogólny problem obliczeniowy, który jako przypadek specjalny obejmuje wiele klasycznych problemów, takich jak obliczenia dyskretnej transformaty Hadamarda , dekodowanie kodu liniowego z maksymalnym prawdopodobieństwem w kanale bez pamięci i mnożenie łańcucha macierzy . Siła WKL polega na tym, że ma ona zastosowanie do sytuacji, w których uogólnia się dodatki i mnożenia. Przemienne semiring jest dobre ramy dla wyjaśnienia tego zachowania. Jest zdefiniowany na zbiorze z operatorami " " i " ", gdzie i są przemiennymi monoidami i obowiązuje prawo dystrybucji. ${\ displaystyle K}$${\ displaystyle +}$${\ displaystyle.}$${\ displaystyle (K, \, +)}$${\ Displaystyle (K, \ ,.)}$

Niech będą takie zmienne, że gdzie jest skończony zbiór i . Tutaj . Jeśli i niech , , , , i ${\ displaystyle p_ {1}, \ ldots, p_ {n}}$${\ displaystyle p_ {1} \ in A_ {1}, \ ldots, p_ {n} \ in A_ {n}}$${\ displaystyle A}$${\ displaystyle | A_ {i} | = q_ {i}}$${\ Displaystyle i = 1, \ ldots, n}$${\ displaystyle S = \ {i_ {1}, \ ldots, i_ {r} \}}$${\ Displaystyle S \, \ podzbiór \ {1, \ ldots, n \}}$${\ Displaystyle A_ {S} = A_ {i_ {1}} \ razy \ cdots \ razy A_ {i_ {r}}}$${\ Displaystyle p_ {S} = (p_ {i_ {1}}, \ ldots, p_ {i_ {r}})}$${\ Displaystyle q_ {S} = | A_ {S} |}$${\ Displaystyle \ mathbf {A} = A_ {1} \ razy \ cdots \ razy A_ {n}}$${\ Displaystyle \ mathbf {p} = \ {p_ {1}, \ ldots, p_ {n} \}}$

Niech gdzie . Załóżmy, że funkcja jest zdefiniowana jako , gdzie jest przemiennym semirowaniem . Ponadto, są nazywane przez miejscowych domen i jak lokalne jąder . ${\ Displaystyle S = \ {S_ {j} \} _ {j = 1} ^ {M}}$${\ Displaystyle S_ {j} \ podzbiór \ {1, ... \ ,, n \}}$${\ displaystyle \ alpha _ {i}: A_ {S_ {i}} \ rightarrow R}$${\ displaystyle R}$${\ displaystyle p_ {S_ {i}}}$${\ displaystyle \ alpha _ {i}}$

Teraz globalne jądro jest zdefiniowane jako: ${\ Displaystyle \ beta: \ mathbf {A} \ rightarrow R}$${\ Displaystyle \ beta (p_ {1}, ... \ ,, p_ {n}) = \ prod _ {i = 1} ^ {M} \ alfa (p_ {S_ {i}})}$

Definicja problemu MPF : Dla jednego lub więcej indeksów oblicz tabelę wartości - marginalizacji globalnego jądra , czyli funkcji zdefiniowanej jako${\ Displaystyle i = 1, ... \ ,, M}$${\ displaystyle S_ {i}}$${\ displaystyle \ beta}$${\ Displaystyle \ beta _ {i}: A_ {S_ {i}} \ rightarrow R}$${\ Displaystyle \ beta _ {i} (p_ {S_ {i}}) \, = \ Displaystyle \ suma \ limity _ {p_ {S_ {i} ^ {c}} \ in A_ {S_ {i} ^ { c}}} \ beta (p)}$

Tutaj jest uzupełnienie względem i nazywa się funkcją celu lub funkcją celu w . Można zauważyć, że obliczenie funkcji celu w oczywisty sposób wymaga operacji. Dzieje się tak, ponieważ przy obliczaniu funkcji celu potrzebne są dodania i mnożenia . Algorytm GDL, który zostanie wyjaśniony w następnej sekcji, może zmniejszyć tę złożoność obliczeniową. ${\ Displaystyle S_ {i} ^ {c}}$${\ displaystyle S_ {i}}$${\ Displaystyle \ mathbf {\ {} 1, ... \ ,, n \}}$${\ Displaystyle \ beta _ {i} (p_ {S_ {i}})}$${\ displaystyle i ^ {th}}$ ${\ displaystyle S_ {i}}$${\ displaystyle i ^ {th}}$${\ Displaystyle Mq_ {1} q_ {2} q_ {3} \ cdots q_ {n}}$${\ displaystyle q_ {1} q_ {2} \ cdots q_ {n}}$${\ displaystyle (M-1) q_ {1} q_ {2} ... q_ {n}}$${\ displaystyle i ^ {\ text {th}}}$

Poniżej znajduje się przykład problemu MPF. Niech i będą zmiennymi takimi, że i . Tutaj i . Podane funkcje wykorzystujące te zmienne są a i trzeba obliczyć i zdefiniowane jako: ${\ Displaystyle p_ {1}, \, p_ {2}, \, p_ {3}, \, p_ {4},}$${\ displaystyle p_ {5}}$${\ displaystyle p_ {1} \ in A_ {1}, p_ {2} \ in A_ {2}, p_ {3} \ in A_ {3}, p_ {4} \ in A_ {4},}$${\ displaystyle p_ {5} \ in A_ {5}}$${\ displaystyle M = 4}$${\ Displaystyle S = \ {\ {1,2,5 \}, \ {2,4 \}, \ {1,4 \}, \ {2 \} \}}$${\ displaystyle f (p_ {1}, p_ {2}, p_ {5})}$${\ Displaystyle g (p_ {3}, p_ {4})}$${\ Displaystyle \ alpha (p_ {1}, \, p_ {4})}$${\ Displaystyle \ beta (p_ {2})}$

${\ Displaystyle \ alpha (p_ {1}, \, p_ {4}) = \ Displaystyle \ suma \ limity _ {p_ {2} \ w A_ {2}, \, p_ {3} \ w A_ {3} , \, p_ {5} \ in A_ {5}} f (p_ {1}, \, p_ {2}, \, p_ {5}) \ cdot g (p_ {2}, \, p_ {4} )}$

${\ Displaystyle \ beta (p_ {2}) = \ suma \ limity _ {p_ {1} \ in A_ {1}, \, p_ {3} \ in A_ {3}, \, p_ {4} \ in A_ {4}, \, p_ {5} \ in A_ {5}} f (p_ {1}, \, p_ {2}, \, p_ {5}) \ cdot g (p_ {2}, \, p_ {4})}$

Tutaj domeny lokalne i jądra lokalne są zdefiniowane w następujący sposób:

domeny lokalne	jądra lokalne
${\ displaystyle \ {p_ {1}, p_ {2}, p_ {5} \}}$	${\ displaystyle (f (p_ {1}, p_ {2}, p_ {5})}$
${\ displaystyle \ {p_ {2}, p_ {4} \}}$	${\ displaystyle g (p_ {2}, p_ {4})}$
${\ displaystyle \ {p_ {1}, p_ {4} \}}$	${\ displaystyle 1}$
${\ displaystyle \ {p_ {2} \}}$	${\ displaystyle 1}$

gdzie jest funkcją celu i jest funkcją celu. ${\ displaystyle \ alpha (p_ {1}, p_ {4})}$${\ displaystyle 3 ^ {rd}}$${\ Displaystyle \ beta (p_ {2})}$${\ displaystyle 4 ^ {th}}$

Rozważmy inny przykład, w którym i jest funkcją o wartościach rzeczywistych. Teraz rozważymy problem MPF, w którym przemienne semiowanie jest zdefiniowane jako zbiór liczb rzeczywistych ze zwykłym dodawaniem i mnożeniem, a domeny lokalne i jądra lokalne są zdefiniowane w następujący sposób: ${\ Displaystyle p_ {1}, p_ {2}, p_ {3}, p_ {4}, r_ {1}, r_ {2}, r_ {3}, r_ {4} \ in \ {0,1 \ }}$${\ Displaystyle f (r_ {1}, r_ {2}, r_ {3}, r_ {4})}$

domeny lokalne	jądra lokalne
${\ displaystyle \ {r_ {1}, r_ {2}, r_ {3}, r_ {4} \}}$	${\ Displaystyle f (r_ {1}, r_ {2}, r_ {3}, r_ {4})}$
${\ displaystyle \ {p_ {1}, r_ {1} \}}$	${\ Displaystyle (-1) ^ {p_ {1} r_ {1}}}$
${\ displaystyle \ {p_ {2}, r_ {2} \}}$	${\ Displaystyle (-1) ^ {p_ {2} r_ {2}}}$
${\ displaystyle \ {p_ {3}, r_ {3} \}}$	${\ Displaystyle (-1) ^ {p_ {3} r_ {3}}}$
${\ displaystyle \ {p_ {4}, r_ {4} \}}$	${\ Displaystyle (-1) ^ {p_ {4} r_ {4}}}$
${\ displaystyle \ {p_ {1}, p_ {2}, p_ {3}, p_ {4} \}}$	${\ displaystyle 1}$

Odkąd globalne jądro jest zdefiniowane jako produkt lokalnych jąder, tak właśnie jest

${\ Displaystyle F (p_ {1}, p_ {2}, p_ {3}, p_ {4}, r_ {1}, r_ {2}, r_ {3}, r_ {4}) = f (p_ { 1}, p_ {2}, p_ {3}, p_ {4}) \ cdot (-1) ^ {p_ {1} r_ {1} + p_ {2} r_ {2} + p_ {3} r_ { 3} + p_ {4} r_ {4}}}$

a funkcja celu w domenie lokalnej to ${\ displaystyle p_ {1}, p_ {2}, p_ {3}, p_ {4}}$

${\ Displaystyle F (p_ {1}, p_ {2}, p_ {3}, p_ {4}) = \ Displaystyle \ suma \ limity _ {r_ {1}, r_ {2}, r_ {3}, r_ {4}} f (r_ {1}, r_ {2}, r_ {3}, r_ {4}) \ cdot (-1) ^ {p_ {1} r_ {1} + p_ {2} r_ {2 } + p_ {3} r_ {3} + p_ {4} r_ {4}}.}$

To jest transformata Hadamarda funkcji . Stąd widzimy, że obliczenie transformaty Hadamarda jest szczególnym przypadkiem problemu MPF. Więcej przykładów można wykazać, aby udowodnić, że problem MPF tworzy szczególne przypadki wielu klasycznych problemów, jak wyjaśniono powyżej, których szczegóły można znaleźć na ${\ displaystyle f (\ cdot)}$

GDL: algorytm rozwiązywania problemu MPF

Jeśli uda się znaleźć związek między elementami danego zbioru , to można rozwiązać problem MPF w oparciu o pojęcie propagacji przekonań, które jest szczególnym zastosowaniem techniki „przekazywania wiadomości”. Wymagana relacja polega na tym, że dany zestaw domen lokalnych można zorganizować w drzewo połączeń . Innymi słowy, tworzenie wykresów teoretyczną drzewo z elementów jak wierzchołków drzew , na przykład, że dla dowolnych dwóch dowolnych wierzchołki powiedzieć, i gdzie i istnieje krawędź pomiędzy tymi dwoma wierzchołkami, a punkt przecięcia odpowiedniej etykiety, a mianowicie , jest podzbiorem etykiety na każdym wierzchołku na unikalnej ścieżce od do . ${\ displaystyle S}$${\ displaystyle S}$ ${\ displaystyle T}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle i \ neq j}$${\ Displaystyle S_ {i} \ czapka S_ {j}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$

Na przykład,

Przykład 1: rozważ następujące dziewięć domen lokalnych:

1. ${\ displaystyle \ {p_ {2} \}}$
2. ${\ displaystyle \ {p_ {3}, p_ {2} \}}$
3. ${\ displaystyle \ {p_ {2}, p_ {1} \}}$
4. ${\ displaystyle \ {p_ {3}, p_ {4} \}}$
5. ${\ displaystyle \ {p_ {3} \}}$
6. ${\ displaystyle \ {p_ {1}, p_ {4} \}}$
7. ${\ displaystyle \ {p_ {1} \}}$
8. ${\ displaystyle \ {p_ {4} \}}$
9. ${\ displaystyle \ {p_ {2}, p_ {4} \}}$

Dla podanego powyżej zestawu domen lokalnych można zorganizować je w drzewo połączeń, jak pokazano poniżej:

Podobnie, jeśli podany jest inny zestaw podobny do poniższego

Przykład 2: rozważ następujące cztery domeny lokalne:

1. ${\ displaystyle \ {p_ {1}, p_ {2} \}}$
2. ${\ displaystyle \ {p_ {2}, p_ {3} \}}$
3. ${\ displaystyle \ {p_ {3}, p_ {4} \}}$
4. ${\ displaystyle \ {p_ {1}, p_ {4} \}}$

Następnie skonstruowanie drzewa tylko z tymi domenami lokalnymi nie jest możliwe, ponieważ ten zestaw wartości nie ma wspólnych domen, które można umieścić między dowolnymi dwiema wartościami z powyższego zestawu. Jeśli jednak dodasz dwie fikcyjne domeny, jak pokazano poniżej, zorganizowanie zaktualizowanego zestawu w drzewo połączeń również będzie możliwe i łatwe.

5. , 6. ,${\ displaystyle \ {p_ {1}, p_ {2}}$${\ displaystyle p_ {4} \}}$
${\ displaystyle \ {p_ {2}, p_ {3}}$${\ displaystyle p_ {4} \}}$

Podobnie w przypadku tego zestawu domen drzewo połączeń wygląda tak, jak pokazano poniżej:

Algorytm uogólnionego prawa dystrybucji (GDL)

Dane wejściowe: zbiór domen lokalnych.
Wynik: dla danego zestawu domen obliczana jest możliwa minimalna liczba operacji wymaganych do rozwiązania problemu.
Tak więc, jeśli i są połączone krawędzią w drzewie skrzyżowań, to komunikat od do jest zbiorem / tabelą wartości podanych przez funkcję :: . Na początek wszystkie funkcje, tj. Dla wszystkich kombinacji danego drzewa iw danym drzewie, są zdefiniowane tak, aby były identyczne, a gdy dana wiadomość jest aktualizowana, postępuje zgodnie z równaniem podanym poniżej. ${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle v_ {i}}$${\ displaystyle v_ {j}}$${\ displaystyle \ mu _ {i, j}}$${\ Displaystyle A_ {S_ {i} \ nasadka S_ {j}} \ rightarrow R}$${\ displaystyle i}$${\ displaystyle j}$${\ displaystyle \ mu _ {i, j}}$${\ displaystyle 1}$

${\ Displaystyle \ mu _ {i, j} (p_ {S_ {i} \ czapka S_ {j}})}$ = ${\ displaystyle \ sum _ {p_ {S_ {i} \ setminus S_ {j}} \ in A_ {S_ {i} \ setminus S_ {j}}} \ alpha _ {i} (p_ {S_ {i}} ) \ prod _ {{v_ {k} \ operatorname {przym} v_ {i}}, {k \ neq j}} \ mu _ {k, j} (p_ {S_ {k} \ cap S_ {i}} ) (1)}$

gdzie oznacza, że jest to sąsiedni wierzchołek w drzewie. ${\ displaystyle v_ {k} \ operatorname {przym} v_ {i}}$${\ displaystyle v_ {k}}$${\ displaystyle v_ {i}}$

Podobnie każdy wierzchołek ma stan, który jest zdefiniowany jako tabela zawierająca wartości z funkcji.Tak jak w przypadku identycznej inicjalizacji wiadomości do 1, stan jest definiowany jako jądro lokalne , ale za każdym razem, gdy jest aktualizowany, następuje następujące równanie: ${\ displaystyle \ sigma _ {i}: A_ {S_ {i}} \ rightarrow R}$${\ displaystyle v_ {i}}$${\ displaystyle \ alpha (p_ {S_ {i}})}$${\ displaystyle \ sigma _ {i}}$

${\ Displaystyle \ sigma (p_ {S_ {i}}) = \ alfa _ {i} (p_ {S_ {i}}) \ prod _ {v_ {k} \ operatorname {przym} v_ {i}} \ mu _ {k, j} (p_ {S_ {k} \ cap S_ {i}}) (2).}$

Podstawy działania algorytmu

Dla podanego zestawu domen lokalnych jako danych wejściowych dowiadujemy się, czy możemy utworzyć drzewo skrzyżowań, używając zestawu bezpośrednio lub dodając najpierw domeny fikcyjne do zestawu, a następnie tworząc drzewo skrzyżowań, jeśli węzeł konstrukcyjny nie jest możliwy wyjście algorytmu, że nie ma sposobu, aby zmniejszyć liczbę kroków do obliczenia danego problemu równania, ale kiedy już mamy drzewo węzłów, algorytm będzie musiał zaplanować komunikaty i obliczyć stany, robiąc to, możemy wiedzieć, gdzie kroki można zmniejszyć, stąd zostaną omówione poniżej.

Planowanie przekazywania wiadomości i obliczanie stanu

Są dwa szczególne przypadki, o których będziemy tutaj mówić, mianowicie Problem pojedynczego wierzchołka, w którym funkcja celu jest obliczana tylko na jednym wierzchołku, a drugi to Problem wszystkich wierzchołków, w którym celem jest obliczenie funkcji celu na wszystkich wierzchołkach. ${\ displaystyle v_ {0}}$

Zacznijmy od problemu z jednym wierzchołkiem , GDL rozpocznie od skierowania każdej krawędzi w kierunku docelowego wierzchołka . Tutaj wiadomości są wysyłane tylko w kierunku do docelowego wierzchołka. Zwróć uwagę, że wszystkie skierowane wiadomości są wysyłane tylko raz. Wiadomości są rozpoczynane od węzłów liści (gdzie stopień wynosi 1) idą w górę w kierunku wierzchołka docelowego . Wiadomość wędruje od liści do rodziców, a stamtąd do ich rodziców i tak dalej, aż dotrze do wierzchołka docelowego . Wierzchołek docelowy obliczy swój stan tylko wtedy, gdy otrzyma wszystkie wiadomości od wszystkich swoich sąsiadów. Kiedy już mamy stan, mamy odpowiedź i stąd algorytm się kończy. ${\ displaystyle v_ {0}}$${\ displaystyle v_ {0}}$${\ displaystyle v_ {0}}$${\ displaystyle v_ {0}}$

Na przykład, rozważmy drzewo węzłów zbudowane z zestawu domen lokalnych podanych powyżej, tj. Zbioru z przykładu 1,
Teraz tabela zestawieniowa dla tych domen jest (gdzie znajduje się wierzchołek docelowy ). ${\ displaystyle p_ {2}}$

${\ displaystyle {\ text {Okrągła wiadomość lub obliczenia stanu}}}$
${\ Displaystyle 1. \ mu _ {8,4} (p_ {4}) = \ alfa _ {8} (p_ {4})}$
${\ Displaystyle 2. \ mu _ {8,4} (p_ {4}) = \ Sigma _ {p_ {2}} \ alfa _ {9} (p_ {2}, p_ {4})}$
${\ Displaystyle 3. \ mu _ {5,2} (p_ {3}) = \ alfa _ {5} (p_ {3})}$
${\ Displaystyle 4. \ mu _ {6,3} (p_ {1}) = \ Sigma _ {p_ {4}} \ alfa _ {6} (p_ {1}, p_ {4})}$
${\ Displaystyle 5. \ mu _ {7,3} (p_ {1}) = \ alfa _ {7} (p_ {1})}$
${\ Displaystyle 6. \ mu _ {4,2} (p_ {3}) = \ Sigma _ {p_ {4}} \ alfa _ {4} (p_ {3}, p_ {4}). \ mu _ {8,4} (p_ {4}). \ Mu _ {9,4} (p_ {4})}$
${\ Displaystyle 7. \ mu _ {3,1} (p_ {2}) = \ Sigma _ {p_ {1}} \ alfa _ {3} (p_ {2}, p_ {1}). \ mu _ {6,3} (p_ {1}). \ Mu _ {7,3} (p_ {1})}$
${\ Displaystyle 8. \ mu _ {2,1} (p_ {2}) = \ Sigma _ {p_ {3}} \ alfa _ {2} (p_ {3}, p_ {2}). \ mu _ {4,2} (p_ {3}). \ Mu _ {5,2} (p_ {3})}$
${\ Displaystyle 9. \ sigma _ {1} (p_ {2}) = \ alfa _ {1} (p_ {2}). \ mu _ {2,1} (p_ {2}). \ mu _ { 3,1} (p_ {2})}$

W ten sposób złożoność GDL pojedynczego wierzchołka można przedstawić jako

${\ Displaystyle \ Sigma _ {v} d (v) | A_ {S _ {(v)}} |}$ operacje arytmetyczne
Gdzie (Uwaga: wyjaśnienie powyższego równania jest wyjaśnione w dalszej części artykułu) jest etykietą . jest wyższe od (liczba wierzchołków przyległych do V).
${\ Displaystyle S (v)}$${\ displaystyle v}$
${\ Displaystyle d (v)}$${\ displaystyle v}$

Aby rozwiązać problem All-Vertices , możemy zaplanować GDL na kilka sposobów, niektóre z nich to implementacje równoległe, w których w każdej rundzie każdy stan jest aktualizowany, a każda wiadomość jest obliczana i przesyłana w tym samym czasie. W tego typu implementacji stany i komunikaty ustabilizują się po liczbie rund, która jest co najwyżej równa średnicy drzewka. W tym momencie wszystkie stany wierzchołków będą równe żądanej funkcji celu.

Innym sposobem na zaplanowanie GDL dla tego problemu jest implementacja szeregowa, która jest podobna do problemu z pojedynczym wierzchołkiem, z tym wyjątkiem, że nie zatrzymujemy algorytmu, dopóki wszystkie wierzchołki wymaganego zestawu nie otrzymają wszystkich wiadomości od wszystkich sąsiadów i nie obliczą ich stan.
Zatem liczba działań arytmetycznych, których ta implementacja wymaga, to co najwyżej operacje arytmetyczne. ${\ Displaystyle \ Sigma _ {v \ in V} d (v) | A_ {S _ {(v)}} |}$

Konstruowanie drzewa węzłowego

Kluczem do zbudowania drzewa skrzyżowań jest graf domeny lokalnej , który jest kompletnym grafem ważonym z wierzchołkami, tj. Po jednym dla każdej domeny lokalnej, o ciężarze krawędzi zdefiniowanym przez . jeśli , to mówimy, że jest zawarte w . Oznaczona przez (waga drzewa rozpinającego o maksymalnej masie ), która jest zdefiniowana przez ${\ displaystyle G_ {LD}}$${\ displaystyle M}$${\ displaystyle v_ {1}, v_ {2}, v_ {3}, \ ldots, v_ {M}}$${\ displaystyle e_ {i, j}: v_ {i} \ leftrightarrow v_ {j}}$
${\ Displaystyle \ omega _ {i, j} = | S_ {i} \ czapka S_ {j} |}$
${\ displaystyle x_ {k} \ in S_ {i} \ cap S_ {j}}$${\ displaystyle x_ {k}}$${\ displaystyle e_ {i, j}}$${\ displaystyle \ omega _ {max}}$${\ displaystyle G_ {LD}}$

${\ Displaystyle \ omega ^ {*} = \ Sigma _ {i = 1} ^ {M} | S_ {i} | -n}$

gdzie n to liczba elementów w tym zestawie. Aby uzyskać większą jasność i szczegóły, zapoznaj się z nimi.

Twierdzenie o planowaniu

Niech będzie drzewem węzłowym z zestawem wierzchołków i zestawu krawędzi . W tym algorytmie komunikaty są wysyłane w obu kierunkach na dowolnej krawędzi, więc możemy powiedzieć / potraktować zbiór krawędzi E jako zbiór uporządkowanych par wierzchołków. Na przykład z rysunku 1 można zdefiniować w następujący sposób ${\ displaystyle 'T'}$${\ displaystyle 'V'}$${\ displaystyle 'E'}$${\ displaystyle 'E'}$

${\ Displaystyle E = \ {(1,2), (2,1), (1,3), (3,1), (4,2), (2,4), (5,2), ( 2,5), (6,3), (3,6), (7,3), (3,7), (8,4), (4,8), (9,4), (4, 9) \}}$

UWAGA: powyżej podaje wszystkie możliwe wskazówki, jakimi wiadomość może podróżować w drzewie. ${\ displaystyle E}$

Harmonogram GDL jest zdefiniowany jako skończona sekwencja podzbiorów . Co jest ogólnie reprezentowane przez { }, gdzie jest zestaw komunikatów aktualizowanych podczas rundy działania algorytmu. ${\ displaystyle E}$${\ displaystyle {\ mathcal {E}} =}$${\ Displaystyle E_ {1}, E_ {2}, E_ {3}, \ ldots, E_ {N}}$${\ displaystyle E_ {N}}$${\ displaystyle N ^ {th}}$

Po zdefiniowaniu / widziałem kilka zapisów, ujrzymy chcą twierdzenie mówi, Kiedy podano harmonogram , odpowiedni krata wiadomość jako skończonego grafu skierowanego z Vertex zestaw , w którym typowy element jest oznaczony na , a następnie po zakończeniu przekazanie wiadomości, stan na wierzchołku będzie celem zdefiniowanym w ${\ Displaystyle {\ mathcal {E}} = \ {E_ {1}, E_ {2}, E_ {3}, \ ldots, E_ {N} \}}$${\ Displaystyle V \ razy \ {0,1,2,3, \ ldots, N \}}$${\ displaystyle v_ {i} (t)}$${\ Displaystyle t \ in \ {0,1,2,3, \ ldots, N \}}$${\ displaystyle v_ {j}}$${\ displaystyle j ^ {\ text {th}}}$

${\ Displaystyle \ sigma (p_ {S_ {i}}) = \ alfa _ {i} (p_ {S_ {i}}) \ prod _ {v_ {k} \ operatorname {przym} v_ {i}} \ mu _ {k, j} (p_ {S_ {k} \ cap S_ {i}})}$

i jeśli istnieje ścieżka od do${\ displaystyle v_ {i} (0)}$${\ displaystyle v_ {j} (N)}$

Złożoność obliczeniowa

Tutaj staramy się wyjaśnić złożoność rozwiązania problemu MPF liczbą operacji matematycznych wymaganych do obliczenia. tj. Porównujemy liczbę operacji wymaganych przy obliczaniu przy użyciu zwykłej metody (tutaj przez normalną metodę mamy na myśli metody, które nie używają przekazywania komunikatów lub drzew węzłów w krótkich metodach, które nie używają pojęć GDL) i liczbę operacji wykorzystujących uogólnione prawo dystrybucyjne.

Przykład: Rozważmy najprostszy przypadek, w którym musimy obliczyć następujące wyrażenie . ${\ displaystyle ab + ac}$

Naiwna ocena tego wyrażenia wymaga dwóch mnożeń i jednego dodania. Wyrażenie wyrażone za pomocą prawa podziału można zapisać jako prostą optymalizację, która redukuje liczbę operacji do jednego dodania i jednego mnożenia. ${\ displaystyle a (b + c)}$

Podobnie jak w powyższym przykładzie, będziemy wyrażać równania w różnych formach, aby wykonać jak najmniej operacji, stosując GDL.

Jak wyjaśniono w poprzednich sekcjach, rozwiązujemy problem, wykorzystując koncepcję drzew skrzyżowań. Optymalizacja uzyskana przy użyciu tych drzew jest porównywalna z optymalizacją uzyskaną przez rozwiązanie problemu półgrupowego na drzewach. Na przykład, aby znaleźć minimum grupy liczb, możemy zauważyć, że jeśli mamy drzewo i wszystkie elementy znajdują się na dole drzewa, to możemy porównać minimum dwa elementy równolegle, a wynikowe minimum będzie napisane do rodzica. Kiedy ten proces jest propagowany w górę drzewa, minimum grupy elementów zostanie znalezione w katalogu głównym.

Poniżej przedstawiono złożoność rozwiązywania drzewa skrzyżowań za pomocą przekazywania komunikatów

Przepisujemy użyty wcześniej wzór do następującej postaci. To jest równanie wiadomości wysyłanej z wierzchołka v do w

${\ displaystyle \ mu _ {v, w} (p_ {v \ cap w}) = \ suma _ {p_ {v \ setminus w} \ in A_ {S (v) \ setminus S (w)}} \ alfa _ {v} (p_ {v}) \ prod _ {uadjv_ {u \ neq v}} \ mu _ {u, v} (p_ {u \ cap v})}$ ---- równanie wiadomości

Podobnie przepisujemy równanie do obliczania stanu wierzchołka v w następujący sposób

${\ displaystyle \ sigma _ {v} (p_ {v}) = \ alfa _ {v} (p_ {v}) \ prod _ {u \ operatorname {przym} v} \ mu _ {v, w} (p_ {v \ cap w})}$

Najpierw przeanalizujemy problem z jednym wierzchołkiem i założymy, że wierzchołek docelowy jest i stąd mamy jedną krawędź od do . Załóżmy, że mamy krawędź, którą obliczamy za pomocą równania wiadomości. Aby obliczyć wymagania ${\ displaystyle v_ {0}}$${\ displaystyle v}$${\ displaystyle v_ {0}}$${\ displaystyle (v, w)}$${\ displaystyle p_ {u \ cap v}}$

${\ displaystyle q_ {v \ setminus w} -1}$

dodatki i

${\ displaystyle q_ {v \ setminus w} (d (v) -1)}$

mnożenia.

(Reprezentujemy as .) ${\ Displaystyle | A_ {S (v) \ S (w)} |}$${\ displaystyle q_ {v \ setminus w}}$

Ale będzie wiele możliwości, stąd możliwości . Zatem cała wiadomość będzie potrzebna ${\ displaystyle x_ {v \ cap w}}$
${\ Displaystyle q_ {v \ nasadka w} {\ stackrel {\ mathrm {def}} {=}} | A_ {S (v) \ nasadka S (w)} |}$${\ displaystyle p_ {v \ cap w}}$

${\ Displaystyle (q_ {v \ nasadka w}) (q_ {v \ setminus w} -1) = q_ {v} -q_ {v \ nasadka w}}$

dodatki i

${\ Displaystyle (q_ {v \ nasadka w}) q_ {v \ setminus w}. (d (v) -1) = (d (v) -1) q_ {v}}$

mnożenia

Całkowita liczba operacji arytmetycznych wymaganych do wysłania wiadomości w kierunku krawędzi drzewa będzie wynosić ${\ displaystyle v_ {0}}$

${\ displaystyle \ sum _ {v \ neq v0} (q_ {v} -q_ {v \ cap w})}$

dodatki i

${\ displaystyle \ sum _ {v \ neq v0} (d (v) -1) q_ {v}}$

mnożenia.

Po przesłaniu wszystkich wiadomości algorytm kończy się obliczeniem stanu na . Obliczenie stanu wymaga więcej mnożenia. Dlatego liczba obliczeń wymaganych do obliczenia stanu jest podana poniżej ${\ displaystyle v_ {0}}$${\ displaystyle d (v_ {0}) q_ {0}}$

${\ displaystyle \ sum _ {v \ neq v_ {0}} (q_ {v} -q_ {v \ cap w})}$

dodatki i

${\ displaystyle \ sum _ {v \ neq v_ {0}} (d (v) -1) q_ {v} + d (v_ {0}) q_ {v_ {0}}}$

mnożenia

Zatem całkowita suma liczby obliczeń wynosi

${\ Displaystyle \ chi (T) = \ suma _ {v \ in V} d (v) q_ {v} - \ suma _ {e \ in E} q_ {e}}$ ----${\ displaystyle (1)}$

gdzie jest krawędź, a jej rozmiar jest określony przez${\ Displaystyle e = (v, w)}$${\ displaystyle q_ {v \ cap w}}$

Powyższy wzór określa górną granicę.

Jeśli zdefiniujemy złożoność krawędzi jako ${\ Displaystyle e = (v, w)}$

${\ displaystyle \ chi (e) = q_ {v} + q_ {w} -q_ {v \ cap w}}$

Dlatego można zapisać jako ${\ displaystyle (1)}$

${\ displaystyle \ chi (T) = \ suma _ {e \ in E} \ chi (e)}$

Teraz obliczamy złożoność krawędzi dla problemu zdefiniowanego na rysunku 1 w następujący sposób

${\ Displaystyle \ chi (1,2) = q_ {2} + q_ {2} q_ {3} -q_ {2}}$

${\ Displaystyle \ chi (2,4) = q_ {3} q_ {4} + q_ {2} q_ {3} -q_ {3}}$

${\ displaystyle \ chi (2,5) = q_ {3} + q_ {2} q_ {3} -q_ {3}}$

${\ displaystyle \ chi (4,8) = q_ {4} + q_ {3} q_ {4} -q_ {4}}$

${\ displaystyle \ chi (4,9) = q_ {2} q_ {4} + q_ {3} q_ {4} -q_ {4}}$

${\ Displaystyle \ chi (1,3) = q_ {2} + q_ {2} q_ {1} -q_ {2}}$

${\ Displaystyle \ chi (3,7) = q_ {1} + q_ {1} q_ {2} -q_ {1}}$

${\ Displaystyle \ chi (3,6) = q_ {1} q_ {4} + q_ {1} q_ {2} -q_ {1}}$

Całkowita złożoność będzie znacznie niska w porównaniu z metodą bezpośrednią. (Tutaj przez metodę bezpośrednią mamy na myśli metody, które nie wykorzystują przekazywania wiadomości. Czas potrzebny przy użyciu metody bezpośredniej będzie równoważny z obliczeniem wiadomości w każdym węźle i czasem obliczenia stanu każdego z węzłów). ${\ displaystyle 3q_ {2} q_ {3} + 3q_ {3} q_ {4} + 3q_ {1} q_ {2} + q_ {2} q_ {4} + q_ {1} q_ {4} -q_ { 1} -q_ {3} -q_ {4}}$

Teraz rozważymy problem obejmujący wszystkie wierzchołki, w którym wiadomość będzie musiała zostać wysłana w obu kierunkach, a stan musi zostać obliczony na obu wierzchołkach. To by wymagało, ale dzięki obliczeniom wstępnym możemy zmniejszyć liczbę mnożeń do . Oto stopień wierzchołka. Przykład: Jeżeli istnieje zestaw z liczbami. Możliwe jest obliczenie wszystkich iloczynów d funkcji z co najwyżej mnożenia, a nie oczywistości . Robimy to poprzez wstępne obliczenie ilości, a to wymaga mnożenia. Wtedy, jeśli oznacza iloczyn wszystkich, oprócz tego, że mamy i tak dalej, będziemy potrzebować kolejnego mnożenia tworzącego sumę${\ Displaystyle O (\ suma _ {v} d (v) d (v) q_ {v})}$${\ Displaystyle 3 (d-2)}$${\ displaystyle d}$${\ displaystyle (a_ {1}, \ ldots, a_ {d})}$${\ displaystyle d}$${\ displaystyle d-1}$${\ displaystyle a_ {i}}$${\ Displaystyle 3 (d-2)}$${\ Displaystyle d (d-2)}$${\ Displaystyle b_ {1} = a_ {1}, b_ {2} = b_ {1} \ cdot a_ {2} = a_ {1} \ cdot a_ {2}, b_ {d-1} = b_ {d -2} \ cdot a_ {d-1} = a_ {1} a_ {2} \ cdots a_ {d-1}}$${\ displaystyle c_ {d} = a_ {d}, c_ {d-1} = a_ {d-1} c_ {d} = a_ {d-1} \ cdot a_ {d}, \ ldots, c_ {2 } = a_ {2} \ cdot c_ {3} = a_ {2} a_ {3} \ cdots a_ {d}}$${\ Displaystyle 2 (d-2)}$${\ displaystyle m_ {j}}$${\ displaystyle a_ {i}}$${\ displaystyle a_ {j}}$${\ Displaystyle m_ {1} = c_ {2}, m_ {2} = b_ {1} \ cdot c_ {3}}$${\ displaystyle d-2}$${\ Displaystyle 3 (d-2)}$

Niewiele możemy zrobić, jeśli chodzi o konstrukcję drzewa węzłów, poza tym, że możemy mieć wiele drzew rozpinających o maksymalnej masie i powinniśmy wybierać drzewo rozpinające z najmniejszą liczbą, a czasami może to oznaczać dodanie domeny lokalnej w celu obniżenia połączenia złożoność drzewa. ${\ displaystyle \ chi (T)}$

Może się wydawać, że GDL jest poprawne tylko wtedy, gdy domeny lokalne można wyrazić jako drzewo połączeń. Ale nawet w przypadkach, gdy istnieją cykle i liczba iteracji, komunikaty będą w przybliżeniu równe funkcji celu. Eksperymenty z algorytmem Gallagera – Tannera – Wiberga dla kodów kontroli parzystości o niskiej gęstości potwierdziły to twierdzenie.

Bibliografia