बैकट्रैकिंग, शाखा-व-परिबंध व निम्न सीमा सिद्धांत

GATE के उधार लिए कलनविधि अध्याय विभाजन-और-जीत, गतिक प्रोग्रामन व लोभी अभिकल्प GATE की गहराई पर ढकते हैं। NET की इकाई 7 अतिरिक्त रूप से बैकट्रैकिंग व शाखा-व-परिबंध को अभिकल्प-तकनीकों के रूप में, तथा निम्न सीमा सिद्धांत (तुलना-वृक्ष, न्यूनन से निम्न सीमाएँ) को अपने ही प्रकरण के रूप में नामित करती है — इनमें से किसी को GATE CS नहीं परखता। यह अध्याय तीनों ढकता है।

बैकट्रैकिंग

बैकट्रैकिंग हल को वृद्धिशील रूप से बनाता है, एक बार में एक चुनाव, व आंशिक हल को उसी क्षण त्याग देता ('बैकट्रैक करता') है जब वह अमान्य या निराशाजनक सिद्ध हो सकता हो — उसे विस्तारित करते रहने व केवल अंत में जाँचने के बजाय। यही छंटाई बैकट्रैकिंग को हर पूर्ण प्रत्याशी की भोली प्रत्यक्ष-बल परिगणना से अलग करती है: बुरा आंशिक चुनाव उसे पूर्ण करने के (प्रायः घातांकी रूप से अनेक) तरीकों के कभी उत्पन्न होने से पहले त्याग दिया जाता है। N-रानी समस्या विहित उदाहरण है — रानियों को स्तंभ-दर-स्तंभ रखना व किसी पहले-रखी रानी पर आक्रमण करती स्तंभ-स्थिति को तुरंत अस्वीकार करना, न कि सभी N रानियाँ पहले रखकर बाद में पूरा बोर्ड जाँचना।

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

शाखा-व-परिबंध

शाखा-व-परिबंध भी आंशिक हलों का खोज-वृक्ष खोजता है, पर यह अनुकूलन समस्याओं को लक्षित करता है (केवल कोई वैध हल नहीं, सर्वश्रेष्ठ हल खोजें) व केवल वैधता-जाँच के बजाय संख्यात्मक सीमा से छाँटता है: हर नोड पर यह उस आंशिक हल से पहुँचने योग्य सर्वश्रेष्ठ संभव उद्देश्य-मान की सीमा गणित करता है (अधिकतमीकरण हेतु ऊर्ध्व सीमा, न्यूनतमीकरण हेतु अधो सीमा), व यदि वह सीमा अब तक मिले सर्वश्रेष्ठ पूर्ण हल को न हरा सके, तो उस नोड के नीचे का पूरा उपवृक्ष बिना खोजे त्याग दिया जाता है — यह ठीक वही तकनीक है जो इकाई 1 के अनुकूलन अध्याय में पूर्णांक प्रोग्रामन के LP-शिथिलन सीमा हेतु पहले ही प्रस्तुत की गई, यहाँ LP-विशिष्ट के बजाय सामान्य कलनविधि-अभिकल्प तकनीक के रूप में लागू।

बैकट्रैकिंग बनाम शाखा-व-परिबंध
गुणबैकट्रैकिंगशाखा-व-परिबंध
समस्या-प्रकारनिर्णय/सुसंगति (कोई भी वैध हल, या सभी)अनुकूलन (एकल सर्वश्रेष्ठ हल)
छंटाई परीक्षणक्या यह आंशिक अवस्था अभी भी वैध/सुसंगत है?क्या इस आंशिक अवस्था की सीमा अब तक मिले सर्वश्रेष्ठ हल को हरा सकती है?

निम्न सीमा सिद्धांत: तुलना-वृक्ष व न्यूनन

  • तुलना-वृक्ष (निर्णय-वृक्ष) किसी भी तुलना-आधारित कलनविधि को द्विआधारी वृक्ष के रूप में प्रतिरूपित करता है: हर आंतरिक नोड एक तुलना है, हर पत्ती एक संभव अंतिम परिणाम/निर्गम, व कलनविधि का निकृष्टतम-स्थिति चलने का समय कम-से-कम वृक्ष की ऊँचाई है, क्योंकि कोई निवेश उतने लंबे मूल-से-पत्ती पथ पर विवश करता है। चूँकि ऊँचाई h वाले द्विआधारी वृक्ष की अधिकतम 2^h पत्तियाँ होती हैं, व कलनविधि को कम-से-कम उतनी पत्तियाँ चाहिए जितने भिन्न संभव निर्गम हैं, ऊँचाई ≥ log₂(संभव निर्गमों की संख्या) — यही ठीक वह तर्क है जो सिद्ध करता है कि तुलना-आधारित वर्गीकरण को निकृष्टतम स्थिति में Ω(n log n) तुलनाएँ चाहिए: n! संभव क्रम हैं, अतः स्टर्लिंग सन्निकटन से ऊँचाई ≥ log₂(n!) = Ω(n log n)।
  • न्यूनन से निम्न सीमाएँ: यह सिद्ध करने हेतु कि समस्या B कम-से-कम पहले से ज्ञात-कठिन समस्या A जितनी कठिन है, दिखाएँ कि A को A के किसी दृष्टांत को (परिबद्ध लागत पर) B के दृष्टांत में रूपांतरित कर व B हेतु किसी काल्पनिक कलनविधि को बुलाकर हल किया जा सकता है — यदि B को A की ज्ञात निम्न सीमा (प्लस सस्ती रूपांतरण-लागत) से तेज़ हल किया जा सकता, तो A भी हो सकता, A के विषय में पहले से ज्ञात के विरुद्ध जाते हुए। यही न्यूनन-विचार सम्पूर्ण जटिलता-सिद्धांत में प्रयुक्त होता है (अगले अध्याय में NP-पूर्णता प्रमाणों सहित), यहाँ केवल किसी निर्णय-समस्या को वर्गीकृत करने के बजाय निम्न सीमा सिद्ध करने पर लक्षित।
⚠️ निम्न सीमा **हर** कलनविधि की बात है, ऊर्ध्व सीमा **एक** कलनविधि की
यह सिद्ध करना कि मर्जसॉर्ट O(n log n) में चलता है वर्गीकरण-समस्या पर ऊर्ध्व सीमा है (एक कलनविधि यह प्राप्त करती है)। यह सिद्ध करना कि तुलना-आधारित वर्गीकरण को Ω(n log n) तुलनाएँ चाहिए स्वयं वर्गीकरण-समस्या पर निम्न सीमा है (कोई भी तुलना-आधारित कलनविधि, चाहे कितनी चतुराई से अभिकल्पित हो, इसे नहीं हरा सकती)। चूँकि ये दोनों सीमाएँ मेल खाती हैं (दोनों n log n), तुलना-वर्गीकरण को इष्टतम कहा जाता है — यह दावा अकेली ऊर्ध्व सीमा से नहीं किया जा सकता था, क्योंकि तेज़ कलनविधि तब तक खोजी जाने की प्रतीक्षा में हो सकती थी जब तक मेल खाती निम्न सीमा उसे रद्द न कर दे।

हल किए उदाहरण: N-रानी, 0/1 नैपसैक व सुडोकू

  • बैकट्रैकिंग से N-रानी: प्रति पंक्ति एक रानी रखें, उस पंक्ति में स्तंभ-दर-स्तंभ। रखने से पहले, नई स्थिति को हर पहले-रखी रानी के विरुद्ध समान-स्तंभ या समान-विकर्ण टकराव हेतु जाँचें (पंक्ति/स्तंभ/विकर्ण अंतर से प्रति-जाँच O(1) परीक्षण); टकराव पर, उस पंक्ति में अगला स्तंभ आज़माएँ; यदि वर्तमान पंक्ति में कोई स्तंभ काम न करे, पिछली पंक्ति पर बैकट्रैक करें व उसका अगला विकल्प आज़माएँ।
  • शाखा-व-परिबंध से 0/1 नैपसैक: हर नोड पर (वस्तुओं के किसी उपसर्ग पर आंशिक निर्णय), मान-भार अनुपात से क्रमित शेष वस्तुओं के भिन्नात्मक शिथिलन से प्राप्य मान की ऊर्ध्व सीमा गणित करें (वही लोभी सीमा जिसे भिन्नात्मक नैपसैक ठीक-ठीक हल करता है) — चूँकि यह भिन्नात्मक सीमा उस नोड से पहुँचने योग्य वास्तविक 0/1 इष्टतम से सदा कम-से-कम उतनी है, जिस भी नोड की सीमा अब तक मिले सर्वश्रेष्ठ 0/1 हल से नीचे गिरे उसे पूर्णतः छाँटा जा सकता है।
  • बैकट्रैकिंग से सुडोकू: कोष्ठिकाएँ स्थिर क्रम में भरें; अंक रखने से पहले, दोहराव हेतु पंक्ति, स्तंभ व 3×3 बॉक्स जाँचें — एक तत्काल, सस्ती प्रतिबंध-जाँच जो खोज-वृक्ष के विशाल भाग को उसके कभी उत्पन्न होने से पहले ही त्याग देती है, यही ठीक वह छंटाई-प्रबलता का मुद्दा है जो पहले के टिप्पण से आया।

मुख्य बिंदु

  • बैकट्रैकिंग आंशिक हल को उसी क्षण त्याग देता है जब वह सिद्ध रूप से अमान्य हो, संपूर्ण परिगणना से पहले छाँटते हुए; दुर्बल छंटाई-नियम इसे प्रत्यक्ष-बल की ओर अपकर्षित करता है।
  • शाखा-व-परिबंध अनुकूलन-समस्या के उपवृक्ष अब तक मिले सर्वश्रेष्ठ पूर्ण हल के विरुद्ध तुलनित संख्यात्मक सीमा से छाँटता है — पूर्णांक प्रोग्रामन के LP-शिथिलन सीमा वाला ही विचार, सामान्यीकृत।
  • तुलना-वृक्ष की ऊँचाई तुलना-आधारित कलनविधि की निकृष्टतम स्थिति की निम्न सीमा देती है; यह सिद्ध करती है कि तुलना-वर्गीकरण को Ω(n log n) तुलनाएँ चाहिए।
  • न्यूनन से निम्न सीमा दिखाती है कि समस्या B कम-से-कम पहले से ज्ञात-कठिन समस्या A जितनी कठिन है, A को B में सस्ते में रूपांतरित करके।
  • निम्न सीमा हर संभव कलनविधि को बाधित करती है; ऊर्ध्व सीमा एक कलनविधि से प्राप्त होती है — मेल खाती सीमाएँ इष्टतमता सिद्ध करती हैं।

अभ्यास प्रश्न (8)

उत्तर खोलने से पहले प्रत्येक प्रश्न हल करें। हर व्याख्या सही विकल्प के साथ लुभावना गलत विकल्प भी बताती है, क्योंकि अंक वहीं जाते हैं।

  1. बैकट्रैकिंग हर पूर्ण प्रत्याशी की भोली प्रत्यक्ष-बल परिगणना से मुख्यतः इस प्रकार भिन्न है कि यह:

    1. आंशिक हल को उसी क्षण त्याग देता है जब वह सिद्ध रूप से अमान्य हो, उसे पूर्ण करने के तरीके उत्पन्न करने से पहले
    2. बहरहाल हर संभव पूर्ण प्रत्याशी को देखता है
    3. किसी भी आंशिक अवस्था की कभी जाँच नहीं करता
    4. किसी समस्या-विशिष्ट वैधता-जाँच की बिल्कुल आवश्यकता नहीं
    उत्तर देखें

    उत्तर: A — आंशिक हल को उसी क्षण त्याग देता है जब वह सिद्ध रूप से अमान्य हो, उसे पूर्ण करने के तरीके उत्पन्न करने से पहले

    आंशिक (अपूर्ण) हल पर लागू छंटाई-जाँच ही ठीक वह है जो पहले से अमान्य आंशिक हल को विस्तारित करने वाले घातांकी रूप से अनेक पूर्ण प्रत्याशियों को उत्पन्न होने से बचाती है।

  2. बैकट्रैकिंग की तुलना में, शाखा-व-परिबंध विशेष रूप से इस हेतु अभिकल्पित है:

    1. अनुकूलन समस्याएँ, अब तक मिले सर्वश्रेष्ठ हल के विरुद्ध संख्यात्मक सीमा से छाँटते हुए
    2. केवल निर्णय समस्याएँ, अकेली वैधता-जाँच सहित
    3. बिना किसी संख्यात्मक उद्देश्य वाली समस्याएँ
    4. विशेष रूप से वर्गीकरण समस्याएँ
    उत्तर देखें

    उत्तर: A — अनुकूलन समस्याएँ, अब तक मिले सर्वश्रेष्ठ हल के विरुद्ध संख्यात्मक सीमा से छाँटते हुए

    शाखा-व-परिबंध अनुकूलन समस्या का एकल सर्वश्रेष्ठ हल खोजने को लक्षित करता है, आंशिक अवस्था से प्राप्य सर्वश्रेष्ठ उद्देश्य-मान की सीमा प्रयोग कर यह तय करते हुए कि वह उपवृक्ष खोजने योग्य है भी या नहीं।

  3. शाखा-व-परिबंध से हल 0/1 नैपसैक में, हर नोड पर सीमा सामान्यतः इससे गणित की जाती है:

    1. शेष वस्तुओं का भिन्नात्मक शिथिलन हल करके
    2. शेष सभी वस्तुओं को पूर्णतः नज़रअंदाज़ करके
    3. सदा यह मानकर कि नैपसैक रिक्त है
    4. यादृच्छिक रूप से किसी संख्या का अनुमान लगाकर
    उत्तर देखें

    उत्तर: A — शेष वस्तुओं का भिन्नात्मक शिथिलन हल करके

    भिन्नात्मक नैपसैक का लोभी हल वह मान देता है जो उस नोड से प्राप्य वास्तविक 0/1 इष्टतम जितना अच्छा या उससे अच्छा सदा होता है, इसे छंटाई हेतु वैध (व गणना करने में सस्ती) ऊर्ध्व सीमा बनाते हुए।

  4. तुलना-वृक्ष तर्क सिद्ध करता है कि तुलना-आधारित वर्गीकरण को, निकृष्टतम स्थिति में, कम-से-कम इतनी आवश्यकता है:

    1. Ω(n log n) तुलनाएँ
    2. ठीक n तुलनाएँ, कभी अधिक नहीं
    3. शून्य तुलनाएँ
    4. अनंत तुलनाएँ
    उत्तर देखें

    उत्तर: A — Ω(n log n) तुलनाएँ

    तुलना (निर्णय) वृक्ष की पत्तियों के रूप में n! संभव क्रमों सहित, वृक्ष की ऊँचाई कम-से-कम log₂(n!) होनी ही चाहिए, जो स्टर्लिंग सन्निकटन से Ω(n log n) है।

  5. पहले से ज्ञात-कठिन समस्या A से न्यूनन द्वारा समस्या B हेतु निम्न सीमा सिद्ध करने में सम्मिलित है:

    1. A के किसी दृष्टांत को B के दृष्टांत में सस्ते में रूपांतरित करना, ताकि B हेतु तेज़ कलनविधि A हेतु एक दे दे
    2. यह सिद्ध करना कि A सरल है, कठिन नहीं
    3. समस्या A को पूर्णतः नज़रअंदाज़ करना
    4. केवल वर्गीकरण समस्याओं पर लागू होता है
    उत्तर देखें

    उत्तर: A — A के किसी दृष्टांत को B के दृष्टांत में सस्ते में रूपांतरित करना, ताकि B हेतु तेज़ कलनविधि A हेतु एक दे दे

    यदि B को A की ज्ञात निम्न सीमा (प्लस सस्ता रूपांतरण) से तेज़ हल किया जा सकता, तो A भी उतनी तेज़ी से हल हो सकता — A के विषय में पहले से ज्ञात के विरुद्ध जाते हुए, जो B को कम-से-कम उतना कठिन होने पर बाध्य करता है।

  6. बैकट्रैकिंग से हल N-रानी के विषय में निम्नलिखित में कौन सत्य हैं? (एक से अधिक विकल्प सही हो सकते हैं।)

    1. नई रानी की स्थिति स्वीकार किए जाने से पहले हर पहले-रखी रानी के विरुद्ध जाँची जाती है
    2. टकराव पर, कलनविधि वर्तमान पंक्ति में अगला स्तंभ आज़माती है
    3. यदि वर्तमान पंक्ति में कोई स्तंभ काम न करे, यह पिछली पंक्ति पर बैकट्रैक करती है
    4. यह सदा बिना किसी जाँच के सभी N रानियाँ रखती है
    उत्तर देखें

    उत्तर: A — नई रानी की स्थिति स्वीकार किए जाने से पहले हर पहले-रखी रानी के विरुद्ध जाँची जाती है; B — टकराव पर, कलनविधि वर्तमान पंक्ति में अगला स्तंभ आज़माती है; C — यदि वर्तमान पंक्ति में कोई स्तंभ काम न करे, यह पिछली पंक्ति पर बैकट्रैक करती है

    जाँचें-फिर-रखें-या-पुनः-आज़माएँ-या-बैकट्रैक करें चक्र ही ठीक बैकट्रैकिंग क्रियाविधि है; बिना किसी जाँच के सभी रानियाँ रखना इसके बजाय केवल अंत में वैधता जाँची जाती प्रत्यक्ष-बल परिगणना होती।

  7. उस वृक्ष का नाम बताइए जो किसी भी तुलना-आधारित कलनविधि को प्रतिरूपित करने हेतु प्रयुक्त होता है, जिसकी ऊँचाई कलनविधि के निकृष्टतम-स्थिति चलने के समय की निम्न सीमा देती है।

    संख्यात्मक उत्तर — मान टाइप करें।

    उत्तर देखें

    उत्तर: comparison tree

    तुलना (निर्णय) वृक्ष की पत्तियाँ संभव निर्गमों से संगत होती हैं, और चूँकि ऊँचाई h वाले द्विआधारी वृक्ष की अधिकतम 2^h पत्तियाँ होती हैं, ऊँचाई संभव निर्गमों की संख्या के लॉग के बराबर या उससे अधिक होनी ही चाहिए।

  8. शाखा-व-परिबंध खोज के उपवृक्ष को छाँटने हेतु प्रयुक्त अधिकतम-प्रवाह/न्यूनतम-कट-शैली सीमा तब पूर्णतः त्यागी जाती है जब:

    1. सीमा अब तक मिले सर्वश्रेष्ठ पूर्ण हल को न हरा सके
    2. सीमा ठीक अब तक मिले सर्वश्रेष्ठ हल के बराबर हो
    3. उपवृक्ष पहले कभी देखा न गया हो
    4. कलनविधि अभी आरंभ न हुई हो
    उत्तर देखें

    उत्तर: A — सीमा अब तक मिले सर्वश्रेष्ठ पूर्ण हल को न हरा सके

    जिस उपवृक्ष की सर्वश्रेष्ठ-स्थिति सीमा पहले से हाथ में मौजूद हल से पहले ही बुरी हो, वह कुछ भी बेहतर नहीं रख सकता, अतः पूरे उपवृक्ष को बिना खोजे त्यागना सुरक्षित है।