Uogólnione prawo dystrybucji

prawo dystrybucji (GDL) jest uogólnieniem właściwości dystrybucyjnej , która daje początek ogólnemu algorytmowi przekazywania komunikatów . Jest syntezą prac wielu autorów zajmujących się teorią informacji , komunikacją cyfrową , przetwarzaniem sygnałów , statystyką i sztuczną inteligencją . Prawo i algorytm zostały wprowadzone w półsamouczku autorstwa Srinivasa M. Aji i Roberta J. McEliece o tym samym tytule.

Wstęp

„Prawo rozdzielności w matematyce to prawo odnoszące się do operacji mnożenia i dodawania, wyrażone symbolicznie, $\ Displaystyle a * (b + c) = a * b + a * c}$${\ displaystyle b + c}$ to znaczy czynnik jednomianowy $do$ rozprowadzany lub oddzielnie stosowany do każdego składnika czynnika dwumianowego , co daje iloczyn ${\ Displaystyle a * b + a * c}$ " - Britannica

Jak widać z definicji, zastosowanie prawa rozdzielności do wyrażenia arytmetycznego zmniejsza liczbę operacji w nim zawartych. W $do$ mnożenia i dodawania w dwóch (jedno mnożenie i ${\ Displaystyle a * (b + c)}$ ). Uogólnienie prawa dystrybucji prowadzi do dużej rodziny szybkich algorytmów . Obejmuje to FFT i Viterbiego .

Wyjaśniono to w bardziej formalny sposób w poniższym przykładzie:

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

Tutaj „marginalizujemy” zmienne niezależne ( $displaystyle e}$$,$ mi { $)$ aby uzyskać wynik. Kiedy obliczamy złożoność obliczeniową, widzimy, że dla każdej pary $(a, b)}$$\ Displaystyle$$}$$\ displaystyle q ^$ {2} } ^ $,\,b)}$ terminy ze względu na tryplet $)$ w ocenie $\ Displaystyle \$ z każdym krokiem mającym jedno dodawanie i jedno mnożenie. Dlatego całkowita liczba potrzebnych obliczeń wynosi ${\ Displaystyle 2 \ cdot q ^ {2} \ cdot q ^ {3} = 2q ^ {5}}$ . Stąd asymptotyczna złożoność powyższej funkcji wynosi ${\ Displaystyle O (n ^ {5})}$ .

Jeśli zastosujemy prawo rozdzielności do RHS równania, otrzymamy:

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

$\$ to, że $b )$ produkt gdzie ${\ Displaystyle \ alpha _ { 1} (a, b) {\ stackrel {\ operatorname {def} }{=}} \ Displaystyle \ sum \ limits _ {c \ in A} f (a, \, c, \, b)}$ i $\ Displaystyle \ alfa _ {2} (a) {\ stackrel {\ operatorname {def}} {=}} \ Displaystyle \ sum \limits _{d,\,e\in A}g(a,\,d,\,e)}$

Teraz, kiedy obliczamy złożoność obliczeniową, widzimy, że istnieją $w$ α $)}$$\ Displaystyle \ alpha _ {1} (a, \$$iloczynu$ i ${\ Displaystyle \ alpha _ {2} (a)}$ i istnieją mnożenia, gdy używamy ${\ Displaystyle \ alpha _ {1} (a, \, b) \ cdot \ alpha _ {2} (a)}$ oceniać ${\ Displaystyle \ alpha (a ,\,b)}$ . Dlatego całkowita liczba potrzebnych obliczeń to ${\ Displaystyle q ^ {3} + q ^ {3} + q ^ {2} = 2q ^ {3} +q^{2}}$ . Stąd asymptotyczna złożoność obliczania $\ styl wyświetlania O(n^{5})}$ się do $Displaystyle$$O (n ^$ z . Pokazuje to na przykładzie, że zastosowanie prawa rozdzielności zmniejsza złożoność obliczeniową, co jest jedną z dobrych cech „szybkiego algorytmu”.

Historia

Niektóre problemy, do rozwiązania których wykorzystano prawo 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. Opierając się na pracy Gallagera, Tanner przedstawił wykres Tannera i przedstawił pracę Gallagera w formie przekazywania wiadomości. Wykres garbarzy pomógł również w wyjaśnieniu algorytmu Viterbiego .

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

2. Algorytm przód-tył Algorytm przód-tył pomógł jako algorytm śledzenia stanów w łańcuchu Markowa . I to również zostało użyte w algorytmie GDL jak ogólność

3. Sztuczna inteligencja Pojęcie drzew skrzyżowań zostało wykorzystane do rozwiązania wielu problemów w sztucznej inteligencji. Również koncepcja eliminacji kubełków wykorzystywała wiele koncepcji.

Problem z MPFem

MPF lub marginalizacja funkcji produktu to ogólny problem obliczeniowy, który jako szczególny przypadek obejmuje wiele klasycznych problemów, takich jak obliczanie dyskretnej transformaty Hadamarda , dekodowanie kodu liniowego o maksymalnej wiarygodności w kanale bez pamięci i mnożenie łańcucha macierzy . Siła WKL polega na tym, że odnosi się ona do sytuacji, w których dodawanie i mnożenie są uogólnione. Semiring przemienny to dobre ramy do wyjaśnienia tego zachowania. Jest zdefiniowany na zbiorze z operatorami " ${\ Displaystyle$$+}$ " i " ${\ Displaystyle.}$ " gdzie ${\ Displaystyle (K, \, +)} i ( K , + ) {\ Displaystyle (K, \,$ ) $przemiennymi$ i prawo .

Niech ${\ Displaystyle p_ {1}, \ ldots, p_ {n}}$ będą zmiennymi takimi, że ${\ Displaystyle p_ {1} \ w A_ {1}, \ ldots, p_ {n} \ w A_ {n}}$$skończonym$ jest zbiorem i ${\ Displaystyle | A_ {i} | = q_ {i}}$ . Tutaj ${\ Displaystyle i = 1, \ ldots, n}$ . $\ {i_ {1}, \ ldots, i_ {r} \}}$ = i ${\ Displaystyle S \, \ podzbiór \ {1, \ ldots, n \}}$ , niech ${\ Displaystyle A_ {S} = A_ {i_ {1}} \ razy \ cdots \ razy A_ { ja_ {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}}$ , p ${p} = \ {p_ {1}, \ ldots, p_ {n} \}}$

Niech ${\ Displaystyle S = \ {S_ {j} \} _ {j = 1} ^ {M}}$ gdzie ${\ Displaystyle S_ {j} \ podzbiór \ {1, ... \, n \}}$ . $_$ funkcja $.$ gdzie półpierścieniem _ _ Również $.$ nazywane domenami lokalnymi $_$ _ _ _

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

Definicja problemu MPF : Dla jednego lub więcej wskaźników ${\ Displaystyle i = 1, ... \,, M}$ , oblicz tabelę wartości ${\ Displaystyle S_ {i}}$ - marginalizacja globalnego jądra , ${\ Displaystyle S_ {i}}$ S ja jest funkcją ${\ Displaystyle \ beta _ {i}: A_ {S_ {i}} \ rightarrow R}$ zdefiniowana jako ${\ Displaystyle \ beta _ {i} (p_ {S_ {i}}) \ = \ Displaystyle \ suma \ limity _ {p_ {S_ {i} ^ {c}} \ w A_ { S_{i}^{c}}}\beta (p)}$

Tutaj ${\ Displaystyle S_ {i} ^ {c}}$ jest dopełnieniem ${\ Displaystyle S_ {i}}$ w odniesieniu do $n \}}$ i ${\ Displaystyle \ beta _ {i} (p_ {S_ {i}} )}$ nazywa się funkcją celu $lub funkcją celu w S ja t$ godz { \ $}$ . Można zauważyć, że obliczenie funkcji celu w oczywisty sposób wymaga $\ Displaystyle$${1} q_ {2} q_$ operacji. $1$ istnieją i ${\ Displaystyle (M-1) q_ {1} q_ {2}... q_ {n}}$ mnożenia potrzebne do obliczenia funkcji celu ${\ Displaystyle i ^ {\ tekst {th}}}$ . Algorytm GDL, który wyjaśniono w następnej sekcji, może zmniejszyć tę złożoność obliczeniową.

Poniżej przedstawiono przykład problemu MPF. p ${\ Displaystyle p_ {1}, \, p_ {2}, \, p_ {3}, \, p_ {4},}$ p $\ Displaystyle p_ {5}}$ być zmiennymi takimi, że ${\ Displaystyle p_ {1} \ w A_ {1}, p_ {2} \ w A_ {2}, p_ {3} \ w A_ {3}, p_ {4} \ w A_ {4},}$ i ${\ Displaystyle p_ {5} \ w A_ {5}}$ . ${\ Displaystyle M = 4}$ i $\ {\ {1, 2,5\},\{2,4\},\{1,4\},\{2\}\}}$ = . Podane funkcje wykorzystujące te zmienne to ${\ Displaystyle f (p_ {1}, p_ {2}, p_ {5})}$ i ${\ displaystyle g ( p_ {3}, p_ {4})}$ i musimy obliczyć ${\ Displaystyle \ alpha (p_ {1}, \ p_ {4})}$ i ${\ Displaystyle \ beta (p_ {2})}$ zdefiniowane jako:

${\ Displaystyle \alpha (p_{1},\,p_{4})=\displaystyle \sum \limits _{p_{2}\in A_{2},\,p_{3}\in A_{3},\, p_{5}\in A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_{4})}$

${ \displaystyle \beta (p_{2})=\sum \limits _{p_{1}\in A_{1},\,p_{3}\in A_{3},\,p_{4}\in A_ {4},\,p_{5}\w A_{5}}f(p_{1},\,p_{2},\,p_{5})\cdot g(p_{2},\,p_ {4})}$

Tutaj domeny lokalne i lokalne jądra 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 $)$ celu i ${2})}$${\ α ( p 1 , p 4 ) {$$} displaystyle \$$celu$ p_ jest

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

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}$

Teraz, ponieważ globalne jądro jest zdefiniowane jako produkt lokalnych jąder, tak 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 jest ${\ Displaystyle p_ {1}, p_ {2}, p_ {3}, p_ {4}}$

${\ Displaystyle F (p_ {1}, p_ {2}, p_ {3}, p_ {4}) = \ Displaystyle \ suma \ ograniczenia _ {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 ${\ Displaystyle f (\ cdot)}$ . Widzimy więc, że obliczenie transformaty Hadamarda jest szczególnym przypadkiem problemu MPF. Można wykazać więcej przykładów, aby udowodnić, że problem MPF stanowi szczególne przypadki wielu klasycznych problemów, jak wyjaśniono powyżej, których szczegóły można znaleźć pod adresem

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 specjalnym zastosowaniem techniki „przekazywania wiadomości”. Wymagana relacja polega na tym, że dany zestaw domen lokalnych można zorganizować w drzewo połączeń . Innymi $}$ teoretyczne drzewo grafów z elementami jako $wierzchołkami$ drzewa , tak że dla dowolnych dwóch dowolnych wierzchołków powiedzmy $displaystyle v_$$i$ } i ${\ Displaystyle v_ {j}}$ gdzie ${\ Displaystyle i \ neq j}$ i istnieje krawędź między tymi dwoma wierzchołkami, a następnie przecięcie odpowiednich etykiet, a mianowicie ${\ Displaystyle S_ {i} \ cap S_ {j}}$ , jest podzbiorem etykiety na każdym wierzchołku na unikalnej ścieżce od ${\ displaystyle v_ {i}}$ do ${\ displaystyle v_ {j}}$ .

Na przykład,

Przykład 1: Rozważmy 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 powyższego zestawu domen lokalnych można zorganizować je w drzewo połączeń, jak pokazano poniżej:

Podobnie Jeśli podany jest inny zestaw, taki jak poniższy

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} \}}$

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

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

Podobnie dla tych zestawów domen, drzewo połączeń wygląda tak, jak pokazano poniżej:

Algorytm uogólnionego prawa dystrybucji (GDL).

Dane wejściowe: zestaw domen lokalnych. Wynik: Dla podanego zbioru dziedzin obliczana jest możliwa minimalna liczba operacji wymaganych do rozwiązania problemu. Tak więc, jeśli ${$ krawędzią w drzewie połączeń, to wiadomość od $i}}$$\ displaystyle v_ {i}$ do ${\ Displaystyle v_ {j}}$ to zbiór / tabela wartości podanych przez funkcję: ${\ Displaystyle \ mu _ {i, j}}$ : ${\ Displaystyle A_ {S_{i}\cap S_{j}}\rightarrow R}$ . Na $początek$ wszystkie funkcje, tj. dla wszystkich $są$$w$ drzewie , jako ${\ displaystyle 1}$ i kiedy dana wiadomość jest aktualizowana, jest zgodna z równaniem podanym poniżej.

${\ Displaystyle \ mu _ {i, j} (p_ {S_ {i} \ czapka S_ {j}})}$ = ${\ Displaystyle \ suma _ {p_ {S_ {i} \setminus S_{j}}\in A_{S_{i}\setminus S_{j}}}\alpha _{i}(p_{S_{i}})\prod _{{v_{k}\nazwa operatora { adj} v_{i}},{k\neq j}}\mu _{k,j}(p_{S_{k}\cap S_{i}})(1)}$

gdzie ${\ Displaystyle v_ {k} \ operatorname {przym.} v_ {i}}$ oznacza, że ${\ displaystyle v_ {k}}$ jest sąsiednim wierzchołkiem do ${\ displaystyle v_ {i} }$ w drzewie.

Podobnie każdy wierzchołek ma stan, który jest zdefiniowany jako tabela zawierająca wartości z funkcji ${\ Displaystyle \ sigma _ {i}: A_ {S_ {i}} \ rightarrow R$ } jak komunikaty inicjują się $(p_ {S_ {i}})}$ na 1, stan definiuje się jako jądro lokalne $) {\ Displaystyle \$ ale za każdym razem ${\ Displaystyle \ sigma _ {i}}$ zostaje zaktualizowany, jest zgodny z następującym równaniem:

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

Podstawowe działanie algorytmu

Dla danego zestawu domen lokalnych jako danych wejściowych sprawdzamy, czy możemy utworzyć drzewo połączeń, używając bezpośrednio zestawu lub dodając najpierw fikcyjne domeny do zestawu, a następnie tworząc drzewo połączeń, jeśli budowa węzła nie jest możliwa, wtedy wyjście algorytmu, że nie ma sposobu na zmniejszenie liczby kroków do obliczenia danego problemu z równaniem, ale kiedy mamy drzewo połączeń, algorytm będzie musiał zaplanować komunikaty i obliczyć stany, wykonując to, możemy wiedzieć, gdzie kroki można zmniejszyć, stąd zostanie to omówione poniżej.

Szeregowanie przekazywania wiadomości i obliczanie stanu

Istnieją dwa szczególne przypadki, o których będziemy tutaj mówić, a mianowicie $problem$ pojedynczego wierzchołka , w którym funkcja celu jest obliczana tylko w jednym wierzchołku, drugi to problem wszystkich wierzchołków , w którym celem jest obliczenie funkcja celu we wszystkich wierzchołkach.

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

Na przykład rozważmy drzewo połączeń zbudowane z zestawu domen lokalnych podanych powyżej, tj. Zestaw z przykładu 1. Teraz tabela planowania dla tych domen to (gdzie wierzchołek docelowy to ${\ displaystyle p_ {2}}$ } .

${\ Displaystyle {\ tekst {Okrągły komunikat lub obliczenie 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})}$

Zatem złożoność GDL z pojedynczym wierzchołkiem 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) ${\ displaystyle S (v)}$ to etykieta ${\ displaystyle v}$ . $)}$$v$ to stopień ( tj. liczba wierzchołków przylegających do v)

Aby rozwiązać problem wszystkich wierzchołków , możemy zaplanować GDL na kilka sposobów, niektóre z nich to implementacja równoległa, w której w każdej rundzie każdy stan jest aktualizowany, a każdy komunikat jest obliczany i przesyłany 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 drzewa. W tym momencie wszystkie wszystkie stany wierzchołków będą równe żądanej funkcji celu.

Innym sposobem zaplanowania GDL dla tego problemu jest implementacja szeregowa, która jest podobna do problemu pojedynczego wierzchołka, z tą różnicą, że nie zatrzymujemy algorytmu, dopóki wszystkie wierzchołki wymaganego zestawu nie otrzymają wszystkich komunikatów od wszystkich swoich sąsiadów i obliczą ich państwo. Zatem liczba działań arytmetycznych wymaganych przez tę implementację wynosi co najwyżej ${\ Displaystyle \ Sigma _ {v \ w V} d (v) | A_ {S_ {(v)}} |}$ operacje arytmetyczne.

Konstruowanie drzewa połączeń

Kluczem do skonstruowania drzewa skrzyżowań jest graf domeny lokalnej $displaystyle M}$$M {\$${\ Displaystyle v_ {1}, v_ {2}, v_ {3}, \ ldots, v_ {M}}$ grafem ważonym z wierzchołkami tj. jeden dla każdej domeny lokalnej, mający wagę krawędzi ${\ Displaystyle e_ {i, j}: v_ {i} \ leftrightarrow v_ {j}}$ zdefiniowany przez ${\ Displaystyle \ omega _ {i, j} = | S_ {i} \ cap S_ {j} |}$ . jeśli ${\ Displaystyle x_ {k} \ w S_ {i} \ cap S_ {j}}$${\ Displaystyle e_ {i, j}}$$to$ mówimy, jest zawarte w . Oznaczony przez ${\ Displaystyle \ omega _ {max}}$$, który jest$ waga drzewa rozpinającego o maksymalnej wadze przez .

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

gdzie n to liczba elementów w tym zbiorze. Aby uzyskać więcej jasności i szczegółów, zapoznaj się z nimi.

Twierdzenie o szeregowaniu

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

${ \ 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 )\}}$

$Powyżej$ : podano wszystkie możliwe kierunki, w których wiadomość może podróżować w drzewie.

Harmonogram GDL jest zdefiniowany jako skończona $sekwencja$ . Który jest ogólnie reprezentowany przez ${\ Displaystyle {\ mathcal {E}} =}$ { $ldots, E_ {N}}$${\ Displaystyle E_ {1}, E_ {2}, E_ {3} ,$$jest$$zbiorem$ gdzie komunikatów aktualizowanych podczas algorytmu.

Po zdefiniowaniu / obejrzeniu kilku notacji zobaczymy, że twierdzenie mówi: Kiedy otrzymamy harmonogram ${\ Displaystyle {\ mathcal {E}} = \ {E_{1},E_{2},E_{3},\ldots ,E_{N}\}}$ , odpowiednia krata wiadomości jako graf skończony skierowany ze zbiorem wierzchołków ${\ Displaystyle V \ razy \ {0,1,2,3, \ ldots, N \}}$ , w którym typowy element jest oznaczony przez ${\ Displaystyle v_ {i} (t )}$ dla ${\ Displaystyle t \ in \ {0,1,2,3, \ ldots, N \}}$ , Następnie po zakończeniu przekazywania wiadomości stan w wierzchołku ${\ Displaystyle v_ {j}}$ będzie celem zdefiniowanym w $\ Displaystyle j ^ {\ tekst {th}}}$

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

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

Złożoność obliczeniowa

Tutaj staramy się wyjaśnić złożoność rozwiązania problemu MPF pod względem liczby operacji matematycznych wymaganych do obliczeń. tj. Porównujemy liczbę operacji wymaganych przy obliczaniu przy użyciu metody normalnej (tutaj przez metodę normalną rozumiemy metody, które nie wykorzystują przekazywania komunikatów lub drzew połączeń w metodach krótkich, które nie wykorzystują koncepcji GDL) i liczbę operacji wykorzystujących uogólnione prawo dystrybucji.

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 przy użyciu prawa rozdzielności można zapisać jako $prostą$ , która zmniejsza liczbę operacji do jednego

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

Jak wyjaśniono w poprzednich sekcjach, rozwiązujemy problem, używając koncepcji 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 zaobserwować, że jeśli mamy drzewo i wszystkie elementy znajdują się na dole drzewa, możemy porównać minimum dwóch elementów 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 korzeniu.

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

Przepisujemy formułę używaną wcześniej do następującej postaci. To jest eqn dla wiadomości, która ma być wysłana 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)}} \alpha _{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\nazwa operatora {przym.} v}\mu _{v,w}(p_{v\cap w})}$

Najpierw przeanalizujemy problem pojedynczego wierzchołka i założymy, że docelowy wierzchołek to ${\ displaystyle v_ {0}}$$v_ {0}}$ a zatem mamy jedną krawędź od v $displaystyle$ . Załóżmy $, że$ mamy krawędź obliczamy wiadomość za Aby obliczyć wymaga ${\ displaystyle p_ {u \ cap v}}$

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

dodatki i

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

mnożenia.

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

${\ Displaystyle q_ {v \ cap w} {\ stackrel {\ operatorname {def}}} {=}} | A_ {S (v) \ cap S (w)} |} możliwości p v$ będzie $_$ = ∩ $p_ {v\cap w}}$ . W ten sposób cała wiadomość będzie potrzebować

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

dodatki i

${\ Displaystyle (q_ {v \ cap 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 \ suma _ {v \ neq v0} (q_ {v} -q_ {v \ czapka w})}$

dodatki i

${\ Displaystyle \ suma _ {v \ neq v0} (d (v) -1) q_ {v}}$

mnożenia.

Gdy wszystkie komunikaty zostaną przesłane, algorytm kończy się obliczeniem stanu w. Obliczenie stanu wymaga $v_ {0}) q_ {0}}$ ) $($ mnożenia. Zatem liczba obliczeń wymaganych do obliczenia stanu jest podana jak poniżej

${\ Displaystyle \ suma _ {v \ neq v_ {0}} (q_ {v} -q_ {v \ czapka w})}$

dodatki i

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

mnożenia

Zatem całkowita liczba obliczeń wynosi

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

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

Powyższy wzór daje nam górną granicę.

Jeśli zdefiniujemy złożoność krawędzi jako mi = $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 \ w E} \ chi (e)}$

Obliczymy teraz 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}}$

${\ Displaystyle 3q_ {2} q_$ + , co jest znacznie niższe w porównaniu z metodą bezpośrednią. (Tutaj przez metodę bezpośrednią rozumiemy metody, które nie wykorzystują przekazywania komunikatów. Czas potrzebny przy użyciu metody bezpośredniej będzie równoważny obliczeniu komunikatu w każdym węźle i czasowi obliczenia stanu każdego z węzłów.)

Teraz rozważymy problem wszystkich wierzchołków, w którym wiadomość będzie musiała zostać wysłana w obu kierunkach, a stan musi zostać obliczony w obu wierzchołkach. Zajęłoby to $) d (v) q_ {v})}$ v liczba mnożeń do ${\ Displaystyle 3 (d-2)}$ . Tutaj $wierzchołka$ . Np .: Jeśli istnieje zestaw z liczbami $\ Displaystyle (a_ {1}, \ ldots, a_ {d}$$)$ . Możliwe jest obliczenie wszystkich iloczynów d $\ displaystyle a_$ za $i}}$ { $}$${\ Displaystyle 3 (d-2$ mnożenia zamiast oczywistych ${\ Displaystyle d (d-2)}$ . Robimy to poprzez wstępne obliczenie wielkości ${\ 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}}$ i ${\ 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}}$ to zajmuje ${\ Displaystyle 2 (d-2)} .$ mnożenia Wtedy jeśli $}$ iloczyn wszystkich ${\ Displaystyle a_$$}$ za ${\ Displaystyle m_ {1} = c_ {2}, m_ {2} = b_ {1} \ cdot c_ {3}}$ mamy i tak dalej będzie potrzebował kolejnego ${\ Displaystyle d-2}$ mnożenia dające sumę ${\ Displaystyle 3 (d-2)}$

Niewiele możemy zrobić, jeśli chodzi o konstrukcję drzewa rozpinającego, z wyjątkiem tego, że możemy mieć wiele drzew rozpinających o maksymalnej wadze i powinniśmy wybrać drzewo rozpinające z najmniejszą liczbą χ ( T ) {\ Displaystyle \ $}$ a czasami może to oznaczać dodanie domeny lokalnej w celu zmniejszenia złożoności drzewa połączeń.

Może się wydawać, że GDL jest poprawny tylko wtedy, gdy domeny lokalne można wyrazić jako drzewo połączeń. Ale nawet w przypadkach, w których 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.