ब्रूट-फोर्स सर्च

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

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

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

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

ब्रूट-फोर्स सर्च को लागू करना

बेसिक एल्गोरिथम

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

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

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

सी ← पहले (पी)
'जबकि' सी ≠ Λ 'करो'
    'अगर' वैध (पी, सी) 'तो'
        आउटपुट (पी, सी)
    सी ← अगला (पी, सी)
'अंत जबकि'

उदाहरण के लिए, जब पूर्णांक n के भाजक की तलाश की जाती है, तो उदाहरण डेटा P संख्या n होता है। कॉल पहले (n) को पूर्णांक 1 वापस करना चाहिए यदि n ≥ 1, या Λ अन्यथा; अगली कॉल (एन, सी) को सी + 1 वापस करना चाहिए यदि सी <एन, और Λ अन्यथा; और वैध (एन, सी) को 'सत्य' वापस करना चाहिए अगर और केवल अगर सी एन का विभाजक है। (वास्तव में, यदि हम Λ को 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 से शुरू करके और 1,000,000 से अधिक होने तक बार-बार 417 जोड़कर और अधिक कुशलता से हल किया जा सकता है – जो केवल 2398 (= 1,000,000 ÷ 417) कदम उठाता है, और कोई परीक्षण नहीं करता है।

खोज स्थान को पुनर्क्रमित करना

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

ब्रूट-फोर्स सर्च के विकल्प

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

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

Main article: Brute-force attack

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

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

यह भी देखें

• सुडोकू सॉल्विंग एल्गोरिदम # सुडोकू ब्रूट फोर्स | सुडोकू पहेली को हल करने के लिए एक ब्रूट-फोर्स एल्गोरिदम।
• पशुबल का आक्रमण
• बिग ओ नोटेशन

श्रेणी:खोज एल्गोरिदम