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

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

परिचय

गणित में वितरणात्मक नियम गुणा और योग की संक्रियाओं से संबंधित नियम है, जिसे प्रतीकात्मक रूप से कहा गया है, $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$) को हाशिए पर रख रहे हैं। जब हम कम्प्यूटेशनल जटिलता की गणना कर रहे हैं, तो हम देख सकते हैं कि $(a,b)$ के प्रत्येक $q^{2}$ जोड़े के लिए, त्रिक $(c,d,e)$ के कारण $q^{3}$ पद हैं जिन्हें लेने की आवश्यकता है प्रत्येक चरण में एक योग और एक गुणा के साथ $\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)$

अब, जब हम कम्प्यूटेशनल जटिलता की गणना कर रहे हैं, तो हम देख सकते हैं कि $\alpha _{1}(a,\,b)$ और $\alpha _{2}(a)$ प्रत्येक में $q^{3}$ योग हैं और जब हम होते हैं तो $q^{2}$ गुणन होते हैं $\alpha (a,\,b)$ का मूल्यांकन करने के लिए उत्पाद $\alpha _{1}(a,\,b)\cdot \alpha _{2}(a)$ का उपयोग करना। इसलिए, आवश्यक गणनाओं की कुल संख्या $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$, के लिए, वैश्विक कर्नेल $\beta$ के $S_{i}$- हाशियाकरण के मानों की एक तालिका की गणना करें, जो $\beta _{i}(p_{S_{i}})\,=\displaystyle \sum \limits _{p_{S_{i}^{c}}\in A_{S_{i}^{c}}}\beta (p)$ के रूप में परिभाषित फलन $\beta _{i}:A_{S_{i}}\rightarrow R$ है।

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

निम्नलिखित एमपीएफ समस्या का उदाहरण है। मान लीजिए $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})$

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

स्थानीय प्रांत	स्थानीय कर्नेल
$\{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})$ एक वास्तविक मानित फलन है। अब, हम एमपीएफ समस्या पर विचार करेंगे जहां क्रमविनिमेय अर्ध वलय को सामान्य योग और गुणा के साथ वास्तविक संख्याओं के समुच्चय के रूप में परिभाषित किया गया है और स्थानीय प्रांत और स्थानीय कर्नेल को निम्नानुसार परिभाषित किया गया है:

स्थानीय प्रांत	स्थानीय कर्नेल
$\{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}}.$ है।

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

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

यदि कोई किसी दिए गए समुच्चय के अवयवों $S$ के बीच संबंध पा सकता है , तो कोई विश्वास प्रसार की धारणा के आधार पर एमपीएफ समस्या को हल कर सकता है जो संदेश भेजने की तकनीक का विशेष उपयोग है। आवश्यक संबंध यह है कि स्थानीय प्रांत के दिए गए समुच्चय को संधि ट्री में व्यवस्थित किया जा सकता है। दूसरे शब्दों में, हम ट्री $T$ के शीर्षों के रूप में $S$ के साथ एक ग्राफ सैद्धांतिक ट्री बनाते हैं, जैसे कि किन्हीं दो यादृच्छिक शीर्षों $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 तभी सही है जब स्थानीय प्रांत को संधि ट्री के रूप में व्यक्त किया जा सकता है। परंतु ऐसे मामलों में भी जहां चक्र और कई पुनरावृत्तियां हैं, संदेश लगभग उद्देश्य फलन के बराबर होंगे। कम घनत्व समता-जांच कोड के लिए गैलेजर-टान्नर-वाइबर्ग एल्गोरिदम पर प्रयोग इस दावे का समर्थन करते थे।