एक पेड़ में सबसे छोटे सामान्य पूर्वज को खोजने के लिए एल्गोरिथ्म

इत्मीनान से, एक दिलचस्प विचार मेरे पास आया, जिसे मैंने एक पेड़ में दो कोने के कम से कम सामान्य पूर्वज (एलसीए) को खोजने के लिए एक एल्गोरिथ्म में विकसित किया। यह विचार आने से पहले, मुझे एलसीए की खोज के लिए अन्य एल्गोरिदम का पता नहीं था। काम की शुद्धता की जांच करने के बाद, मैंने इस समस्या को हल करने के लिए अन्य एल्गोरिदम का अध्ययन करने के लिए जल्दबाजी की, लेकिन मुझे कोई समान नहीं मिला। अब मैं इसे समुदाय के साथ साझा करने की जल्दी कर रहा हूं।

परिचय

एक पेड़ N कोने और N-1 किनारों का एक अप्रत्यक्ष जुड़ा हुआ ग्राफ है। किसी भी शीर्ष से किसी भी अन्य के लिए, बिल्कुल एक सरल मार्ग है।
पेड़ की जड़ को एक ऐसा शीर्ष कहा जाएगा, जहां से पेड़ की परिक्रमा करने की दिशा निर्धारित की जाती है, जब वह चक्कर काटता है।
दो कोने यू और वी के सबसे छोटे सामान्य पूर्वज को वर्टेक्स पी कहा जाएगा जो रूट से वर्टेक्स वी , और वर्टेक्स यू तक के मार्ग पर स्थित है, और जहां तक ​​संभव हो सके।

इनपुट डेटा

पेड़ के बारे में जानकारी में आता है: एन - कोने की संख्या, एन-1 जोड़ी कोने जो एक किनारे से जुड़े हुए हैं, और एम - अनुरोधों की संख्या। फिर कार्यक्रम को अनुरोध प्राप्त होता है: दो कोने यू और वी , जिसके लिए उनके कम से कम सामान्य पूर्वज को खोजने की आवश्यकता होती है।

एल्गोरिदम का आइडिया

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

const int SIZE = 100050; vector<int> v[SIZE]; //      bool vis[SIZE]; //       int kids[SIZE]; // -     int dist[SIZE]; //      int last[SIZE]; //    int turn[SIZE]; 

अब, प्रत्येक शीर्ष के लिए, एक पुनरावर्ती फ़ंक्शन (कॉल k_go (0) ) का उपयोग करके, हम इसके वंशजों की संख्या की गणना करते हैं:

 int k_go(int s) { int res = 0; vis[s] = true; for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) res += k_go(v[s][i]) + 1; } kids[s] = res; return res; } 

और अब हम एल्गोरिथ्म के प्रारंभिक भाग को पूरा करेंगे और प्रत्येक शीर्ष के लिए आवश्यक जानकारी भरें। हम फ़ंक्शन को l_go (0, 0, 0, 1) कहते हैं :

 void l_go(int s, int d, int l, int r) { vis[s] = true; dist[s] = d; last[s] = l; turn[s] = r; int maxval = 0; int idx = -1; for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) { int k = kids[v[s][i]]; if(k > maxval) idx = v[s][i], maxval = k; } } for(int i = 0, maxi = v[s].size(); i < maxi; i++) { if(!vis[v[s][i]]) { if(idx == v[s][i]) l_go(v[s][i], d + 1, l, r); else l_go(v[s][i], d + 1, s, v[s][i]); } } } 

अब मैं समझाऊंगा कि कोड का अंतिम भाग कैसे काम करता है, क्योंकि शीर्ष पर बच्चों की संख्या का पता लगाना एक सामान्य कार्य है।
प्रत्येक शीर्ष के लिए हम उसके वंशज को देखते हैं और उनमें से हम अधिकतम वंश के साथ एक शीर्ष का चयन करते हैं। उसके लिए, पूर्वज के बारे में सभी जानकारी वर्तमान एक से विरासत में मिली होगी, और केवल रूट की दूरी बदल जाएगी। इस शीर्ष के अन्य सभी वंशज के लिए, वर्तमान शीर्ष अब अंतिम का पूर्वज होगा, और वंशज खुद को बदल देगा।
अब मैं दावा करता हूं कि यदि हम पेड़ में कुछ शीर्ष लेते हैं और जब तक हम इसे जड़ से प्राप्त नहीं कर लेते हैं, तब तक अंतिम पूर्वज के लिए संक्रमण की संख्या पेड़ में संख्याओं के द्विआधारी लघुगणक से अधिक नहीं होगी।
प्रमाण: हमें कुछ शीर्ष v पर होना चाहिए जिसमें एक वंशज है। तब यह स्पष्ट है कि इससे निकलने वाला वंश पूर्वज की अंतिम कड़ी को नहीं बदलता है। दो या दो से अधिक चक्करों के मामले में, हमें एक वंशज (वर्तमान शीर्ष के सभी वंशजों में से सबसे बड़ी संख्या में वंशज हैं) जिनकी लिंक वर्तमान और सभी अन्य से विरासत में मिली है, जिनसे यह अद्यतन किया गया है। N द्वारा वर्तमान शीर्ष के वंशजों की कुल संख्या को निरूपित करें । फिर इस शीर्ष के वंशज से, जिसमें हम पूर्वज के लिंक को अपडेट करते हैं, एन / 2 वंशजों से अधिक नहीं होगा (अन्यथा यह संख्या अधिकतम होगी, लेकिन तब लिंक अपडेट की आवश्यकता नहीं है)। इस प्रकार, प्रत्येक कोने पर, जो कि पिछले का पूर्वज है , किसी के लिए आधे से अधिक कोने नहीं हैं, इससे आने वाले सभी वंशज हैं। इस तरह के पथ की कुल लंबाई एन के द्विआधारी लघुगणक से अधिक नहीं होगी ।

अब आइए एल्गोरिथ्म के मुख्य कार्य पर चलते हैं और बताते हैं कि यह क्यों काम करता है।
तो, हमारे पास दो कोने हैं u और v , जिसके लिए हमें अनुरोध का उत्तर खोजने की आवश्यकता है। हम फ़ंक्शन को p = lca (u, v) कहते हैं :

 int lca(int a, int b) { if(turn[a] == turn[b]) { if(dist[a] < dist[b]) return a; else return b; } if(dist[last[a]] > dist[last[b]]) return lca(last[a], b); return lca(last[b], a); } 

फ़ंक्शन को पुन: मूल दिशा में उगता है। ए और बी के बाद के प्रत्येक कोने के लिए , हम पहले उस शीर्ष की जांच करते हैं जिस पर अंतिम घुमाव बनाया गया था। यदि यह संयोग करता है, तो इसका मतलब है कि या तो शीर्ष रूट से वर्टे ख के मार्ग पर स्थित है या इसके विपरीत। इस आधार पर कि कौन सा शीर्ष जड़ के करीब है, यह वांछित कम से कम पूर्वज है।
अन्यथा, शीर्ष को ए या बी को जड़ के करीब लाने के लिए आवश्यक है। हम इस आधार पर अनुमानित करेंगे कि इसके पूर्वज के लिए संक्रमण के मामले में एक रूट से आगे होगा (एक शीर्ष लगातार रूट के दूसरे शिखर के साथ पकड़ने की कोशिश करेगा)। इस प्रकार, जितनी जल्दी या बाद में, वर्टिकल या तो एक शीर्ष पर आ जाएंगे, जो तुरंत उनका सबसे छोटा सामान्य पूर्वज होगा, या एक कोने में जड़ से दूसरे वर्टेक्स तक मार्ग पर झूठ होगा, जो पहले चरण में वर्णित है।

एल्गोरिथ्म का मूल्यांकन

एल्गोरिथ्म को लागू करने के लिए, O (N) मेमोरी की आवश्यकता होती है ( 6N कुल मेमोरी खपत होती है), O (N) प्रारंभिक गणना, और O (M * log (N)) सभी अनुरोधों का जवाब देने के लिए समय।
एल्गोरिथ्म आपको पूर्वनिर्धारित पेड़ पर अनुरोधों का जवाब देने और प्रत्येक के लिए ओ (लॉग (एन)) के रूप में आने के अनुरोधों का जवाब देने की अनुमति देता है।

LCA खोज समस्या को हल करने के लिए अन्य एल्गोरिदम की प्रभावशीलता

इस समस्या को हल करने के लिए कई एल्गोरिदम हैं, जिनमें से प्रत्येक लेखन जटिलता, प्रारंभिक गणना के लिए समय, एक अनुरोध का जवाब और आवश्यक स्मृति के आकार में भिन्न है।
1) हे (लॉग एन) के लिए अनुरोध का जवाब, ओ (एन) के लिए प्रारंभिक गणना। कार्यान्वयन की जटिलता डेटा संरचना "सेगमेंट के पेड़" या "वर्गर्ट-अपघटन" का उपयोग करने की आवश्यकता है।
2) बाइनरी लिफ्ट विधि । O (लॉग एन) के लिए अनुरोध का जवाब, ओ (लॉग एन) के लिए प्रारंभिक गणना, प्रयुक्त मेमोरी (एन * लॉग (एन))। मैंने जिस एल्गोरिथ्म का हवाला दिया, उसकी तुलना में थोड़े बेहतर समय के साथ काफी सरल कार्यान्वयन, लेकिन उपयोग की गई अतिरिक्त मेमोरी के कारण।
3) फराह-कोल्टन और बेंडर एल्गोरिथ्म । यह सबसे इष्टतम एल्गोरिथ्म है, आपको ओ (1) के लिए अनुरोध का जवाब देने की अनुमति देता है, लेकिन इसके लिए बहुत अधिक अतिरिक्त मेमोरी की आवश्यकता होती है और इसे लागू करना मुश्किल होता है।
साथ ही एक एल्गोरिथ्म जो आपको ओ (1) के लिए एक अनुरोध का जवाब देने की अनुमति देता है, लेकिन इसके लिए आपको सभी अनुरोधों के बारे में पहले से जानकारी जानना आवश्यक है।
4) टारजन एल्गोरिथ्म

निष्कर्ष

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

UPD: जानकार लोगों ने मुझे बताया कि मेरा एल्गोरिथ्म हैवी-लाइट अपघटन के अनुप्रयोगों में से एक है। इससे पहले, मैं इस अपघटन से परिचित नहीं था, लेकिन किसी भी मामले में, यह खुद के साथ आने पर अच्छा है, भले ही यह मौजूदा हो।