ब्रूट-फोर्स सर्च: Difference between revisions
No edit summary |
No edit summary |
||
| 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 को विभाजित करता है। आठ रानियों की पहेली के लिए | एक ब्रूट-फोर्स एल्गोरिथ्म जो [[प्राकृतिक संख्या]] ''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}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§ संयुक्त विस्फोट)।<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}}जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§ संयुक्त विस्फोट)।<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}}रेखीय सर्च कहा जाता है। | ||
== ब्रूट-फोर्स सर्च को कार्यान्वित करना == | == ब्रूट-फोर्स सर्च को कार्यान्वित करना == | ||
| Line 15: | Line 15: | ||
# वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है। | # वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है। | ||
# आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें। | # आउटपुट (P, c): आवेदन के लिए उपयुक्त के रूप में P के समाधान c का उपयोग करें। | ||
अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान एक c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने की सुविधाजनक विधि "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट- | अगली प्रक्रिया को यह भी बताना होगा कि वर्तमान एक c के बाद P के लिए कोई और प्रत्याशी नहीं हैं। ऐसा करने की सुविधाजनक विधि "अशक्त प्रत्याशी" को वापस करना है, कुछ पारंपरिक डेटा मान Λ जो कि किसी भी वास्तविक प्रत्याशी से अलग है। इसी प्रकार पहली प्रक्रिया को Λ वापस करना चाहिए यदि उदाहरण P के लिए कोई प्रत्याशी नहीं हैं। ब्रूट-फोर्स विधि तब एल्गोरिदम द्वारा व्यक्त की जाती है:<syntaxhighlight> | ||
c ← first(P) | c ← first(P) | ||
while c ≠ Λ do | while c ≠ Λ do | ||
| Line 24: | Line 24: | ||
</syntaxhighlight> | </syntaxhighlight> | ||
उदाहरण के लिए, जब पूर्णांक 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 में 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 है । इसके अतिरिक्त, एक ही पंक्ति या एक ही स्तंभ पर दो रानियों के साथ कोई व्यवस्था समाधान नहीं हो सकती है। इसलिए, हम प्रत्याशियों के समुच्चय को उन व्यवस्थाओं तक सीमित कर सकते हैं। | ||
जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अधिकांशतः प्रत्याशी समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को नगण्य में बदल सकता है। | जैसा कि इस उदाहरण से पता चलता है, थोड़ा सा विश्लेषण अधिकांशतः प्रत्याशी समाधानों की संख्या में नाटकीय कमी लाएगा, और जटिल समस्या को नगण्य में बदल सकता है। | ||
कुछ स्थितियों में, विश्लेषण प्रत्याशियों को सभी वैध समाधानों के समुच्चय तक कम कर सकता है; अर्थात्, यह एल्गोरिदम उत्पन्न कर सकता है जो परीक्षणों के साथ समय नष्ट किए बिना और अमान्य प्रत्याशियों की पीढ़ी के बिना सभी वांछित समाधानों की सीधे गणना करता है (या उपयुक्त समाधान प्राप्त करता है)। उदाहरण के लिए, समस्या हेतु "1 और 1,000,000 के बीच के सभी पूर्णांकों को | कुछ स्थितियों में, विश्लेषण प्रत्याशियों को सभी वैध समाधानों के समुच्चय तक कम कर सकता है; अर्थात्, यह एल्गोरिदम उत्पन्न कर सकता है जो परीक्षणों के साथ समय नष्ट किए बिना और अमान्य प्रत्याशियों की पीढ़ी के बिना सभी वांछित समाधानों की सीधे गणना करता है (या उपयुक्त समाधान प्राप्त करता है)। उदाहरण के लिए, समस्या हेतु "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 तक के सूचकांक हैं, और यदि P(c)= '1 ' हो तो प्रत्याशी c मान्य है । अब, मान लीजिए कि P का पहला बिट '0' या '1' होने की समान प्रायिकता है, किन्तु उसके बाद प्रत्येक बिट 90% प्रायिकता के साथ पिछले के बराबर है। यदि प्रत्याशियों को बढ़ते क्रम में 1 से 1000 तक गिना जाता है, तो सफलता से पहले जांचे गए प्रत्याशियों की संख्या औसतन लगभग 6 होगी। दूसरी ओर, यदि प्रत्याशियों की गणना 1,11,21,31...991,2,12,22,32 आदि के क्रम में की जाती है, तो ''t'' का अपेक्षित मूल्य 2 से थोड़ा ही अधिक होगा। सामान्य रूप से अधिक, सर्च-स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक प्रायिकता है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में "क्लस्टर" या "समूहीकृत" किए जाने की प्रायिकता है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की प्रायिकता है, तो निश्चित रूप से इसका विलोम होता है। | ||
== ब्रूट-फोर्स सर्च के विकल्प == | == ब्रूट-फोर्स सर्च के विकल्प == | ||
कई अन्य | कई अन्य सर्च विधियाँ , या मेटाह्यूरिस्टिक्स हैं , जिन्हें समाधान के विषय में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए रचित किया गया है। सर्च के कुछ हिस्सों का प्रारंभिक कटऑफ़ बनाने के लिए ह्यूरिस्टिक्स का भी उपयोग किया जा सकता है। इसका उदाहरण गेम-ट्रीज की सर्च के लिए [[अल्पमहिष्ठ|अल्पमहिष्ठ सिद्धांत]] है, जो सर्च के प्रारंभिक चरण में कई सबट्रीज को निष्काशित कर देता है। कुछ क्षेत्रों में, जैसे भाषा विश्लेषण , [[ चार्ट विश्लेषण |चार्ट विश्लेषण]] जैसी विधियां घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का लाभ उठा सकती हैं। कई स्थितियों में, जैसे कि [[बाधा संतुष्टि समस्या|बाधा संतुष्टि समस्याओं]] में, [[बाधा प्रचार]] के माध्यम से सर्च-स्थान को नाटकीय रूप से कम कर सकते हैं, जो [[बाधा प्रोग्रामिंग]] भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए सर्च-स्थान को भी कम किया जा सकता है। उदाहरण के लिए, [[कंप्यूटर शतरंज]] में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम ट्रीज की गणना करने के अतिरिक्त , न्यूनतम प्रायिकताओं के अधिक सीमित ट्रीज की गणना की जाती है, जिसमें ट्रीज को निश्चित संख्या में चालों में काट दिया जाता है, और शेष [[मूल्यांकन समारोह|मूल्यांकन फंक्शन]] द्वारा ट्रीज का अनुमान लगाया जा रहा है। | ||
== कूटलिपि शास्त्र(क्रिप्टोग्राफी) में == | == कूटलिपि शास्त्र(क्रिप्टोग्राफी) में == | ||
{{main| | {{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 61: | Line 61: | ||
{{DEFAULTSORT:Brute-Force Search}} | {{DEFAULTSORT:Brute-Force Search}} | ||
श्रेणी: | |||
श्रेणी:सर्च एल्गोरिदम | |||
[[Category: Machine Translated Page]] | [[Category: Machine Translated Page]] | ||
[[Category:Created On 02/03/2023]] | [[Category:Created On 02/03/2023]] | ||
Revision as of 09:41, 11 March 2023
कंप्यूटर विज्ञान में, ब्रूट-फोर्स सर्च या विस्तृत सर्च, जिसे उत्पन्न(जेनरेट) और परीक्षण के रूप में भी जाना जाता है, बहुत ही सामान्य समस्या-समाधान विधि और एल्गोरिथम प्रतिमान है जिसमें समाधान के लिए सभी संभावित प्रत्याशियों की व्यवस्थित रूप से गणना करना और यह जांचना सम्मिलित है कि प्रत्येक प्रत्याशी समस्या के कथन को संतुष्ट करता है या नहीं करता है।
एक ब्रूट-फोर्स एल्गोरिथ्म जो प्राकृतिक संख्या n के विभाजकों को खोजता है, यह 1 से n तक सभी पूर्णांकों की गणना करेगा, और जाँच करेगा कि कि क्या उनमें से प्रत्येक बिना शेष के n को विभाजित करता है। आठ रानियों की पहेली के लिए ब्रूट-फोर्स दृष्टिकोण 64-वर्ग शतरंज की बिसात पर 8 भागों की सभी संभावित व्यवस्थाओं की जांच करेगा और प्रत्येक व्यवस्था के लिए यह जांच करेगा कि प्रत्येक(रानी) भाग किसी अन्य पर हमला कर सकता है या नहीं कर सकता है ।[1]
यद्यपि ब्रूट-फोर्स सर्च सॉफ़्टवेयर को प्रयुक्त करना आसान है और यदि यह उपस्थित है तो सदैव एक समाधान मिलेगा, कार्यान्वयन निवेश उम्मीदवार समाधानों की संख्या के अनुपात में होती है – जो कई व्यावहारिक समस्याओं में समस्या के आकार के बढ़ने पर बहुत तीव्र गति से बढ़ने लगती है (§ संयुक्त विस्फोट)।[2] इसलिए, ब्रूट-फोर्स सर्च का उपयोग सामान्यतः तब किया जाता है जब समस्या का आकार सीमित होता है, या जब समस्या-विशिष्ट अनुमानिकीय होते हैं, जिनका उपयोग प्रत्याशी के समाधान के समुच्चय को प्रबंधनीय आकार में कम करने के लिए किया जा सकता है। विधि का उपयोग तब भी किया जाता है जब कार्यान्वयन की सरलता गति से अधिक महत्वपूर्ण होती है।
यह एकव प्रकार का स्थिति है, उदाहरण के लिए, महत्वपूर्ण अनुप्रयोगों में जहां कलन विधि में किसी भी त्रुटि के बहुत गंभीर परिणाम होंगे या जब गणितीय प्रमेय सिद्ध हो रहे हों। अन्य एल्गोरिदम या मेटाह्यूरिस्टिक्स को बेंच मार्किंग(मानकीकरण) करते समय ब्रूट-फोर्स सर्च आधारभूत विधि के रूप में भी उपयोगी होती है। दरअसल, ब्रूट-फोर्स सर्च को सबसे सरल मेटाह्यूरिस्टिक के रूप में देखा जा सकता है। ब्रूट फ़ोर्स सर्च को बैक ट्रैकिंग के साथ भ्रमित नहीं होना चाहिए, जहां समाधानों के बड़े समुच्चयों को स्पष्ट रूप से गणना किए बिना त्याग दिया जा सकता है (जैसा कि ऊपर आठ रानियों की समस्या के पाठ्यपुस्तक कंप्यूटर समाधान में है)। किसी सारिणी में किसी वस्तु को खोजने के लिए ब्रूट-फोर्स विधि – अर्थात्, बाद की सभी प्रविष्टियों की जाँच करें, क्रमिक रूप से – रेखीय सर्च कहा जाता है।
ब्रूट-फोर्स सर्च को कार्यान्वित करना
बेसिक एल्गोरिथम
क्रम में वर्तमान के बाद P के लिए प्रत्याशी c।
- वैध (P, c): जांचें कि प्रत्याशी c P के लिए समाधान है या नहीं है।
- आउटपुट (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 से थोड़ा ही अधिक होगा। सामान्य रूप से अधिक, सर्च-स्थान को इस तरह से गिना जाना चाहिए कि अगले प्रत्याशी के वैध होने की सबसे अधिक प्रायिकता है, यह देखते हुए कि पिछले परीक्षण नहीं थे। इसलिए यदि वैध समाधानों को किसी अर्थ में "क्लस्टर" या "समूहीकृत" किए जाने की प्रायिकता है, तो प्रत्येक नए प्रत्याशी को उसी अर्थ में पिछले वाले से जितना संभव हो उतना दूर होना चाहिए। निश्चित रूप से, यदि समाधान संयोग से अपेक्षा से अधिक समान रूप से फैले होने की प्रायिकता है, तो निश्चित रूप से इसका विलोम होता है।
ब्रूट-फोर्स सर्च के विकल्प
कई अन्य सर्च विधियाँ , या मेटाह्यूरिस्टिक्स हैं , जिन्हें समाधान के विषय में विभिन्न प्रकार के आंशिक ज्ञान का लाभ उठाने के लिए रचित किया गया है। सर्च के कुछ हिस्सों का प्रारंभिक कटऑफ़ बनाने के लिए ह्यूरिस्टिक्स का भी उपयोग किया जा सकता है। इसका उदाहरण गेम-ट्रीज की सर्च के लिए अल्पमहिष्ठ सिद्धांत है, जो सर्च के प्रारंभिक चरण में कई सबट्रीज को निष्काशित कर देता है। कुछ क्षेत्रों में, जैसे भाषा विश्लेषण , चार्ट विश्लेषण जैसी विधियां घातीय जटिलता समस्या को बहुपद जटिलता समस्या में कम करने के लिए समस्या में बाधाओं का लाभ उठा सकती हैं। कई स्थितियों में, जैसे कि बाधा संतुष्टि समस्याओं में, बाधा प्रचार के माध्यम से सर्च-स्थान को नाटकीय रूप से कम कर सकते हैं, जो बाधा प्रोग्रामिंग भाषाओं में कुशलतापूर्वक कार्यान्वित किया जाता है। पूरी समस्या को सरलीकृत संस्करण के साथ बदलकर समस्याओं के लिए सर्च-स्थान को भी कम किया जा सकता है। उदाहरण के लिए, कंप्यूटर शतरंज में, खेल के शेष भाग के लिए सभी संभावित चालों के पूर्ण न्यूनतम ट्रीज की गणना करने के अतिरिक्त , न्यूनतम प्रायिकताओं के अधिक सीमित ट्रीज की गणना की जाती है, जिसमें ट्रीज को निश्चित संख्या में चालों में काट दिया जाता है, और शेष मूल्यांकन फंक्शन द्वारा ट्रीज का अनुमान लगाया जा रहा है।
कूटलिपि शास्त्र(क्रिप्टोग्राफी) में
कूटलिपि शास्त्र में, ब्रूट-फोर्स आक्रमण में सही कुंजी मिलने तक व्यवस्थित रूप से सभी संभावित कुंजी की जांच करना सम्मिलित है।[5] यह रणनीति सैद्धांतिक रूप से किसी भी गोपित डेटा के विरुद्ध उपयोग की जा सकती है[6] (पैड या गद्दी के अतिरिक्त) आक्रमणकारी द्वारा जो एन्क्रिप्शन अथवा कूटलेखन प्रणाली में किसी भी अशक्तता का लाभ उठाने में असमर्थ है जो अन्यथा उसके कार्य को सरल बना देगा।
एन्क्रिप्शन में उपयोग की जाने वाली कुंजी लंबाई ब्रूट-फोर्स के आक्रमण को करने की व्यावहारिक व्यवहार्यता को निर्धारित करती है, जिसमें छोटी कुंजियों की तुलना में लंबी कुंजियों को भंग करना अधिक कठिन होता है। ब्रूट-फोर्स के आक्रमणों को सांकेतिक शब्दों में परिवर्तित किए जाने वाले डेटा को बाधित करके कम प्रभावी बनाया जा सकता है, ऐसा कुछ जो किसी आक्रमणकारी के लिए यह पहचानना अधिक कठिन बना देता है कि उसने संहिता को कब भंग किया है। एन्क्रिप्शन प्रणाली की शक्ति के उपायों में से यह है कि सैद्धांतिक रूप से आक्रमणकारी को इसके विरुद्ध सफल ब्रूट-फोर्स आक्रमण करने में कितना समय लगेगा।
संदर्भ
- ↑ "ब्रूट फ़ोर्स एल्गोरिदम समझाया गया". freeCodeCamp.org (in English). 2020-01-06. Retrieved 2021-04-11.
- ↑ "क्रूर बल खोज की जटिलता". coursera. Retrieved 14 June 2018.
- ↑ "Is there a freely available online 7 piece Endgame tablebase?". Stack Exchange.
- ↑ "लोमोनोसोव एंडगेम टेबलबेस". ChessOK.
- ↑ Mark Burnett, "Blocking Brute Force Attacks" Archived 2016-12-03 at the Wayback Machine, UVA Computer Science, 2007
- ↑ Christof Paar; Jan Pelzl; Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners. Springer. p. 7. ISBN 3-642-04100-0.
यह भी देखें
- सुडोकू पहेलियों को हल करने के लिए ब्रूट-फोर्स एल्गोरिदम।
- ब्रूट-फोर्स का आक्रमण
- बिग ओ-अंकन
श्रेणी:सर्च एल्गोरिदम
