Level ancestor problem
ग्राफ सिद्धांत और सैद्धांतिक कंप्यूटर विज्ञान में, स्तर पूर्वज समस्या एक दिए गए जड़ वाले ट्री टी को एक डेटा संरचना में पूर्व-संसाधित करने की समस्या है जो पेड़ की जड़ से दी गई दूरी पर दिए गए नोड के पूर्वज को निर्धारित कर सकती है। अधिक सटीक रूप से, मान लीजिए कि टी को एन नोड्स के साथ एक रूट ट्री है, और मान लीजिए कि वी को टी का एक मनमाना नोड है। स्तर पूर्वज क्वेरी एलए (वी, डी) गहराई डी पर नोड वी के पूर्वज से अनुरोध करता है, जहां एक ट्री में एक नोड वी की गहराई ट्री के रूट से नोड वी तक के सबसे छोटे रास्ते पर किनारों की संख्या है। इस समस्या को प्रति क्वेरी स्थिर समय में हल करना संभव है, एक प्रीप्रोसेसिंग एल्गोरिदम के बाद जो ओ (एन) लेता है और जो एक डेटा संरचना बनाता है जो ओ (एन) भंडारण स्थान का उपयोग करता है। नादान तरीके एक नोड के एक स्तर के पूर्वज को खोजने का सबसे सरल तरीका पेड़ की जड़ की ओर पेड़ पर चढ़ना है। पेड़ की जड़ के रास्ते पर, एक नोड के प्रत्येक पूर्वज का दौरा किया जा सकता है और इसलिए सूचित किया जा सकता है। इस मामले में, पेड़ को पूर्व-संसाधित करने की आवश्यकता नहीं है और एक प्रश्न का उत्तर देने का समय ओ (एच) है, जहाँ "एच" पेड़ की ऊँचाई है। यह दृष्टिकोण उन स्थितियों में संभव नहीं है जहां पेड़ की ऊंचाई अधिक हो सकती है और बड़ी संख्या में प्रश्नों को संसाधित करने की आवश्यकता होती है। वैकल्पिक रूप से, सभी संभावित समाधानों को पूर्व संगणित किया जा सकता है और एक तालिका में संग्रहीत किया जा सकता है। इस मामले में, प्रश्नों का उत्तर ओ (1) में दिया जा सकता है लेकिन स्थान और पूर्व प्रसंस्करण समय ओ (एन 2) है। एल. ए. (वी, 0) और एल. ए. (वी, डेप्थ (वी)) सबसे सरल प्रश्न हैं जिनका उत्तर बिना किसी पूर्वसंसाधन के स्थिर समय में दिया जा सकता है। पहले मामले में, उत्तर हमेशा पेड़ की जड़ होता है और बाद के मामले में, उत्तर नोड v ही होता है। इनमें से प्रत्येक परिणाम ओ (1) लेता है। एक तिरछी द्विआधारी यादृच्छिक अभिगम सूची में पेड़ के माध्यम से रास्तों को संग्रहीत करने से पेड़ को अभी भी एक समय में एक ओ (1) कदम नीचे की ओर बढ़ाया जा सकता है, लेकिन अब खोज को ओ (लॉग (पी)) में आगे बढ़ने की अनुमति देता है, जहां "पी" अनुरोधित गहराई तक वी से दूरी है। यह दृष्टिकोण तब संभव है जब पेड़ विशेष रूप से चौड़ा हो या इसे ऑनलाइन बढ़ाया जाएगा और इसलिए इसे प्रभावी रूप से पूर्व-संसाधित नहीं किया जा सकता है, क्योंकि भंडारण और पहुंच का समय विशुद्ध रूप से पथ की लंबाई से निर्धारित होता है। जंप पॉइंटर एल्गोरिदम जंप पॉइंटर एल्गोरिदम ओ (एन लॉग एन) समय में एक ट्री को पूर्व-संसाधित करता है और ओ (लॉग एन) समय में स्तर पूर्वज प्रश्नों का उत्तर देता है। जंप पॉइंटर एल्गोरिथ्म पेड़ के प्रत्येक शीर्ष पर लॉग एन पॉइंटर्स तक संबद्ध करता है। इन संकेतों को कूद संकेत कहा जाता है क्योंकि वे पेड़ की जड़ की ओर पेड़ पर कूदते हैं। एक पेड़ के दिए गए नोड वी के लिए, एल्गोरिथ्म लंबाई कूदने वालों की एक सरणी को संग्रहीत करता है। इस सरणी का ith तत्व v के 2th पूर्वज की ओर इशारा करता है। इस तरह की डेटा संरचना का उपयोग करने से हमें किसी भी नोड से पेड़ के आधे रास्ते पर कूदने में मदद मिलती है। जब एल्गोरिथ्म को किसी प्रश्न को संसाधित करने के लिए कहा जाता है, तो हम बार-बार इन संकेतों का उपयोग करके पेड़ पर कूदते हैं। कूद की संख्या अधिक से अधिक लॉग एन होगी और इसलिए प्रश्नों का उत्तर लॉग एन समय में दिया जा सकता है। सीढ़ी एल्गोरिथ्म सीढ़ी एल्गोरिथ्म एक पेड़ को पथों के संग्रह में सरल बनाने के विचार पर आधारित है। इसका कारण यह है कि जब पूर्वजों के प्रश्नों के स्तर की बात आती है तो रास्तों से पूछताछ करना आसान होता है। एक पथ पी पर विचार करें जिसमें एक नोड आर पर जड़ वाले एन नोड्स शामिल हैं। हम पथ को सीढ़ी नामक आकार एन की एक सरणी में संग्रहीत कर सकते हैं और हम सीढ़ी [डी] को गहराई (वी) ≤ डी वापस करके एलए (वी, डी) के एक स्तर पूर्वज प्रश्न का त्वरित उत्तर दे सकते हैं। यह ओ (1) लेगा। हालाँकि, यह केवल तभी काम करेगा जब दिया गया वृक्ष एक मार्ग हो। अन्यथा, हमें इसे रास्तों में विघटित करने की आवश्यकता है। यह दो चरणों में किया जाता हैः लंबे मार्ग का अपघटन और लंबे मार्गों को सीढ़ी में विस्तारित करना। चरण 1: लंबा पथ अपघटन यह एक पुनरावर्ती विधि है जो किसी दिए गए पेड़ को पथ में विघटित करती है। यह चरण पेड़ में जड़ से पत्ती तक का सबसे लंबा मार्ग खोजने से शुरू होता है। इसके बाद यह पेड़ से अपने संबंधों को तोड़कर इस रास्ते को हटा देता है जो पेड़ के शेष हिस्से को उप-पेड़ों में तोड़ देगा और फिर प्रत्येक उप-पेड़ को बार-बार संसाधित करेगा। हर बार जब कोई पथ विघटित होता है, तो उस पथ के साथ एक सरणी बनाई जाती है जिसमें जड़ से पत्ती तक के मार्ग पर तत्व होते हैं। इस पुनरावृत्ति का आधार मामला तब होता है जब पेड़ एक रास्ता होता है जिस स्थिति में इसे हटाने से एक खाली ग्राफ निकल जाता है। प्रत्येक शीर्ष v में एक अद्वितीय सीढ़ी होती है जो इसे धारण करने वाली सीढ़ी होती है और हम इसे "v की सीढ़ी" कहते हैं। हालाँकि, इस पूर्व-प्रसंस्करण चरण के बाद, प्रश्नों का उत्तर जल्दी से नहीं दिया जा सकता है। वास्तव में एक स्तर के पूर्वज प्रश्न का उत्तर देने के लिए, एल्गोरिथ्म को एक मार्ग से दूसरे मार्ग पर कूदने की आवश्यकता होती है जब तक कि यह मूल तक नहीं पहुंच जाता है और लीफ-टू-रूट पथ पर ऐसे पथों का θ () हो सकता है। यह हमें एक एल्गोरिथ्म की ओर ले जाता है जो ओ (एन) समय में ट्री को पूर्व-संसाधित कर सकता है और ओ () में प्रश्नों का उत्तर दे सकता है। इष्टतम प्रश्न समय तक पहुँचने के लिए, हमें नीचे वर्णित दूसरे चरण में परिणामों को संसाधित करने की आवश्यकता है। चरण 2: सीढ़ी में लंबे रास्तों का विस्तार एल्गोरिदम का पहला चरण पेड़ को कई अलग-अलग रास्तों में विघटित कर देता है। एल्गोरिथम के दूसरे चरण में, प्रत्येक पथ का विस्तार किया जाता है और इसलिए परिणामी पथ पारस्परिक रूप से अनन्य नहीं होंगे। एल्गोरिथम के पहले चरण में, प्रत्येक पथ आकार एच 'की एक सरणी से जुड़ा होता है। हम एक ही सरणी में पथ के शीर्ष पर एच 'तत्काल पूर्वजों को जोड़कर इस मार्ग का विस्तार करते हैं। यह प्रत्येक सरणी को उसके मूल आकार से दोगुना बढ़ाएगा जिसके परिणामस्वरूप सभी सीढ़ियों में कुल 2n नोड्स होंगे। ध्यान दें कि सीढ़ी की संख्या नहीं बदली है और प्रत्येक नोड की सीढ़ी समान रहती है। हालाँकि एक नोड वी को अब कई रास्तों में सूचीबद्ध किया जा सकता है, लेकिन इसकी सीढ़ी वह है जो एल्गोरिथ्म के पहले चरण में वी से जुड़ी थी। ये दोनों चरण ओ (एन) में प्रक्रियाएँ हो सकती हैं लेकिन पूछताछ का समय अभी तक स्थिर नहीं है। ऊँचाई एच के नोड यू पर एक स्तर पूर्वज प्रश्न पर विचार करें। यू की सीढ़ी के शीर्ष पर यात्रा करने से, कम से कम 2 घंटे की ऊँचाई के शीर्ष तक पहुँच जाएगा। ध्यान दें कि सभी नोड्स की ऊंचाई कम से कम 1 है और इसलिए इसे i बार करने के बाद, हम कम से कम 2i ऊंचाई के नोड तक पहुंच जाते हैं और इसलिए हमें इसे अधिकतम लॉग n बार करने की आवश्यकता होती है। यह हमें ओ (लॉग एन) का क्वेरी समय देता है। चरण 3: दोनों दृष्टिकोणों का संयोजन यह पता चला है कि सीढ़ी एल्गोरिथ्म अपने दम पर चाल नहीं करता है। वास्तव में जंप पॉइंटर एल्गोरिदम और लैडर एल्गोरिदम एक दूसरे के पूरक हैं। दोनों एल्गोरिदम विपरीत दिशाओं में काम करते हैंः जंप पॉइंटर एल्गोरिदम तेजी से हॉप्स को कम करता है और लैडर एल्गोरिदम तेजी से हॉप्स को बढ़ाता है। दो एल्गोरिदम का एक संयोजन ओ (1) समय में प्रश्नों का उत्तर दे सकता है। एक सिंगल जंप पॉइंटर किसी भी प्रश्न को कम से कम पेड़ के आधे रास्ते पर ले जाता है जिसके बाद केवल एक सीढ़ी पर चढ़ने से प्रश्न का उत्तर मिलेगा। इसके परिणामस्वरूप ओ (एन लॉग एन) पूर्व-प्रसंस्करण समय और ओ (1) प्रश्न समय होता है। पूर्व-प्रसंस्करण को चार रूसियों की विधि के एक अनुप्रयोग द्वारा ओ (एन) समय तक कम किया जा सकता है, जिसमें पेड़ को रैखिक पूर्व-प्रसंस्करण के साथ एक छोटे पेड़ तक कम किया जाता है, और बहुत छोटे पेड़ों का संग्रह, जो इतने छोटे होते हैं कि सभी पेड़ों की एक विस्तृत गणना और उन पेड़ों का पूर्व-प्रसंस्करण अभी भी ओ (एन) समय है। आकार के पेड़ (लॉग एन)/4 पर्याप्त हैं। बर्कमैन और विश्किन का समाधान एक अलग समाधान बर्कमैन और विश्किन के कारण है। यह समाधान पेड़ों को संसाधित करने के लिए यूलर टूर तकनीक पर आधारित है। मुख्य अवलोकन यह है कि एल. ए. (वी, डी) गहराई डी का पहला नोड है जो वी. के अंतिम प्रदर्शन के बाद यूलर टूर में दिखाई देता है। इस प्रकार, यूलर टूर और गहराई पर संबंधित जानकारी का निर्माण करके, समस्या को सरणियों पर एक प्रश्न तक कम कर दिया जाता है, जिसे फाइंड स्मॉलर (एफ. एस.) नाम दिया गया है। एक सरणी A के लिए, और एक वैध सूचकांक i, FS (i, x) पहला सूचकांक j> i इस तरह देता है कि A [i] <x (यहाँ, हम x = d + 1 का उपयोग करते हैं)। एफ. एस. समस्या का एक कुशल समाधान सामान्य रूप से कठिन है, लेकिन यूलर टूर से उत्पन्न होने वाले विशेष मामले के लिए आसान है; इस मामले में, आसन्न तत्व ±1 से भिन्न होते हैं। यह विचार जटिलता ओ (एन लॉग एन) के पूर्व प्रसंस्करण एल्गोरिदम के साथ ओ (1) प्रश्न समय देता है। प्रीप्रोसेसिंग समय को चार रूसियों की विधि के एक अनुप्रयोग द्वारा ओ (एन) में सुधार किया गया है। यह भी देखें रेंज क्वेरी (कंप्यूटर विज्ञान) सबसे कम सामान्य पूर्वज संदर्भ सैद्धांतिक कंप्यूटर विज्ञान पेड़ (ग्राफ सिद्धांत)