सामान्यीकृत वितरण नियम

सामान्यीकृत वितरण कानून (जीडीएल) वितरण संपत्ति का एक सामान्यीकरण है जो एक सामान्य संदेश देना एल्गोरिदम को जन्म देता है। यह सूचना सिद्धांत, डिजिटल संचार, संकेत आगे बढ़ाना , सांख्यिकी और कृत्रिम बुद्धिमत्ता समुदायों में कई लेखकों के काम का संश्लेषण है। कानून और एल्गोरिदम को इसी शीर्षक के साथ श्रीनिवास एम. अजी और रॉबर्ट मैकएलीस|रॉबर्ट जे. मैकएलीस द्वारा एक अर्ध-ट्यूटोरियल में पेश किया गया था।

परिचय

गणित में वितरणात्मक कानून गुणा और जोड़ की संक्रियाओं से संबंधित कानून है, जिसे प्रतीकात्मक रूप से कहा गया है, $a*(b+c)=a*b+a*c$; वह है, एकपदी कारक $a$ द्विपद गुणनखंड के प्रत्येक पद पर वितरित किया जाता है, या अलग से लागू किया जाता है $b+c$, जिसके परिणामस्वरूप उत्पाद प्राप्त होता है $a*b+a*c$- ब्रिटानिका

जैसा कि परिभाषा से देखा जा सकता है, एक अंकगणितीय अभिव्यक्ति में वितरणात्मक कानून को लागू करने से इसमें संक्रियाओं की संख्या कम हो जाती है। पिछले उदाहरण में संक्रियाओं की कुल संख्या तीन से कम हो गई (दो गुणा और एक जोड़)। $a*b+a*c$) से दो (एक गुणा और एक जोड़) $a*(b+c)$). वितरणात्मक कानून के सामान्यीकरण से तेज़ एल्गोरिदम का एक बड़ा परिवार तैयार होता है। इसमें फास्ट फूरियर ट्रांसफॉर्म और विटर्बी एल्गोरिदम शामिल हैं।

इसे नीचे दिए गए उदाहरण में अधिक औपचारिक तरीके से समझाया गया है:

$\alpha (a,\,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c,d,e\in A}f(a,\,c,\,b)\,g(a,\,d,\,e)$ कहाँ $f(\cdot )$ और $g(\cdot )$ वास्तविक-मूल्यवान कार्य हैं, $a,b,c,d,e\in A$ और $|A|=q$ (कहना)

यहां हम स्वतंत्र चरों को हाशिए पर रख रहे हैं ($c$, $d$, और $e$) परिणाम प्राप्त करने के लिए. जब हम कम्प्यूटेशनल जटिलता की गणना कर रहे हैं, तो हम इसे प्रत्येक के लिए देख सकते हैं $q^{2}$ के जोड़े $(a,b)$, वहाँ हैं $q^{3}$ त्रिक के कारण शर्तें $(c,d,e)$ जिसके मूल्यांकन में भाग लेने की आवश्यकता है $\alpha (a,\,b)$ प्रत्येक चरण में एक जोड़ और एक गुणा होता है। इसलिए, आवश्यक गणनाओं की कुल संख्या है $2\cdot q^{2}\cdot q^{3}=2q^{5}$. इसलिए उपरोक्त फ़ंक्शन की स्पर्शोन्मुख जटिलता है $O(n^{5})$.

यदि हम वितरण नियम को समीकरण के आरएचएस पर लागू करते हैं, तो हमें निम्नलिखित मिलता है:

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

इसका अर्थ यह है कि $\alpha (a,\,b)$ एक उत्पाद के रूप में वर्णित किया जा सकता है $\alpha _{1}(a,\,b)\cdot \alpha _{2}(a)$ कहाँ $\alpha _{1}(a,b){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{c\in A}f(a,\,c,\,b)$ और $\alpha _{2}(a){\stackrel {\mathrm {def} }{=}}\displaystyle \sum \limits _{d,\,e\in A}g(a,\,d,\,e)$ अब, जब हम कम्प्यूटेशनल जटिलता की गणना कर रहे हैं, तो हम देख सकते हैं कि वहाँ हैं $q^{3}$ में परिवर्धन $\alpha _{1}(a,\,b)$ और $\alpha _{2}(a)$ प्रत्येक और वहाँ हैं $q^{2}$ जब हम उत्पाद का उपयोग कर रहे होते हैं तो गुणन $\alpha _{1}(a,\,b)\cdot \alpha _{2}(a)$ मूल्यांकन करना $\alpha (a,\,b)$. इसलिए, आवश्यक गणनाओं की कुल संख्या है $q^{3}+q^{3}+q^{2}=2q^{3}+q^{2}$. इसलिए गणना की स्पर्शोन्मुख जटिलता $\alpha (a,b)$ तक कम कर देता है $O(n^{3})$ से $O(n^{5})$. यह एक उदाहरण से पता चलता है कि वितरण कानून लागू करने से कम्प्यूटेशनल जटिलता कम हो जाती है जो कि तेज़ एल्गोरिदम की अच्छी विशेषताओं में से एक है।

इतिहास

कुछ समस्याएँ जिन्हें हल करने के लिए वितरणात्मक कानून का उपयोग किया गया, उन्हें निम्नानुसार समूहीकृत किया जा सकता है

1. डिकोडिंग एल्गोरिदम
कम घनत्व समता-जांच कोड को डिकोड करने के लिए गैलेजर द्वारा एक जीडीएल जैसे एल्गोरिदम का उपयोग किया गया था। गैलागर के काम के आधार पर टान्नर ने टान्नर ग्राफ पेश किया और गैलागर के काम को संदेश पासिंग फॉर्म में व्यक्त किया। टेनर्स ग्राफ़ ने विटरबी एल्गोरिथम को समझाने में भी मदद की।

फ़ॉर्नी द्वारा यह देखा गया है कि विटर्बी के कन्वेन्शनल कोड की अधिकतम संभावना डिकोडिंग में जीडीएल जैसी व्यापकता के एल्गोरिदम का भी उपयोग किया जाता है।

2. फॉरवर्ड-बैकवर्ड एल्गोरिथम
फॉरवर्ड बैकवर्ड एल्गोरिदम ने मार्कोव श्रृंखला में राज्यों को ट्रैक करने के लिए एक एल्गोरिदम के रूप में मदद की। और इसमें भी सामान्यता की तरह जीडीएल के एल्गोरिदम का उपयोग किया गया था

3. कृत्रिम बुद्धिमत्ता
एआई में कई समस्याओं को हल करने के लिए जंक्शन पेड़ों की अवधारणा का उपयोग किया गया है। इसके अलावा बाल्टी उन्मूलन की अवधारणा में कई अवधारणाओं का उपयोग किया गया।

एमपीएफ समस्या

एमपीएफ या उत्पाद फ़ंक्शन को हाशिए पर रखना एक सामान्य कम्प्यूटेशनल समस्या है जिसमें विशेष मामले में कई शास्त्रीय समस्याएं शामिल हैं जैसे कि असतत हैडामर्ड परिवर्तन की गणना, मेमोरी-कम चैनल (संचार) पर एक रैखिक कोड की अधिकतम संभावना डिकोडिंग, और मैट्रिक्स श्रृंखला गुणन। जीडीएल की शक्ति इस तथ्य में निहित है कि यह उन स्थितियों पर लागू होता है जिनमें जोड़ और गुणा को सामान्यीकृत किया जाता है। इस व्यवहार को समझाने के लिए एक क्रमविनिमेय सेमीरिंग एक अच्छा ढाँचा है। इसे एक सेट पर परिभाषित किया गया है $K$ ऑपरेटरों के साथ$+$और$.$कहाँ $(K,\,+)$ और $(K,\,.)$ एक क्रमविनिमेय मोनोइड हैं और वितरणात्मक कानून कायम है।

होने देना $p_{1},\ldots ,p_{n}$ ऐसे परिवर्तनशील बनें $p_{1}\in A_{1},\ldots ,p_{n}\in A_{n}$ कहाँ $A$ एक परिमित समुच्चय है और $|A_{i}|=q_{i}$. यहाँ $i=1,\ldots ,n$. अगर $S=\{i_{1},\ldots ,i_{r}\}$ और $S\,\subset \{1,\ldots ,n\}$, होने देना $A_{S}=A_{i_{1}}\times \cdots \times A_{i_{r}}$, $p_{S}=(p_{i_{1}},\ldots ,p_{i_{r}})$,

$q_{S}=|A_{S}|$, $\mathbf {A} =A_{1}\times \cdots \times A_{n}$, और

$\mathbf {p} =\{p_{1},\ldots ,p_{n}\}$ होने देना $S=\{S_{j}\}_{j=1}^{M}$ कहाँ $S_{j}\subset \{1,...\,,n\}$. मान लीजिए किसी फ़ंक्शन को इस प्रकार परिभाषित किया गया है $\alpha _{i}:A_{S_{i}}\rightarrow R$, कहाँ $R$ एक क्रमविनिमेय सेमीरिंग है। भी, $p_{S_{i}}$ स्थानीय डोमेन नाम दिए गए हैं और $\alpha _{i}$ स्थानीय गुठली के रूप में.

अब वैश्विक कर्नेल $\beta :\mathbf {A} \rightarrow R$ परिभाषित किया जाता है : $\beta (p_{1},...\,,p_{n})=\prod _{i=1}^{M}\alpha (p_{S_{i}})$ एमपीएफ समस्या की परिभाषा: एक या अधिक सूचकांकों के लिए $i=1,...\,,M$, के मानों की एक तालिका की गणना करें $S_{i}$-वैश्विक कर्नेल का हाशियाकरण $\beta$, जो कि कार्य है $\beta _{i}:A_{S_{i}}\rightarrow R$ के रूप में परिभाषित $\beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)$ यहाँ $S_{i}^{c}$ का पूरक है $S_{i}$ इसके संबंध में $\mathbf {\{} 1,...\,,n\}$ और यह $\beta _{i}(p_{S_{i}})$ कहा जाता है $i^{th}$ वस्तुनिष्ठ फलन, या वस्तुनिष्ठ फलन $S_{i}$. यह देखा जा सकता है कि की गणना $i^{th}$ स्पष्ट तरीके से वस्तुनिष्ठ कार्य की आवश्यकता है $Mq_{1}q_{2}q_{3}\cdots q_{n}$ परिचालन. ऐसा इसलिए है क्योंकि वहाँ हैं $q_{1}q_{2}\cdots q_{n}$ अतिरिक्त और $(M-1)q_{1}q_{2}...q_{n}$ की गणना में आवश्यक गुणन $i^{\text{th}}$ उद्देश्य समारोह। जीडीएल एल्गोरिदम जिसे अगले भाग में समझाया गया है, इस कम्प्यूटेशनल जटिलता को कम कर सकता है।

निम्नलिखित एमपीएफ समस्या का एक उदाहरण है। होने देना $p_{1},\,p_{2},\,p_{3},\,p_{4},$ और $p_{5}$ ऐसे परिवर्तनशील बनें $p_{1}\in A_{1},p_{2}\in A_{2},p_{3}\in A_{3},p_{4}\in A_{4},$ और $p_{5}\in A_{5}$. यहाँ $M=4$ और $S=\{\{1,2,5\},\{2,4\},\{1,4\},\{2\}\}$. इन वेरिएबल्स का उपयोग करके दिए गए फ़ंक्शन हैं $f(p_{1},p_{2},p_{5})$ और $g(p_{3},p_{4})$ और हमें गणना करने की आवश्यकता है $\alpha (p_{1},\,p_{4})$ और $\beta (p_{2})$ के रूप में परिभाषित:

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

$\beta (p_{2})=\sum \limits _{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})$

यहां स्थानीय डोमेन और स्थानीय कर्नेल को इस प्रकार परिभाषित किया गया है:

local domains	local kernels
$\{p_{1},p_{2},p_{5}\}$	$(f(p_{1},p_{2},p_{5})$
$\{p_{2},p_{4}\}$	$g(p_{2},p_{4})$
$\{p_{1},p_{4}\}$	$1$
$\{p_{2}\}$	$1$

कहाँ $\alpha (p_{1},p_{4})$ है $3^{rd}$ वस्तुनिष्ठ कार्य और $\beta (p_{2})$ है $4^{th}$ उद्देश्य समारोह।

एक और उदाहरण पर विचार करें जहां $p_{1},p_{2},p_{3},p_{4},r_{1},r_{2},r_{3},r_{4}\in \{0,1\}$ और $f(r_{1},r_{2},r_{3},r_{4})$ एक वास्तविक मूल्यवान कार्य है। अब, हम एमपीएफ समस्या पर विचार करेंगे जहां क्रमविनिमेय सेमीरिंग को सामान्य जोड़ और गुणा के साथ वास्तविक संख्याओं के सेट के रूप में परिभाषित किया गया है और स्थानीय डोमेन और स्थानीय कर्नेल को निम्नानुसार परिभाषित किया गया है:

local domains	local kernels
$\{r_{1},r_{2},r_{3},r_{4}\}$	$f(r_{1},r_{2},r_{3},r_{4})$
$\{p_{1},r_{1}\}$	$(-1)^{p_{1}r_{1}}$
$\{p_{2},r_{2}\}$	$(-1)^{p_{2}r_{2}}$
$\{p_{3},r_{3}\}$	$(-1)^{p_{3}r_{3}}$
$\{p_{4},r_{4}\}$	$(-1)^{p_{4}r_{4}}$
$\{p_{1},p_{2},p_{3},p_{4}\}$	$1$

अब चूंकि वैश्विक कर्नेल को स्थानीय कर्नेल के उत्पाद के रूप में परिभाषित किया गया है, यह है

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

और स्थानीय डोमेन पर उद्देश्य फ़ंक्शन $p_{1},p_{2},p_{3},p_{4}$ है

$F(p_{1},p_{2},p_{3},p_{4})=\displaystyle \sum \limits _{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}}.$

यह फ़ंक्शन का Hadamard रूपांतरण है $f(\cdot )$. इसलिए हम देख सकते हैं कि हैडामर्ड ट्रांसफॉर्म की गणना एमपीएफ समस्या का एक विशेष मामला है। यह साबित करने के लिए और अधिक उदाहरण प्रदर्शित किए जा सकते हैं कि एमपीएफ समस्या कई शास्त्रीय समस्याओं के विशेष मामले बनाती है जैसा कि ऊपर बताया गया है जिनका विवरण यहां पाया जा सकता है

जीडीएल: एमपीएफ समस्या को हल करने के लिए एक एल्गोरिदम

यदि कोई किसी दिए गए सेट के तत्वों के बीच एक संबंध पा सकता है $S$, तो कोई विश्वास प्रसार की धारणा के आधार पर एमपीएफ समस्या को हल कर सकता है जो संदेश भेजने की तकनीक का एक विशेष उपयोग है। आवश्यक संबंध यह है कि स्थानीय डोमेन के दिए गए सेट को एक जंक्शन ट्री में व्यवस्थित किया जा सकता है। दूसरे शब्दों में, हम के तत्वों के साथ एक ग्राफ सैद्धांतिक वृक्ष बनाते हैं $S$ पेड़ के शीर्ष के रूप में (ग्राफ सिद्धांत) $T$, जैसे कि किन्हीं दो मनमाने शीर्षों के लिए कहें $v_{i}$ और $v_{j}$ कहाँ $i\neq j$ और इन दो शीर्षों के बीच एक किनारा मौजूद है, फिर संबंधित लेबलों का प्रतिच्छेदन, अर्थात $S_{i}\cap S_{j}$, से अद्वितीय पथ पर प्रत्येक शीर्ष पर लेबल का एक उपसमूह है $v_{i}$ को $v_{j}$.

उदाहरण के लिए,

उदाहरण 1: निम्नलिखित नौ स्थानीय डोमेन पर विचार करें:

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

ऊपर दिए गए स्थानीय डोमेन के सेट के लिए, कोई उन्हें जंक्शन ट्री में व्यवस्थित कर सकता है जैसा कि नीचे दिखाया गया है:

इसी प्रकार यदि निम्नलिखित जैसा एक और सेट दिया गया है

उदाहरण 2: निम्नलिखित चार स्थानीय डोमेन पर विचार करें:

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

फिर केवल इन स्थानीय डोमेन के साथ पेड़ का निर्माण संभव नहीं है क्योंकि मूल्यों के इस सेट में कोई सामान्य डोमेन नहीं है जिसे उपरोक्त सेट के किन्हीं दो मानों के बीच रखा जा सके। लेकिन हालाँकि, यदि नीचे दिखाए गए अनुसार दो डमी डोमेन जोड़ें तो अद्यतन सेट को जंक्शन ट्री में व्यवस्थित करना संभव और आसान भी होगा।

5.$\{p_{1},p_{2}$,$p_{4}\}$
6.$\{p_{2},p_{3}$,$p_{4}\}$ इसी प्रकार डोमेन के इन सेट के लिए, जंक्शन ट्री नीचे दिखाए गए जैसा दिखता है:

सामान्यीकृत वितरण कानून (जीडीएल) एल्गोरिदम

इनपुट: स्थानीय डोमेन का एक सेट।
आउटपुट: डोमेन के दिए गए सेट के लिए, समस्या को हल करने के लिए आवश्यक न्यूनतम संख्या में ऑपरेशन की गणना की जाती है।
तो यदि $v_{i}$ और $v_{j}$ जंक्शन ट्री में एक किनारे से जुड़े होते हैं, फिर एक संदेश से $v_{i}$ को $v_{j}$ किसी फ़ंक्शन द्वारा दिए गए मानों का एक सेट/तालिका है: $\mu _{i,j}$:$A_{S_{i}\cap S_{j}}\rightarrow R$. सभी कार्यों के साथ आरंभ करने के लिए अर्थात सभी संयोजनों के लिए $i$ और $j$ दिए गए पेड़ में, $\mu _{i,j}$ को समान रूप से परिभाषित किया गया है $1$ और जब कोई विशेष संदेश अद्यतन किया जाता है, तो यह नीचे दिए गए समीकरण का पालन करता है।

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

कहाँ $v_{k}\operatorname {adj} v_{i}$ मतलब कि $v_{k}$ का निकटवर्ती शीर्ष है $v_{i}$ पेड़ में.

इसी प्रकार प्रत्येक शीर्ष पर एक स्थिति होती है जिसे फ़ंक्शन के मानों वाली तालिका के रूप में परिभाषित किया जाता है $\sigma _{i}:A_{S_{i}}\rightarrow R$, बिल्कुल वैसे ही जैसे संदेश 1 से प्रारंभ होते हैं, ठीक उसी तरह, की स्थिति $v_{i}$ स्थानीय कर्नेल के रूप में परिभाषित किया गया है $\alpha (p_{S_{i}})$, लेकिन जब भी $\sigma _{i}$ अद्यतन हो जाता है, यह निम्नलिखित समीकरण का पालन करता है:

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

एल्गोरिदम का मूल कार्य

इनपुट के रूप में स्थानीय डोमेन के दिए गए सेट के लिए, हम यह पता लगाते हैं कि क्या हम जंक्शन ट्री बना सकते हैं, या तो सीधे सेट का उपयोग करके या पहले सेट में डमी डोमेन जोड़कर और फिर जंक्शन ट्री बनाकर, यदि निर्माण जंक्शन संभव नहीं है तो एल्गोरिदम आउटपुट देता है कि दिए गए समीकरण समस्या की गणना करने के लिए चरणों की संख्या को कम करने का कोई तरीका नहीं है, लेकिन एक बार जब हमारे पास जंक्शन ट्री होता है, तो एल्गोरिदम को संदेशों को शेड्यूल करना होगा और राज्यों की गणना करनी होगी, ऐसा करने से हम जान सकते हैं कि चरणों को कहां कम किया जा सकता है, इसलिए इस पर नीचे चर्चा की जाएगी।

संदेश भेजने का शेड्यूल और स्थिति की गणना

ऐसे दो विशेष मामले हैं जिनके बारे में हम यहां बात करने जा रहे हैं, अर्थात् सिंगल वर्टेक्स समस्या जिसमें उद्देश्य फ़ंक्शन की गणना केवल एक शीर्ष पर की जाती है। $v_{0}$ और दूसरा ऑल वर्टिसेस समस्या है जहां लक्ष्य सभी शीर्षों पर वस्तुनिष्ठ फ़ंक्शन की गणना करना है।

आइए 'सिंगल-वर्टेक्स समस्या' से शुरुआत करें, जीडीएल प्रत्येक किनारे को लक्षित शीर्ष की ओर निर्देशित करके शुरू करेगा $v_{0}$. यहां संदेश केवल लक्षित शीर्ष की दिशा में ही भेजे जाते हैं। ध्यान दें कि सभी निर्देशित संदेश केवल एक बार भेजे जाते हैं। संदेश लीफ नोड्स (जहां डिग्री 1 है) से शुरू होकर लक्ष्य शीर्ष की ओर बढ़ते हैं $v_{0}$. संदेश पत्तियों से उसके माता-पिता तक और फिर वहां से उनके माता-पिता तक और इसी तरह तब तक चलता रहता है जब तक कि वह लक्ष्य शीर्ष तक नहीं पहुंच जाता $v_{0}$. लक्ष्य शिखर $v_{0}$ अपनी स्थिति की गणना तभी करेगा जब उसे अपने सभी पड़ोसियों से सभी संदेश प्राप्त होंगे। एक बार जब हमें स्थिति मिल जाती है, तो हमें उत्तर मिल जाता है और इसलिए एल्गोरिथम समाप्त हो जाता है।

उदाहरण के लिए, आइए ऊपर दिए गए स्थानीय डोमेन के सेट से निर्मित एक जंक्शन ट्री पर विचार करें, यानी उदाहरण 1 से सेट,
अब इन डोमेन के लिए शेड्यूलिंग तालिका है (जहां लक्ष्य शीर्ष है) $p_{2}$).

${\text{Round Message or State Computation}}$
$1.\mu _{8,4}(p_{4})=\alpha _{8}(p_{4})$
$2.\mu _{8,4}(p_{4})=\Sigma _{p_{2}}\alpha _{9}(p_{2},p_{4})$
$3.\mu _{5,2}(p_{3})=\alpha _{5}(p_{3})$
$4.\mu _{6,3}(p_{1})=\Sigma _{p_{4}}\alpha _{6}(p_{1},p_{4})$
$5.\mu _{7,3}(p_{1})=\alpha _{7}(p_{1})$
$6.\mu _{4,2}(p_{3})=\Sigma _{p_{4}}\alpha _{4}(p_{3},p_{4}).\mu _{8,4}(p_{4}).\mu _{9,4}(p_{4})$
$7.\mu _{3,1}(p_{2})=\Sigma _{p_{1}}\alpha _{3}(p_{2},p_{1}).\mu _{6,3}(p_{1}).\mu _{7,3}(p_{1})$
$8.\mu _{2,1}(p_{2})=\Sigma _{p_{3}}\alpha _{2}(p_{3},p_{2}).\mu _{4,2}(p_{3}).\mu _{5,2}(p_{3})$
$9.\sigma _{1}(p_{2})=\alpha _{1}(p_{2}).\mu _{2,1}(p_{2}).\mu _{3,1}(p_{2})$ इस प्रकार सिंगल वर्टेक्स जीडीएल की जटिलता को इस प्रकार दिखाया जा सकता है

$\Sigma _{v}d(v)|A_{S_{(v)}}|$ अंकगणितीय संक्रियाएँ
कहां (नोट: उपरोक्त समीकरण का स्पष्टीकरण लेख में बाद में बताया गया है)
$S(v)$ का लेबल है $v$.
$d(v)$ की डिग्री (ग्राफ सिद्धांत) है $v$ (अर्थात् v के निकटवर्ती शीर्षों की संख्या)।

ऑल-वर्टिसेस समस्या को हल करने के लिए, हम जीडीएल को कई तरीकों से शेड्यूल कर सकते हैं, उनमें से कुछ समानांतर कार्यान्वयन हैं जहां प्रत्येक दौर में, प्रत्येक राज्य को अपडेट किया जाता है और प्रत्येक संदेश की गणना और एक ही समय में प्रसारित किया जाता है। इस प्रकार के कार्यान्वयन में अवस्थाएं और संदेश अधिक से अधिक संख्या में चक्कर लगाने के बाद स्थिर हो जाएंगे जो कि पेड़ के व्यास के बराबर है। इस बिंदु पर शीर्षों की सभी अवस्थाएँ वांछित उद्देश्य फ़ंक्शन के बराबर होंगी।

इस समस्या के लिए जीडीएल को शेड्यूल करने का दूसरा तरीका क्रमिक कार्यान्वयन है जहां यह सिंगल वर्टेक्स समस्या के समान है, सिवाय इसके कि हम एल्गोरिदम को तब तक नहीं रोकते हैं जब तक कि आवश्यक सेट के सभी शीर्षों को अपने सभी पड़ोसियों से सभी संदेश नहीं मिल जाते हैं और उनकी गणना नहीं कर लेते हैं राज्य।
इस प्रकार इस कार्यान्वयन के लिए आवश्यक अंकगणित की संख्या अधिकतम है $\Sigma _{v\in V}d(v)|A_{S_{(v)}}|$ अंकगणितीय आपरेशनस।

जंक्शन ट्री का निर्माण

जंक्शन ट्री बनाने की कुंजी स्थानीय डोमेन ग्राफ़ में निहित है $G_{LD}$, जो एक भारित पूर्ण ग्राफ़ है $M$ कोने $v_{1},v_{2},v_{3},\ldots ,v_{M}$ यानी प्रत्येक स्थानीय डोमेन के लिए एक, जिसमें किनारे का भार होता है $e_{i,j}:v_{i}\leftrightarrow v_{j}$
द्वारा परिभाषित $\omega _{i,j}=|S_{i}\cap S_{j}|$.
अगर $x_{k}\in S_{i}\cap S_{j}$, तो हम कहते हैं $x_{k}$ में निहित है$e_{i,j}$. द्वारा चिह्नित $\omega _{max}$ (अधिकतम वजन वाले फैले हुए पेड़ का वजन $G_{LD}$), जिसे परिभाषित किया गया है

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

जहाँ n उस सेट में तत्वों की संख्या है। अधिक स्पष्टता और विवरण के लिए, कृपया इन्हें देखें।

शेड्यूलिंग प्रमेय

होने देना $'T'$ वर्टेक्स सेट के साथ एक जंक्शन ट्री बनें $'V'$ और किनारा सेट $'E'$. इस एल्गोरिथ्म में, संदेश किसी भी किनारे पर दोनों दिशाओं में भेजे जाते हैं, इसलिए हम किनारे के सेट E को शीर्षों के क्रमित जोड़े के सेट के रूप में कह/मान सकते हैं। उदाहरण के लिए, चित्र 1 से $'E'$ निम्नानुसार परिभाषित किया जा सकता है

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

टिप्पणी:$E$ उपरोक्त आपको वे सभी संभावित दिशा-निर्देश देता है जिनसे एक संदेश पेड़ में फैल सकता है।

जीडीएल के लिए शेड्यूल को सबसेट के एक सीमित अनुक्रम के रूप में परिभाषित किया गया है$E$. जिसका सामान्यतः प्रतिनिधित्व किया जाता है

${\mathcal {E}}=${$E_{1},E_{2},E_{3},\ldots ,E_{N}$}, कहाँ $E_{N}$ के दौरान अद्यतन किए गए संदेशों का सेट है $N^{th}$ एल्गोरिदम चलाने का दौर।

कुछ नोटेशनों को परिभाषित/देखने के बाद, हम देखेंगे कि प्रमेय कहता है, जब हमें एक शेड्यूल दिया जाता है ${\mathcal {E}}=\{E_{1},E_{2},E_{3},\ldots ,E_{N}\}$, वर्टेक्स सेट के साथ एक परिमित निर्देशित ग्राफ के रूप में संबंधित सलाखें (ग्राफ) । $V\times \{0,1,2,3,\ldots ,N\}$, जिसमें एक विशिष्ट तत्व को निरूपित किया जाता है $v_{i}(t)$ के लिए $t\in \{0,1,2,3,\ldots ,N\}$, फिर संदेश पारित होने के पूरा होने के बाद, शीर्ष पर बताएं $v_{j}$ यह होंगे $j^{\text{th}}$ उद्देश्य परिभाषित

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

और iff से एक रास्ता है $v_{i}(0)$ को $v_{j}(N)$

कम्प्यूटेशनल जटिलता

यहां हम गणना के लिए आवश्यक गणितीय संक्रियाओं की संख्या के संदर्भ में एमपीएफ समस्या को हल करने की जटिलता को समझाने का प्रयास करते हैं। यानी हम सामान्य विधि का उपयोग करके गणना करते समय आवश्यक संचालन की संख्या की तुलना करते हैं (यहां सामान्य विधि से हमारा मतलब उन तरीकों से है जो संदेश पासिंग या जंक्शन पेड़ों का उपयोग नहीं करते हैं जो संक्षिप्त तरीकों में जीडीएल की अवधारणाओं का उपयोग नहीं करते हैं) और उपयोग करने वाले संचालन की संख्या की तुलना करते हैं सामान्यीकृत वितरणात्मक कानून.

उदाहरण: सबसे सरल मामले पर विचार करें जहां हमें निम्नलिखित अभिव्यक्ति की गणना करने की आवश्यकता है $ab+ac$.

इस अभिव्यक्ति का मूल्यांकन करने के लिए दो गुणा और एक जोड़ की आवश्यकता होती है। अभिव्यक्ति जब वितरणात्मक कानून का उपयोग करके व्यक्त की जाती है तो उसे इस प्रकार लिखा जा सकता है $a(b+c)$ एक सरल अनुकूलन जो संचालन की संख्या को एक जोड़ और एक गुणा तक कम कर देता है।

ऊपर बताए गए उदाहरण के समान हम जीडीएल लागू करके यथासंभव कम ऑपरेशन करने के लिए समीकरणों को विभिन्न रूपों में व्यक्त करेंगे।

जैसा कि पिछले अनुभागों में बताया गया है, हम जंक्शन पेड़ों की अवधारणा का उपयोग करके समस्या का समाधान करते हैं। इन पेड़ों के उपयोग से प्राप्त अनुकूलन पेड़ों पर अर्ध समूह समस्या को हल करके प्राप्त अनुकूलन के बराबर है। उदाहरण के लिए, संख्याओं के समूह का न्यूनतम ज्ञात करने के लिए हम यह देख सकते हैं कि यदि हमारे पास एक पेड़ है और सभी तत्व पेड़ के नीचे हैं, तो हम समानांतर में दो वस्तुओं के न्यूनतम की तुलना कर सकते हैं और परिणामी न्यूनतम होगा माता-पिता को लिखा गया। जब यह प्रक्रिया पेड़ तक फैलती है तो जड़ में तत्वों का न्यूनतम समूह पाया जाएगा।

संदेश पासिंग का उपयोग करके जंक्शन ट्री को हल करने की जटिलता निम्नलिखित है

हम पहले इस्तेमाल किए गए फॉर्मूले को निम्नलिखित फॉर्म में फिर से लिखते हैं। यह शीर्ष v से w तक भेजे जाने वाले संदेश का समीकरण है

$\mu _{v,w}(p_{v\cap w})=\sum _{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})$ ----संदेश समीकरण

इसी प्रकार हम शीर्ष v की स्थिति की गणना के लिए समीकरण को निम्नानुसार फिर से लिखते हैं

$\sigma _{v}(p_{v})=\alpha _{v}(p_{v})\prod _{u\operatorname {adj} v}\mu _{v,w}(p_{v\cap w})$

हम पहले एकल-शीर्ष समस्या का विश्लेषण करेंगे और मान लेंगे कि लक्ष्य शीर्ष है $v_{0}$ और इसलिए हमारे पास एक किनारा है $v$ को $v_{0}$. मान लीजिए हमारे पास बढ़त है $(v,w)$ हम संदेश समीकरण का उपयोग करके संदेश की गणना करते हैं। की गणना करना $p_{u\cap v}$ आवश्यक है

$q_{v\setminus w}-1$

अतिरिक्त और

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

गुणन.

(हम इसका प्रतिनिधित्व करते हैं $|A_{S(v)\ S(w)}|$ जैसा $q_{v\setminus w}$.)

लेकिन इसके लिए कई संभावनाएं होंगी $x_{v\cap w}$ इसलिए
$q_{v\cap w}{\stackrel {\mathrm {def} }{=}}|A_{S(v)\cap S(w)}|$ के लिए संभावनाएं $p_{v\cap w}$. इस प्रकार पूरे संदेश की आवश्यकता होगी

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

अतिरिक्त और

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

गुणा

एक संदेश भेजने के लिए आवश्यक अंकगणितीय संक्रियाओं की कुल संख्या $v_{0}$पेड़ के किनारों के साथ होगा

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

अतिरिक्त और

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

गुणन.

एक बार जब सभी संदेश प्रसारित हो जाते हैं तो एल्गोरिदम स्थिति की गणना के साथ समाप्त हो जाता है $v_{0}$ राज्य गणना की आवश्यकता है $d(v_{0})q_{0}$ अधिक गुणन. राज्य की गणना के लिए आवश्यक गणनाओं की संख्या नीचे दी गई है

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

अतिरिक्त और

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

गुणा

इस प्रकार गणनाओं की संख्या का कुल योग है

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

कहाँ $e=(v,w)$ एक किनारा है और इसका आकार इससे परिभाषित होता है $q_{v\cap w}$ उपरोक्त सूत्र हमें ऊपरी सीमा देता है।

यदि हम किनारे की जटिलता को परिभाषित करते हैं $e=(v,w)$ जैसा

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

इसलिए, $(1)$ के रूप में लिखा जा सकता है

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

अब हम चित्र 1 में परिभाषित समस्या के लिए किनारे की जटिलता की गणना निम्नानुसार करते हैं

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

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

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

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

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

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

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

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

पूरी जटिलता होगी $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}$ जो प्रत्यक्ष विधि की तुलना में काफी कम है। (यहां प्रत्यक्ष विधि से हमारा मतलब उन तरीकों से है जो संदेश भेजने का उपयोग नहीं करते हैं। प्रत्यक्ष विधि का उपयोग करने में लगने वाला समय प्रत्येक नोड पर संदेश की गणना करने और प्रत्येक नोड की स्थिति की गणना करने के समय के बराबर होगा।)

अब हम ऑल-वर्टेक्स समस्या पर विचार करते हैं जहां संदेश को दोनों दिशाओं में भेजना होगा और दोनों शीर्षों पर स्थिति की गणना करनी होगी। ये लगेगा $O(\sum _{v}d(v)d(v)q_{v})$ लेकिन प्रीकंप्यूटिंग द्वारा हम गुणन की संख्या को कम कर सकते हैं $3(d-2)$. यहाँ $d$ शीर्ष की डिग्री है. उदाहरणार्थ: यदि कोई समुच्चय है $(a_{1},\ldots ,a_{d})$ साथ $d$ नंबर. के सभी d उत्पादों की गणना करना संभव है $d-1$ की $a_{i}$ अधिक से अधिक के साथ $3(d-2)$ स्पष्ट के बजाय गुणा $d(d-2)$. हम मात्राओं की पूर्व-गणना करके ऐसा करते हैं

$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}$ और $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}$ यह लेता है $2(d-2)$ गुणन. तो अगर $m_{j}$ सभी के उत्पाद को दर्शाता है $a_{i}$ के अलावा $a_{j}$ हमारे पास है $m_{1}=c_{2},m_{2}=b_{1}\cdot c_{3}$ और इसी तरह दूसरे की आवश्यकता होगी $d-2$ गुणन से कुल बनता है $3(d-2)$

जब जंक्शन ट्री के निर्माण की बात आती है तो हम बहुत कुछ नहीं कर सकते हैं, सिवाय इसके कि हमारे पास कई अधिकतम वजन वाले स्पैनिंग ट्री हो सकते हैं और हमें सबसे कम वजन वाले स्पैनिंग ट्री का चयन करना चाहिए। $\chi (T)$ और कभी-कभी इसका मतलब जंक्शन ट्री जटिलता को कम करने के लिए एक स्थानीय डोमेन जोड़ना हो सकता है।

ऐसा लग सकता है कि GDL तभी सही है जब स्थानीय डोमेन को जंक्शन ट्री के रूप में व्यक्त किया जा सकता है। लेकिन ऐसे मामलों में भी जहां चक्र और कई पुनरावृत्तियां हैं, संदेश लगभग उद्देश्य फ़ंक्शन के बराबर होंगे। कम घनत्व समता-जांच कोड के लिए गैलेजर-टान्नर-वाइबर्ग एल्गोरिदम पर प्रयोग इस दावे का समर्थन करते थे।