Reverse-search algorithm
रिवर्स-सर्च एल्गोरिदम संयोजन वस्तुओं के कुछ वर्गों से दिए गए आकार की सभी वस्तुओं को उत्पन्न करने के लिए एल्गोरिदम का एक वर्ग है। कई मामलों में, ये विधियाँ वस्तुओं को प्रति वस्तु बहुपद समय में उत्पन्न करने की अनुमति देती हैं, जिसमें वस्तुओं की एक स्थिर संख्या (बहुपद स्थान) को संग्रहीत करने के लिए केवल पर्याप्त स्मृति का उपयोग किया जाता है। (आम तौर पर, हालांकि, उन्हें बहुपद-समय एल्गोरिदम के रूप में वर्गीकृत नहीं किया जाता है, क्योंकि उनके द्वारा उत्पन्न वस्तुओं की संख्या घातीय होती है।) वे अपने राज्य क्षेत्र के एक फैले हुए पेड़ में उत्पन्न होने वाली वस्तुओं को व्यवस्थित करके काम करते हैं, और फिर इस पेड़ की गहराई से खोज करते हैं। उत्तल पॉलीटोप के शीर्षों और हाइपरप्लेन की व्यवस्था की कोशिकाओं को उत्पन्न करने की समस्याओं के लिए 1991 में डेविड एविस और कोमेई फुकुदा द्वारा रिवर्स-सर्च एल्गोरिदम पेश किए गए थे। 1996 में एविस और फुकुदा द्वारा उन्हें अधिक व्यापक रूप से औपचारिक रूप दिया गया था। सिद्धांत एक रिवर्स-सर्च एल्गोरिथ्म एक अवस्था स्थान में संयोजी वस्तुओं को उत्पन्न करता है, एक अंतर्निहित ग्राफ जिसके शीर्ष सूचीबद्ध की जाने वाली वस्तुएं हैं और जिनके किनारे वस्तुओं के जोड़े को जोड़ने वाली कुछ "स्थानीय चालों" का प्रतिनिधित्व करते हैं, आमतौर पर उनकी संरचना में छोटे बदलाव करके। यह प्रत्येक वस्तु को इस अवस्था स्थान के जड़ वाले फैले हुए पेड़ में गहराई से पहले खोज का उपयोग करते हुए पाता है, जिसका वर्णन निम्नलिखित जानकारी द्वारा किया गया हैः फैले हुए पेड़ की जड़, वस्तुओं में से एक पेड़ में प्रत्येक वस्तु के मूल को उत्पन्न करने के लिए एक सबरूटीन, इस गुण के साथ कि यदि पर्याप्त बार दोहराया जाए तो यह अंततः राज्य स्थान में सभी पड़ोसियों को सूचीबद्ध करने के लिए मूल ए सबरूटीन तक पहुंच जाएगा (जिनमें से सभी पेड़ में पड़ोसी नहीं हो सकते हैं) इस जानकारी से पेड़ में दिए गए किसी भी नोड के बच्चों को ढूंढना संभव है, मूल सबरूटीन द्वारा दिए गए लिंक को उलटते हुएः वे केवल पड़ोसी हैं जिनके मूल दिए गए नोड हैं। यह चाइल्ड नोड्स के लिए ये विपरीत लिंक हैं जिन्हें एल्गोरिथ्म खोजता है। इस फैले हुए पेड़ की एक शास्त्रीय गहराई-पहली खोज, जड़ से शुरू होकर, प्रत्येक नोड पर सभी बच्चों को सूचीबद्ध करती है और प्रत्येक के लिए एक पुनरावर्ती कॉल करती है। चक्रों के साथ ग्राफ की गहराई-पहली खोज के विपरीत, बार-बार आने से बचने के लिए पहले से देखे गए नोड्स के सेट को बनाए रखना आवश्यक नहीं है; इस तरह की पुनरावृत्ति एक पेड़ में संभव नहीं है। हालाँकि, इस पुनरावर्ती एल्गोरिथ्म को अभी भी अपने कॉल स्टैक के लिए बड़ी मात्रा में मेमोरी की आवश्यकता हो सकती है, ऐसे मामलों में जब ट्री बहुत गहरा हो। इसके बजाय, रिवर्स सर्च केवल दो वस्तुओं को संग्रहीत करते हुए एक ही क्रम में फैले हुए पेड़ को पार करता हैः ट्रैवर्सल की वर्तमान वस्तु, और पहले से पार की गई वस्तु। प्रारंभ में, वर्तमान वस्तु को पेड़ की जड़ पर सेट किया जाता है, और कोई पिछली वस्तु नहीं होती है। इस जानकारी से, निम्नलिखित मामले के विश्लेषण द्वारा पारगमन के अगले चरण का निर्धारण करना संभव हैः यदि कोई पिछली वस्तु नहीं है, या पिछली वस्तु वर्तमान वस्तु की मूल है, तो यह पहली बार है जब पारगमन वर्तमान वस्तु तक पहुंच गया है, इसलिए यह खोज से आउटपुट है। अगला उद्देश्य इसका पहला बच्चा है या, यदि इसका कोई बच्चा नहीं है, तो इसका माता-पिता है। अन्य सभी मामलों में, पिछली वस्तु वर्तमान वस्तु की संतान होनी चाहिए। एल्गोरिथ्म इस पिछले बच्चे तक पहुंचने तक बच्चों (यानी, वर्तमान वस्तु के राज्य-स्थान पड़ोसियों जिनके पास वर्तमान वस्तु उनके माता-पिता के रूप में है) को एक बार में सूचीबद्ध करता है, और फिर बच्चों की इस सूची में एक और कदम उठाता है। यदि इस तरह से एक और बच्चा पाया जाता है, तो यह अगली वस्तु है। यदि कोई अगला चाइल्ड नहीं है और वर्तमान वस्तु मूल नहीं है, तो अगला ऑब्जेक्ट वर्तमान वस्तु का मूल है। शेष मामले में, जब कोई अगला बच्चा नहीं होता है और वर्तमान वस्तु मूल होती है, तो रिवर्स खोज समाप्त हो जाती है। इस एल्गोरिथ्म में खोज के प्रत्येक चरण के लिए एक बार किसी वस्तु के पड़ोसियों को सूचीबद्ध करना शामिल है। हालाँकि, यदि सूचीबद्ध की जाने वाली वस्तुएँ हैं, तो खोज चरणों का प्रदर्शन करती है, इसलिए यह वस्तुओं के पड़ोसियों को उत्पन्न करने की संख्या दो बार के कारक के भीतर होती है जो पुनरावर्ती गहराई-पहली खोज एक ही काम करेगी। अनुप्रयोग जिन समस्याओं के लिए विपरीत खोज को लागू किया गया है, उनके उदाहरणों में निम्नलिखित संयोजी पीढ़ी की समस्याएं शामिल हैंः सरल उत्तल पॉलीटोप के शीर्ष यदि एक आयामी उत्तल पॉलीटोप को अर्ध-स्थानों के प्रतिच्छेदन के रूप में परिभाषित किया जाता है, तो इसके शीर्षों को अर्ध-स्थानों को घेरने वाले या अधिक हाइपरप्लेन के प्रतिच्छेदन के बिंदुओं के रूप में वर्णित किया जा सकता है; यह एक सरल पॉलीटोप है यदि कोई भी शीर्ष इन हाइपरप्लेन से अधिक का प्रतिच्छेदन नहीं है। शीर्ष गणना समस्या इन सभी शीर्षों को सूचीबद्ध करने की समस्या है। पॉलीटोप के किनारे उन शीर्षों के जोड़े को जोड़ते हैं जिनमें समान रूप से हाइपरप्लेन होते हैं, इसलिए शीर्ष और किनारे एक अवस्था स्थान बनाते हैं जिसमें प्रत्येक शीर्ष के पड़ोसी होते हैं। रैखिक प्रोग्रामिंग के सिद्धांत से सिम्प्लेक्स एल्गोरिथ्म एक शीर्ष को खोजता है जो निर्देशांक के दिए गए रैखिक कार्य को अधिकतम करता है, शीर्ष से शीर्ष तक चलकर, प्रत्येक चरण में कार्य के अधिक मूल्य के साथ एक शीर्ष का चयन करता है; "धुरी नियम" के कई मानक विकल्प हैं जो अधिक सटीक रूप से निर्दिष्ट करते हैं कि किस शीर्ष को चुनना है। इस तरह के किसी भी धुरी नियम की व्याख्या पॉलीटोप के एक फैले हुए पेड़ के मूल कार्य को परिभाषित करने के रूप में की जा सकती है, जिसका मूल इष्टतम शीर्ष है। इस डेटा पर विपरीत खोज लागू करने से पॉलीटोप के सभी शीर्ष उत्पन्न होते हैं। एक समान एल्गोरिथ्म एक रैखिक कार्यक्रम के सभी आधारों की गणना भी कर सकता है, बिना किसी आवश्यकता के कि यह एक सरल पॉलीटोप को परिभाषित करता है। हाइपरप्लेन व्यवस्था की कोशिकाएँ एक हाइपरप्लेन व्यवस्था यूक्लिडियन स्थान को कोशिकाओं में विघटित करती है, प्रत्येक को एक "साइन वेक्टर" द्वारा वर्णित किया जाता है जो यह वर्णन करता है कि क्या इसके बिंदु हाइपरप्लेन (साइन 0) में से किसी एक से संबंधित हैं, हाइपरप्लेन (साइन + 1) के एक तरफ हैं, या दूसरी तरफ हैं (साइन-1)। कोशिकाएँ स्थानीय चालों के तहत एक जुड़े हुए अवस्था स्थान का निर्माण करती हैं जो एक इकाई द्वारा एक एकल संकेत को बदल देती हैं, और यह जांचना संभव है कि यह ऑपरेशन एक रैखिक प्रोग्रामिंग व्यवहार्यता समस्या को हल करके एक वैध कोशिका का उत्पादन करता है या नहीं। मूल कोशिका के किसी भी विकल्प के लिए एक विस्तृत वृक्ष का निर्माण एक मूल प्रचालक को परिभाषित करके किया जा सकता है जो पहला संभावित परिवर्तन करता है जो संकेत सदिश को मूल के करीब लाएगा। इस अवस्था स्थान और मूल प्रचालक के लिए रिवर्स खोज का उपयोग करके प्रति कोशिका बहुपद समय में सभी कोशिकाओं को सूचीबद्ध करने के लिए एक एल्गोरिथ्म तैयार किया जाता है। एक समतलीय बिंदु समुच्चय के त्रिकोण "पलट" चालों द्वारा जुड़े होते हैं जो एक त्रिभुज से एक विकर्ण को हटा देते हैं और इसे दूसरे द्वारा प्रतिस्थापित करते हैं। यदि डेलाउने त्रिभुज को मूल के रूप में चुना जाता है, तो प्रत्येक त्रिभुज को डेलाउने त्रिभुज में उन चरणों द्वारा फ़्लिप किया जा सकता है जिनमें चार बिंदुओं के कुछ सबसेट के त्रिभुज को इसके डेलाउने त्रिभुज द्वारा प्रतिस्थापित किया जाता है। प्रत्येक त्रिकोण के मूल के रूप में पहले डेलाउने फ़्लिप का चयन करना, और स्थानीय खोज को लागू करना, प्रति त्रिकोण बहुपद समय में सभी त्रिकोणों को सूचीबद्ध करने के लिए एक एल्गोरिथ्म उत्पन्न करता है। कनेक्टेड सबग्राफ एक दिए गए कनेक्टेड ग्राफ के कनेक्टेड सबग्राफ और कनेक्टेड इंड्यूस्ड सबग्राफ एक स्टेट स्पेस बनाते हैं, जिसकी स्थानीय चालें क्रमशः ग्राफ के एक किनारे या शीर्ष को जोड़ना या हटाना होती हैं। इस अवस्था स्थान का एक फैला हुआ वृक्ष पहले किनारे या शीर्ष (किनारों या शीर्षों के कुछ क्रम में) को जोड़कर प्राप्त किया जा सकता है जिसका जोड़ एक और जुड़ा हुआ उपलेख उत्पन्न करता है; इसका मूल पूरा ग्राफ है। इस राज्य स्थान और मूल प्रचालक पर स्थानीय खोज को लागू करने से सभी जुड़े उपग्राफ को बहुपद समय प्रति उपग्राफ में सूचीबद्ध करने के लिए एक एल्गोरिथ्म तैयार होता है। अन्य अनुप्रयोगों में निम्नलिखित संरचनाओं को उत्पन्न करने के लिए एल्गोरिदम शामिल हैंः पॉलीमिनोस, पॉलीअमोंड प्रोटोटाइल्स और पॉलीहेक्स (गणित) हाइड्रोकार्बन अणु। निर्देशित चक्रीय आलेखों के स्थलवैज्ञानिक क्रम, एक अवस्था स्थान का उपयोग करते हुए, जिसकी स्थानीय चालें दो तत्वों के क्रम को उलट देती हैं। ग्राफ के फैले हुए पेड़, समतल बिंदु सेट के फैले हुए पेड़ों को पार न करना, और आम तौर पर मैट्रोइड के आधार, एक राज्य स्थान का उपयोग करते हुए जो एक किनारे को दूसरे के लिए बदल देता है। यूलर ग्राफ में भ्रमण करते हैं। विरल आलेखों के अधिकतम स्वतंत्र समूह। अधिकतम समतलीय ग्राफ और पॉलीहेड्रल ग्राफ। किसी दिए गए बिंदु सेट पर गैर-पार करने वाले न्यूनतम कठोर ग्राफ। आसपास के बहुभुज, बहुभुज जिनमें कुछ दिए गए बिंदुओं को शीर्ष के रूप में होता है और बाकी को घेरते हैं, एक अवस्था स्थान का उपयोग करते हुए जो बहुभुज के एक शीर्ष को जोड़ता या हटाता है। उत्तल पॉलीटोप के मिन्कोव्स्की योग के शीर्ष या पहलू। एकाधिकार आदर्शों के कोने (बहु-डिग्री)। संदर्भ खोज एल्गोरिदम संयोजन एल्गोरिदम