पाशविक बल खोज

This article is about the problem-solving technique in computer science. For similarly named methods in other disciplines, see Brute force (disambiguation).

कंप्यूटर विज्ञान में, ब्रूट-फोर्स सर्च या संपूर्ण खोज, जिसे जनरेट और टेस्ट के रूप में भी जाना जाता है, एक बहुत ही सामान्य समस्या-समाधान तकनीक और एल्गोरिथम प्रतिमान है जिसमें प्रत्येक उम्मीदवार समस्या के कथन को संतुष्ट करता है या नहीं, इसके लिए सभी संभावित उम्मीदवारों की Iteration#Computing शामिल है।

एक क्रूर-बल एल्गोरिदम जो एक प्राकृतिक संख्या एन के विभाजक को ढूंढता है, वह 1 से एन तक सभी पूर्णांकों की गणना करेगा, और जांच करेगा कि क्या उनमें से प्रत्येक एन को बिना किसी शेषफल के विभाजित करता है। आठ रानियों की पहेली के लिए एक क्रूर-बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 टुकड़ों की सभी संभावित व्यवस्था की जांच करेगा और प्रत्येक व्यवस्था के लिए, जांच करेगा कि क्या प्रत्येक (रानी) टुकड़ा किसी अन्य पर हमला कर सकता है। जबकि एक क्रूर-बल खोज सॉफ़्टवेयर के लिए सरल है और यदि कोई समाधान मौजूद है तो वह हमेशा एक समाधान ढूंढेगा, कार्यान्वयन लागत उम्मीदवार समाधानों की संख्या के समानुपाती होती है – जो कई व्यावहारिक समस्याओं में समस्या का आकार बढ़ने के साथ बहुत तेजी से बढ़ने लगता है (#कॉम्बिनेटरियल विस्फोट|§कॉम्बिनेटरियल विस्फोट)। इसलिए, ब्रूट-फोर्स सर्च का उपयोग आम तौर पर तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमान (कंप्यूटर विज्ञान) होते हैं जिनका उपयोग प्रबंधनीय आकार के उम्मीदवार समाधानों के सेट को कम करने के लिए किया जा सकता है। इस पद्धति का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।

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

क्रूर-बल खोज को लागू करना

बुनियादी एल्गोरिदम

वर्तमान सी के बाद पी के लिए उम्मीदवार के क्रम में।

1. वैध (पी, सी): जांचें कि क्या उम्मीदवार सी, पी का समाधान है।
2. आउटपुट (पी, सी): एप्लिकेशन के लिए उपयुक्त पी के समाधान सी का उपयोग करें।

अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान सी के बाद उदाहरण पी के लिए कोई और उम्मीदवार कब नहीं हैं। ऐसा करने का एक सुविधाजनक तरीका एक शून्य उम्मीदवार को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो किसी भी वास्तविक उम्मीदवार से अलग है। इसी तरह पहली प्रक्रिया को Λ लौटाना चाहिए यदि उदाहरण पी के लिए कोई उम्मीदवार नहीं है। ब्रूट-फोर्स विधि को एल्गोरिदम द्वारा व्यक्त किया जाता है

सी ← प्रथम(पी)
'जबकि' c ≠ Λ 'करो'
    'यदि' वैध(पी,सी) 'तब'
        आउटपुट (पी, सी)
    सी ← अगला(पी, सी)
'अभी ख़त्म'

उदाहरण के लिए, जब किसी पूर्णांक n के विभाजक की तलाश की जाती है, तो उदाहरण डेटा P संख्या n है। कॉल फर्स्ट(एन) को पूर्णांक 1 लौटाना चाहिए यदि एन ≥ 1, या अन्यथा; कॉल नेक्स्ट(n,c) को c + 1 लौटना चाहिए यदि c < n, और Λ अन्यथा; और वैध(एन,सी) को 'सही' लौटाना चाहिए यदि और केवल यदि सी एन का विभाजक है। (वास्तव में, यदि हम Λ को n + 1 के रूप में चुनते हैं, तो परीक्षण n ≥ 1 और c < n अनावश्यक हैं।) उपरोक्त जानवर-बल खोज एल्गोरिदम प्रत्येक उम्मीदवार के लिए आउटपुट को कॉल करेगा जो दिए गए उदाहरण पी का समाधान है। पहला समाधान, या समाधानों की एक निर्दिष्ट संख्या खोजने के बाद रुकने के लिए एल्गोरिदम को आसानी से संशोधित किया जाता है; या उम्मीदवारों की एक निर्दिष्ट संख्या का परीक्षण करने के बाद, या केंद्रीय प्रसंस्करण इकाई समय की एक निश्चित राशि खर्च करने के बाद।

संयुक्त विस्फोट

पशु-बल पद्धति का मुख्य नुकसान यह है कि, वास्तविक दुनिया की कई समस्याओं के लिए, प्राकृतिक उम्मीदवारों की संख्या निषेधात्मक रूप से बड़ी है। उदाहरण के लिए, यदि हम ऊपर वर्णित किसी संख्या के भाजक की तलाश करते हैं, तो परीक्षण किए गए उम्मीदवारों की संख्या दी गई संख्या n होगी। इसलिए यदि n में सोलह दशमलव अंक हैं, तो खोज के लिए कम से कम 10 निष्पादित करने की आवश्यकता होगी¹⁵कंप्यूटर निर्देश, जिसमें एक सामान्य व्यक्तिगत कंप्यूटर पर कई दिन लगेंगे। यदि n एक यादृच्छिक 64-बाइनरी अंकों वाली प्राकृतिक संख्या है, जिसमें औसतन लगभग 19 दशमलव अंक हैं, तो खोज में लगभग 10 वर्ष लगेंगे। जैसे-जैसे डेटा का आकार बढ़ता है, उम्मीदवारों की संख्या में यह भारी वृद्धि सभी प्रकार की समस्याओं में होती है। उदाहरण के लिए, यदि हम 10 अक्षरों की एक विशेष पुनर्व्यवस्था चाह रहे हैं, तो हमारे पास 10 हैं! = 3,628,800 उम्मीदवारों पर विचार किया जाना है, जिसे एक सामान्य पीसी एक सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। हालाँकि, एक अक्षर और जोड़ रहा हूँ – जो डेटा आकार में केवल 10% की वृद्धि है – उम्मीदवारों की संख्या 11 से गुणा हो जाएगी, 1000% की वृद्धि। 20 अक्षरों के लिए, उम्मीदवारों की संख्या 20 है!, जो लगभग 2.4×10 है¹⁸या 2.4 क्विंटिलियन; और खोज में लगभग 10 साल लगेंगे। इस अवांछित घटना को आमतौर पर कॉम्बिनेटरियल विस्फोट, या आयामीता का अभिशाप कहा जाता है।

ऐसे मामले का एक उदाहरण जहां संयुक्त जटिलता से सॉल्वैबिलिटी सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई सुलझा हुआ खेल नहीं है. 2005 में, छह मोहरों या उससे कम वाले सभी शतरंज खेल के अंत को हल कर दिया गया था, यदि पूरी तरह से खेला जाए तो प्रत्येक स्थिति का परिणाम दिखाया गया था। टेबलबेस को पूरा करने में एक और शतरंज का टुकड़ा जोड़कर दस साल और लग गए, इस प्रकार 7-टुकड़ों वाला टेबलबेस पूरा हो गया। शतरंज के अंत में एक और टुकड़ा जोड़ना (इस प्रकार 8-टुकड़ों का टेबलबेस बनाना) अतिरिक्त संयोजक जटिलता के कारण कठिन माना जाता है।

जानवर-बल वाली खोजों को तेज़ करना

ब्रूट-फोर्स एल्गोरिदम को तेज़ करने का एक तरीका समस्या वर्ग के लिए विशिष्ट अनुमानों का उपयोग करके खोज स्थान, यानी उम्मीदवार समाधानों के सेट को कम करना है। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को एक मानक शतरंज की बिसात पर रखने की चुनौती है ताकि कोई भी रानी किसी अन्य पर हमला न करे। चूँकि प्रत्येक रानी को 64 वर्गों में से किसी एक में रखा जा सकता है, सिद्धांततः 64 ही हैं⁸ = 281,474,976,710,656 संभावनाओं पर विचार करना। हालाँकि, क्योंकि सभी रानियाँ एक जैसी हैं, और किसी भी दो रानियों को एक ही वर्ग में नहीं रखा जा सकता है, उम्मीदवार सभी 64 वर्गों के सेट से 8 वर्गों के एक सेट का संयोजन हैं; जिसका अर्थ है 64 चुनें 8 = 64!/(56!*8!) = 4,426,165,368 उम्मीदवार समाधान – पिछले अनुमान का लगभग 1/60,000। इसके अलावा, एक ही पंक्ति या एक ही कॉलम पर दो रानियों के साथ कोई भी व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम उम्मीदवारों के समूह को उन व्यवस्थाओं तक ही सीमित कर सकते हैं।

जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अक्सर उम्मीदवार समाधानों की संख्या में नाटकीय कमी ला सकता है, और एक कठिन समस्या को मामूली समस्या में बदल सकता है।

कुछ मामलों में, विश्लेषण उम्मीदवारों को सभी वैध समाधानों के सेट तक सीमित कर सकता है; यानी, यह एक एल्गोरिदम उत्पन्न कर सकता है जो परीक्षणों और अमान्य उम्मीदवारों की पीढ़ी के साथ समय बर्बाद किए बिना, सीधे सभी वांछित समाधानों की गणना करता है (या उपयुक्त के रूप में एक समाधान ढूंढता है)। उदाहरण के लिए, समस्या के लिए 1 और 1,000,000 के बीच सभी पूर्णांक खोजें जो 417 से समान रूप से विभाज्य हों, एक सहज बल-बल समाधान सीमा में सभी पूर्णांक उत्पन्न करेगा, उनमें से प्रत्येक को विभाज्यता के लिए परीक्षण करेगा। हालाँकि, उस समस्या को 417 से शुरू करके और बार-बार 417 जोड़कर तब तक अधिक कुशलता से हल किया जा सकता है जब तक कि संख्या 1,000,000 से अधिक न हो जाए। – जिसमें केवल 2398 (= 1,000,000 ÷ 417) कदम लगते हैं, और कोई परीक्षण नहीं होता।

खोज स्थान को पुनः व्यवस्थित करना

ऐसे अनुप्रयोगों में जिन्हें सभी समाधानों के बजाय केवल एक समाधान की आवश्यकता होती है, एक क्रूर बल खोज का अपेक्षित मूल्य चलने का समय अक्सर उस क्रम पर निर्भर करेगा जिसमें उम्मीदवारों का परीक्षण किया जाता है। एक सामान्य नियम के रूप में, सबसे पहले सबसे होनहार उम्मीदवारों का परीक्षण करना चाहिए। उदाहरण के लिए, किसी यादृच्छिक संख्या n के उचित भाजक की खोज करते समय, उम्मीदवार भाजक को 2 से बढ़ते क्रम में गिनना बेहतर होता है। n − 1, इसके विपरीत – क्योंकि n के c से विभाज्य होने की प्रायिकता 1/c है। इसके अलावा, किसी उम्मीदवार के वैध होने की संभावना अक्सर पिछले असफल परीक्षणों से प्रभावित होती है। उदाहरण के लिए, किसी दिए गए 1000-बिट स्ट्रिंग पी में '1' बिट खोजने की समस्या पर विचार करें। इस मामले में, उम्मीदवार समाधान 1 से 1000 के सूचकांक हैं, और एक उम्मीदवार सी वैध है यदि पी[सी] = '1 '. अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान संभावना है, लेकिन उसके बाद प्रत्येक बिट 90% संभावना के साथ पिछले बिट के बराबर है। यदि उम्मीदवारों की गणना बढ़ते क्रम में की जाए, 1 से 1000, तो सफलता से पहले जांचे गए उम्मीदवारों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि उम्मीदवारों की गणना 1,11,21,31...991,2,12,22,32 आदि क्रम में की जाती है, तो t का अपेक्षित मान 2 से थोड़ा ही अधिक होगा। आम तौर पर, खोज स्थान की गणना इस तरह से की जानी चाहिए कि अगले उम्मीदवार के वैध होने की सबसे अधिक संभावना हो, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में क्लस्टर किए जाने की संभावना है, तो प्रत्येक नए उम्मीदवार को उसी अर्थ में, पिछले वाले से यथासंभव दूर होना चाहिए। निःसंदेह, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैलने की संभावना है, तो यह विपरीत है।

पाशविक खोज के विकल्प

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

क्रिप्टोग्राफी में

Main article: Brute-force attack

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

एन्क्रिप्शन में उपयोग की जाने वाली कुंजी लंबाई क्रूर बल के हमले को करने की व्यावहारिक व्यवहार्यता निर्धारित करती है, छोटी कुंजी की तुलना में लंबी कुंजी को क्रैक करना तेजी से अधिक कठिन होता है। एन्कोड किए जाने वाले डेटा को अस्पष्ट करके क्रूर बल के हमलों को कम प्रभावी बनाया जा सकता है, जिससे किसी हमलावर के लिए यह पहचानना अधिक कठिन हो जाता है कि उसने कोड को कब क्रैक किया है। एन्क्रिप्शन प्रणाली की ताकत का एक माप यह है कि सैद्धांतिक रूप से एक हमलावर को इसके खिलाफ एक सफल क्रूर हमला करने में कितना समय लगेगा।

यह भी देखें

• सुडोकू सुलझाने वाले एल्गोरिदम#सुडोकू क्रूर बल|सुडोकू पहेलियों को हल करने के लिए एक जानवर-बल एल्गोरिदम।
• पशुबल का आक्रमण
• बिग ओ अंकन
• पुनरावृत्ति#कंप्यूटिंग

श्रेणी:खोज एल्गोरिदम श्रेणी:प्रोग्रामिंग में पुनरावृत्ति