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

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

परिचय

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