ब्रूट-फोर्स सर्च: Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
 
(10 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Problem-solving technique and algorithmic paradigm}}
{{Short description|Problem-solving technique and algorithmic paradigm}}
{{about|कंप्यूटर विज्ञान में समस्या समाधान तकनीक|अन्य विषयों में इसी प्रकार नामित विधियाँ|पाशविक शक्ति (असंबद्धता)}}
{{about|कंप्यूटर विज्ञान में समस्या समाधान तकनीक|अन्य विषयों में इसी प्रकार नामित विधियाँ|ब्रूट-फोर्स (असंबद्धता)}}
[[कंप्यूटर विज्ञान]] में, ब्रूट-फोर्स सर्च या एक्सक्लूसिव सर्च, जिसे जेनरेट और टेस्ट के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान तकनीक और [[एल्गोरिथम प्रतिमान]] है जिसमें समाधान के लिए सभी संभावित उम्मीदवारों की व्यवस्थित रूप से गणना करना और यह जांचना शामिल है कि प्रत्येक उम्मीदवार समस्या के बयान को संतुष्ट करता है या नहीं। .
[[कंप्यूटर विज्ञान]] में, ब्रूट-फोर्स सर्च या विस्तृत सर्च, जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान विधि और [[एल्गोरिथम प्रतिमान]] है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के कथन को संतुष्ट करता है या नहीं करता है।


एक ब्रूट-फोर्स एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''n'' के [[भाजक|विभाजकों]]   को खोजता है, 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि क्या उनमें से प्रत्येक ''n'' को शेष के बिना विभाजित करता है। आठ रानियों की पहेली के लिए क्रूर-बल दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 टुकड़ों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक (रानी) टुकड़ा किसी अन्य पर हमला कर सकता है या नहीं।<ref>{{Cite web|date=2020-01-06|title=ब्रूट फ़ोर्स एल्गोरिदम समझाया गया|url=https://www.freecodecamp.org/news/brute-force-algorithms-explained/|access-date=2021-04-11|website=freeCodeCamp.org|language=en}}</ref>
एक ब्रूट-फोर्स एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''n'' के [[भाजक|विभाजकों]] को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए ब्रूट-फोर्स दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 भागों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक(रानी) भाग किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।<ref>{{Cite web|date=2020-01-06|title=ब्रूट फ़ोर्स एल्गोरिदम समझाया गया|url=https://www.freecodecamp.org/news/brute-force-algorithms-explained/|access-date=2021-04-11|website=freeCodeCamp.org|language=en}}</ref>
जबकि ब्रूट-फोर्स सर्च [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] के लिए सरल है और यदि यह मौजूद है तो हमेशा समाधान मिलेगा, कार्यान्वयन लागत उम्मीदवार समाधानों की संख्या के समानुपाती होती है{{snd}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तेज़ी से बढ़ने लगता है (#Combinatorial विस्फोट|§Combinatorial विस्फोट)।<ref>{{cite web |title=क्रूर बल खोज की जटिलता|url=https://www.coursera.org/learn/ml-clustering-and-retrieval/lecture/5R6q3/complexity-of-brute-force-search |website=coursera |access-date=14 June 2018}}</ref> इसलिए, ब्रूट-फोर्स सर्च का उपयोग आमतौर पर तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट ह्यूरिस्टिक (कंप्यूटर साइंस) होते हैं, जिनका उपयोग उम्मीदवार के समाधान के सेट को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।


यह मामला है, उदाहरण के लिए, महत्वपूर्ण अनुप्रयोगों में जहां [[कलन विधि]] में किसी भी त्रुटि के बहुत गंभीर परिणाम होंगे या जब स्वचालित प्रमेय सिद्ध हो रहे हों। अन्य एल्गोरिदम या [[मेटाह्यूरिस्टिक]]्स को [[ बेंच मार्किंग |बेंच मार्किंग]] करते समय ब्रूट-फोर्स खोज आधारभूत विधि के रूप में भी उपयोगी होती है। दरअसल, ब्रूट-फोर्स सर्च को सबसे सरल मेटाह्यूरिस्टिक के रूप में देखा जा सकता है। ब्रूट फ़ोर्स सर्च को [[ बैक ट्रैकिंग |बैक ट्रैकिंग]] के साथ भ्रमित नहीं होना चाहिए, जहां समाधानों के बड़े सेटों को स्पष्ट रूप से गणना किए बिना त्याग दिया जा सकता है (जैसा कि ऊपर आठ रानियों की समस्या के पाठ्यपुस्तक कंप्यूटर समाधान में है)। तालिका में किसी आइटम को खोजने के लिए क्रूर-बल विधि{{snd}}अर्थात्, बाद की सभी प्रविष्टियों की क्रमिक रूप से जाँच करें{{snd}}रेखीय खोज कहा जाता है।
यद्यपि ब्रूट-फोर्स सर्च [[ सॉफ़्टवेयर |सॉफ़्टवेयर]] को प्रयुक्त करना आसान है और यदि यह उपस्थित है तो सदैव एक समाधान मिलेगा, कार्यान्वयन निवेश उम्मीदवार समाधानों की संख्या के अनुपात में होती है{{snd}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§ संयुक्त विस्फोट)।<ref>{{cite web |title=क्रूर बल खोज की जटिलता|url=https://www.coursera.org/learn/ml-clustering-and-retrieval/lecture/5R6q3/complexity-of-brute-force-search |website=coursera |access-date=14 June 2018}}</ref> इसलिए, ब्रूट-फोर्स सर्च का उपयोग सामान्यतः तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमानिकीय होते हैं, जिनका उपयोग प्रत्याशी के समाधान के समुच्चय को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।


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


=== बेसिक एल्गोरिथम ===
=== बेसिक एल्गोरिथम ===
क्रम में वर्तमान के बाद पी के लिए उम्मीदवार सी।
क्रम में वर्तमान के बाद P के लिए प्रत्याशी c।
# वैध (पी, सी): जांचें कि उम्मीदवार सी पी के लिए समाधान है या नहीं।
# वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है।
# आउटपुट (पी, सी): आवेदन के लिए उपयुक्त के रूप में पी के समाधान सी का उपयोग करें।
# आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें।
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान सी के बाद पी के लिए कोई और उम्मीदवार नहीं हैं। ऐसा करने का सुविधाजनक तरीका अशक्त उम्मीदवार को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक उम्मीदवार से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण पी के लिए कोई उम्मीदवार नहीं हैं। ब्रूट-बल विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान एक c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने की सुविधाजनक विधि "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट-फोर्स विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:<syntaxhighlight>
 
c ← first(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    c ← next(P, c)
end while
</syntaxhighlight>


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


== मिश्रित विस्फोट ==
== संयोजक विस्फोट ==
क्रूर-बल पद्धति का मुख्य नुकसान यह है कि, वास्तविक दुनिया की कई समस्याओं के लिए, प्राकृतिक उम्मीदवारों की संख्या निषेधात्मक रूप से बड़ी है। उदाहरण के लिए, यदि हम ऊपर वर्णित संख्या के विभाजक की तलाश करते हैं, तो परीक्षण किए गए उम्मीदवारों की संख्या दी गई संख्या n होगी। इसलिए यदि n में सोलह दशमलव अंक हैं, तो खोज के लिए कम से कम 10 क्रियान्वित करने की आवश्यकता होगी<sup>15</sup> कंप्यूटर निर्देश, जिसमें विशिष्ट व्यक्तिगत कंप्यूटर पर कई दिन लगेंगे। यदि n यादृच्छिक 64-बाइनरी अंकों की प्राकृतिक संख्या है, जिसमें औसतन लगभग 19 दशमलव अंक हैं, तो खोज में लगभग 10 वर्ष लगेंगे। उम्मीदवारों की संख्या में यह तीव्र वृद्धि, जैसे-जैसे डेटा का आकार बढ़ता है, सभी प्रकार की समस्याओं में होता है। उदाहरण के लिए, यदि हम 10 अक्षरों की विशेष पुनर्व्यवस्था की मांग कर रहे हैं, तो हमारे पास 10 हैं! = 3,628,800 उम्मीदवारों पर विचार करने के लिए, जो विशिष्ट पीसी सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। हालाँकि, और पत्र जोड़ना{{snd}}जो डेटा आकार में केवल 10% की वृद्धि है{{snd}}उम्मीदवारों की संख्या को 11 से गुणा कर देगा, 1000% की वृद्धि। 20 अक्षरों के लिए, उम्मीदवारों की संख्या 20! है, जो लगभग 2.4×10 है<sup>18</sup> या 2.4 [[क्विंटिलियन]]; और खोज में लगभग 10 वर्ष लगेंगे। इस अप्रिय घटना को आमतौर पर दहनशील विस्फोट या आयामीता का अभिशाप कहा जाता है।
ब्रूट-फोर्स पद्धति की मुख्य हानि यह है कि, वास्तविक-विश्व की कई समस्याओं के लिए, प्राकृतिक प्रत्याशियों की संख्या निषेधात्मक रूप से बड़ी है। उदाहरण के लिए, यदि हम ऊपर वर्णित संख्या के विभाजक की सर्च करते हैं, तो परीक्षण किए गए प्रत्याशियों की संख्या दी गई संख्या n होगी। इसलिए यदि n में 16 दशमलव अंक हैं, तो सर्च के लिए कम से कम 10<sup>15</sup> कंप्यूटर निर्देश क्रियान्वित करने की आवश्यकता होगी, जिसमें विशिष्ट व्यक्तिगत कंप्यूटर पर कई दिन लगेंगे। यदि n यादृच्छिक 64-बाइनरी अंकों की प्राकृतिक संख्या है, जिसमें औसतन लगभग 19 दशमलव अंक हैं, तो सर्च में लगभग 10 वर्ष लगेंगे। प्रत्याशियों की संख्या में यह तीव्र वृद्धि, जैसे-जैसे डेटा का आकार बढ़ता है, सभी प्रकार की समस्याओं में होता है। उदाहरण के लिए, यदि हम 10 अक्षरों की विशेष पुनर्व्यवस्था की मांग कर रहे हैं, तो हमारे पास 10! = 3,628,800 प्रत्याशियों पर विचार करने के लिए, जो विशिष्ट पीसी(PC) सेकंड से भी कम समय में उत्पन्न और परीक्षण कर सकता है। चूँकि, एक और पत्र जोड़ना{{snd}}जो डेटा आकार में मात्र 10% की वृद्धि है{{snd}}प्रत्याशियों की संख्या को 11 से गुणा कर, 1000% की वृद्धि कर देगा। 20 अक्षरों के लिए, प्रत्याशियों की संख्या 20! है, जो लगभग 2.4×10<sup>18</sup> या 2.4 [[क्विंटिलियन]] है; और सर्च में लगभग 10 वर्ष लगेंगे। इस अप्रिय घटना को सामान्यतः दहनशील विस्फोट या आयामीता का अभिशाप कहा जाता है।


ऐसे मामले का उदाहरण जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है, शतरंज को हल करने में है। शतरंज कोई [[सुलझा हुआ खेल]] नहीं है। 2005 में, छह पीस या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को और शतरंज के टुकड़े के साथ पूरा करने में दस साल लग गए, इस प्रकार 7-टुकड़ा टेबलबेस पूरा हो गया। शतरंज के समापन में और टुकड़ा जोड़ना (इस प्रकार 8-टुकड़ा टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=लोमोनोसोव एंडगेम टेबलबेस|url=http://chessok.com/?page_id=27966 |website=ChessOK}}</ref>
ऐसी स्थितियों का उदाहरण शतरंज को हल करने में है, जहां संयोजी जटिलता से विलेयता की सीमा हो जाती है। शतरंज कोई [[सुलझा हुआ खेल]] नहीं है। 2005 में, छह भाग या उससे कम वाले सभी शतरंज के खेल को हल किया गया था, जो पूरी तरह से खेले जाने पर प्रत्येक स्थिति का परिणाम दिखाते थे। टेबलबेस को एक और शतरंज के भाग के साथ पूरा करने में दस वर्ष लग गए, इस प्रकार एक 7-भाग टेबलबेस पूरा हो गया। शतरंज के समापन में एक और भाग जोड़ने (इस प्रकार एक 8-भाग टेबलबेस बनाना) को जोड़ा संयोजन जटिलता के कारण अट्रैक्टिव माना जाता है।<ref>{{cite web |title=Is there a freely available online 7 piece Endgame tablebase? |url=https://chess.stackexchange.com/questions/5253/is-there-a-freely-available-online-7-piece-endgame-tablebase |website=Stack Exchange}}</ref><ref>{{cite web |title=लोमोनोसोव एंडगेम टेबलबेस|url=http://chessok.com/?page_id=27966 |website=ChessOK}}</ref>
== ब्रूट-फोर्स खोजों को तेज करना ==
== ब्रूट-फोर्स सर्चों को तीव्र करना ==
ब्रूट-फोर्स एल्गोरिदम को गति देने का तरीका समस्या वर्ग के लिए विशिष्ट [[ अनुमानी |अनुमानी]] ्स का उपयोग करके, खोज स्थान को कम करना है, यानी उम्मीदवार समाधान का सेट। उदाहरण के लिए, आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की [[बिसात]] पर रखने की चुनौती है ताकि कोई भी रानी किसी दूसरे पर हमला न करे। चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में 64 हैं<sup>8</sup> = 281,474,976,710,656 विचार करने की संभावनाएं। हालाँकि, क्योंकि रानियाँ सभी जैसी हैं, और कोई भी दो रानियाँ ही वर्ग पर नहीं रखी जा सकती हैं, उम्मीदवार सभी 64 वर्गों के सेट से 8 वर्गों के संयोजन हैं; जिसका मतलब है कि 64 चुनें 8 = 64!/(56!*8!) = 4,426,165,368 उम्मीदवार समाधान{{snd}}पिछले अनुमान का लगभग 1/60,000। इसके अलावा, ही पंक्ति या ही स्तंभ पर दो रानियों के साथ कोई व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम उम्मीदवारों के सेट को उन व्यवस्थाओं तक सीमित कर सकते हैं।
ब्रूट-फोर्स एल्गोरिदम को गति देने की एक विधि अर्थात प्रत्याशी समाधान का समुच्चय जो कि समस्या वर्ग के लिए विशिष्ट [[ अनुमानी |ह्यूरिस्टिक्स]] उपयोग करके, सर्च-स्थान को कम करना है। उदाहरण हेतु , आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की [[बिसात]] पर रखने की चुनौती है जिससे कोई भी रानी किसी दूसरे पर हमला न कर सके । चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में विचार करने की 64<sup>8</sup> = 281,474,976,710,656 संभावनाएं हैं। चूँकि, क्योंकि रानियाँ सभी एक जैसी हैं, और कोई भी दो रानियाँ एक ही वर्ग पर नहीं रखी जा सकती हैं, प्रत्याशी सभी 64 वर्गों के समुच्चय से 8 वर्गों के समुच्चय को चुनने के सभी संभवित मार्ग हैं; जिसका अर्थ है 64 चयन करें 8 = 64!/(56!*8!) = 4,426,165,368 प्रत्याशी समाधान{{snd}}जो पिछले अनुमान का लगभग 1/60,000 है । इसके अतिरिक्त, एक ही पंक्ति या एक ही स्तंभ पर दो रानियों के साथ कोई व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम प्रत्याशियों के समुच्चय को उन व्यवस्थाओं तक सीमित कर सकते हैं।
   
   
जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अक्सर उम्मीदवार समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को तुच्छ में बदल सकता है।
जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अधिकांशतः प्रत्याशी समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को नगण्य में बदल सकता है।


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


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


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


== क्रिप्टोग्राफी में ==
== कूटलिपि शास्त्र(क्रिप्टोग्राफी) में ==
{{main|Brute-force attack}}
{{main|ब्रूट-फोर्स आक्रमण}}


[[क्रिप्टोग्राफी]] में, क्रूर-बल हमले में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित [[कुंजी (क्रिप्टोग्राफी)]] की जांच करना शामिल है।<ref>Mark Burnett, [http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php "Blocking Brute Force Attacks"] {{Webarchive|url=https://web.archive.org/web/20161203020306/http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php |date=2016-12-03 }}, ''UVA Computer Science'', 2007</ref> यह [[रणनीति]] सैद्धांतिक रूप से किसी भी एन्क्रिप्टेड डेटा के खिलाफ इस्तेमाल की जा सकती है<ref>{{cite book|url=http://www.crypto-textbook.com|page=7|title=Understanding Cryptography: A Textbook for Students and Practitioners|author1=Christof Paar |author2=Jan Pelzl |author3=Bart Preneel |publisher=Springer|year=2010|isbn=3-642-04100-0}}</ref> (एक बार के पैड को छोड़कर) हमलावर द्वारा जो एन्क्रिप्शन प्रणाली में किसी भी कमजोरी का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को आसान बना देगा।
[[क्रिप्टोग्राफी|कूटलिपि शास्त्र]] में, ब्रूट-फोर्स आक्रमण में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित [[कुंजी (क्रिप्टोग्राफी)|कुंजी]] की जांच करना सम्मिलित है।<ref>Mark Burnett, [http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php "Blocking Brute Force Attacks"] {{Webarchive|url=https://web.archive.org/web/20161203020306/http://www.cs.virginia.edu/~csadmin/gen_support/brute_force.php |date=2016-12-03 }}, ''UVA Computer Science'', 2007</ref> यह [[रणनीति]] सैद्धांतिक रूप से किसी भी गोपित डेटा के विरुद्ध उपयोग की जा सकती है<ref>{{cite book|url=http://www.crypto-textbook.com|page=7|title=Understanding Cryptography: A Textbook for Students and Practitioners|author1=Christof Paar |author2=Jan Pelzl |author3=Bart Preneel |publisher=Springer|year=2010|isbn=3-642-04100-0}}</ref> (पैड या गद्दी के अतिरिक्त) आक्रमणकारी द्वारा जो एन्क्रिप्शन अथवा कूटलेखन प्रणाली में किसी भी अशक्तता का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को सरल बना देगा।


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


==संदर्भ==
==संदर्भ==
Line 47: Line 54:
== यह भी देखें ==
== यह भी देखें ==


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


{{Algorithmic paradigms}}
{{Algorithmic paradigms}}


{{DEFAULTSORT:Brute-Force Search}}
{{DEFAULTSORT:Brute-Force Search}}
श्रेणी:खोज एल्गोरिदम


श्रेणी:सर्च एल्गोरिदम


[[Category: Machine Translated Page]]
[[Category:Articles with hatnote templates targeting a nonexistent page|Brute-Force Search]]
[[Category:Created On 02/03/2023]]
[[Category:CS1 English-language sources (en)]]
[[Category:Collapse templates|Brute-Force Search]]
[[Category:Created On 02/03/2023|Brute-Force Search]]
[[Category:Lua-based templates|Brute-Force Search]]
[[Category:Machine Translated Page|Brute-Force Search]]
[[Category:Navigational boxes| ]]
[[Category:Navigational boxes without horizontal lists|Brute-Force Search]]
[[Category:Pages with script errors|Brute-Force Search]]
[[Category:Pages with syntax highlighting errors]]
[[Category:Short description with empty Wikidata description|Brute-Force Search]]
[[Category:Sidebars with styles needing conversion|Brute-Force Search]]
[[Category:Template documentation pages|Documentation/doc]]
[[Category:Templates Vigyan Ready|Brute-Force Search]]
[[Category:Templates generating microformats|Brute-Force Search]]
[[Category:Templates that add a tracking category|Brute-Force Search]]
[[Category:Templates that are not mobile friendly|Brute-Force Search]]
[[Category:Templates that generate short descriptions|Brute-Force Search]]
[[Category:Templates using TemplateData|Brute-Force Search]]
[[Category:Webarchive template wayback links]]
[[Category:Wikipedia metatemplates|Brute-Force Search]]

Latest revision as of 17:00, 15 March 2023

This article is about कंप्यूटर विज्ञान में समस्या समाधान तकनीक. For अन्य विषयों में इसी प्रकार नामित विधियाँ, see ब्रूट-फोर्स (असंबद्धता).

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

एक ब्रूट-फोर्स एल्गोरिथ्म जो प्राकृतिक संख्या n के विभाजकों को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए ब्रूट-फोर्स दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 भागों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक(रानी) भाग किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।[1]

यद्यपि ब्रूट-फोर्स सर्च सॉफ़्टवेयर को प्रयुक्त करना आसान है और यदि यह उपस्थित है तो सदैव एक समाधान मिलेगा, कार्यान्वयन निवेश उम्मीदवार समाधानों की संख्या के अनुपात में होती है – जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§ संयुक्त विस्फोट)।[2] इसलिए, ब्रूट-फोर्स सर्च का उपयोग सामान्यतः तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमानिकीय होते हैं, जिनका उपयोग प्रत्याशी के समाधान के समुच्चय को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।

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

ब्रूट-फोर्स सर्च को कार्यान्वित करना

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

क्रम में वर्तमान के बाद P के लिए प्रत्याशी c।

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

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

c ← first(P)
while c ≠ Λ do
    if valid(P,c) then
        output(P, c)
    c ← next(P, c)
end while

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

संयोजक विस्फोट

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

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

ब्रूट-फोर्स सर्चों को तीव्र करना

ब्रूट-फोर्स एल्गोरिदम को गति देने की एक विधि अर्थात प्रत्याशी समाधान का समुच्चय जो कि समस्या वर्ग के लिए विशिष्ट ह्यूरिस्टिक्स उपयोग करके, सर्च-स्थान को कम करना है। उदाहरण हेतु , आठ रानियों की पहेली में आठ रानियों को मानक शतरंज की बिसात पर रखने की चुनौती है जिससे कोई भी रानी किसी दूसरे पर हमला न कर सके । चूंकि प्रत्येक रानी को 64 वर्गों में से किसी में भी रखा जा सकता है, सिद्धांत रूप में विचार करने की 648 = 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 तक के सूचकांक हैं, और यदि P(c)= '1 ' हो तो प्रत्याशी c मान्य है । अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान प्रायिकता है, किन्तु उसके बाद प्रत्येक बिट 90% प्रायिकता के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो t का अपेक्षित मूल्य 2 से थोड़ा ही अधिक होगा। सामान्य रूप से अधिक, सर्च-स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक प्रायिकता है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में "क्लस्टर" या "समूहीकृत" किए जाने की प्रायिकता है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की प्रायिकता है, तो निश्चित रूप से इसका विलोम होता है।

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

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

कूटलिपि शास्त्र(क्रिप्टोग्राफी) में

Main article: ब्रूट-फोर्स आक्रमण

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

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

संदर्भ

  1. ↑ "ब्रूट फ़ोर्स एल्गोरिदम समझाया गया". freeCodeCamp.org (in English). 2020-01-06. Retrieved 2021-04-11.
  2. ↑ "क्रूर बल खोज की जटिलता". coursera. Retrieved 14 June 2018.
  3. ↑ "Is there a freely available online 7 piece Endgame tablebase?". Stack Exchange.
  4. ↑ "लोमोनोसोव एंडगेम टेबलबेस". ChessOK.
  5. ↑ Mark Burnett, "Blocking Brute Force Attacks" Archived 2016-12-03 at the Wayback Machine, UVA Computer Science, 2007
  6. ↑ Christof Paar; Jan Pelzl; Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. p. 7. ISBN 3-642-04100-0.

यह भी देखें



श्रेणी:सर्च एल्गोरिदम

Retrieved from ‘https://www.vigyanwiki.in/index.php?title=ब्रूट-फोर्स_सर्च&oldid=108923’