جستجوی بروت-فورس: تفاوت میان نسخه‌ها

به منظور استفاده از روش brute-force در یک کلاس خاص از مسائل، باید چهار زیر برنامه first, next, valid و output پیاده‌سازی شود. هر یک از این روشها،روش‌ها، داده P از یک مسئله را به عنوان یک پارامتر در نظر گرفته و مراحل زیر را انجام می‌دهد:

از جمله راه‌های سرعت بخشیدن به الگوریتم brute-force استفاده از راه‌های ابتکاری مخصوص برای هر مسئله به منظور کاهش فضای جستجو یا به عبارتی کاهش تعداد نامزدهای قابل قبول می‌باشد. به عنوان مثال، مسئله معروف ۸ ملکه را در نظر بگیرید، در این مسئله ۸ ملکه در [[صفحه شطرنج]] طوری باید قرار بگیرند که هیچ‌یک قادر به حمله به دیگری نباشد. از آنجا که هر یک از ملکه‌ها را می‌توان در هر یک از ۶۴ مربع قرار داد، در اصل ۲۸۱٬۴۷۴٬۹۷۶٬۷۱۰٬۶۵۶ =۶۴۸ (بیش از ۲۸۱ تریلیون) حالت امکان‌پذیر وجود دارد. با این حال، با در نظر گرفتن این موضوع که همه ملکه‌ها یکسان هستند، و این که هیچ دو ملکه‌ای را نمی‌توان در یک خانه قرار داد، نتیجه می‌گیریم که نامزدها تمام راه‌های ممکن از انتخاب مجموعه‌ای از ۸ مربع از مجموعه‌ای از ۶۴ مربع است که به معنی انتخاب ۸ از ۶۴ می‌باشد (۶۴!/۵۶!۸! نامزد حل) در حدود ۱/۶۰، ۰۰۰ برآورد قبلی. همچنین، به سادگی می‌توان تشخیص داد که هیچ آرایشی با دو ملکه در یک سطر یا ستون نمی‌تواند یک راه حل باشد؛ بنابراین، می‌توان گفت که هر یک از ملکه‌ها در یک ردیف مثلاً ملکه ۱ در ردیف ۱، ملکه ۲ در ردیف ۲، و … به گونه‌ای که هیچ‌یک در یک سطر نیز نباشند باید قرار بگیرند. در نتیجه تعداد نامزدها به ۸! تقلیل می‌یابد. همان گونه که این مثال نشان می‌دهد، کمی تجزیه و تحلیل اغلب منجر به کاهش چشمگیر در تعداد نامزدها می‌شود، و ممکن است یک مسئله غیرقابل حل را به مسئله‌ای پیش پا افتاده تبدیل کند. این مثال همچنین نشان می‌دهد که روش شمارش نامزدها (اول و بعدی) برای مجموعهٔ محدود از نامزدها ممکن است به راحتی یا حتی ساده‌تر از مجموعه اصلی باشد. در برخی موارد، تجزیه و تحلیل ممکن است نامزدها را محدود به تمامی جواب‌های مسئله نماید. به عنوان مثال، مسئله پیدا کردن تمام اعداد صحیح بین ۱ و ۱٬۰۰۰٬۰۰۰ که به‌طور مساوی بر ۴۱۷ تقسیم پذیر باشند را در نظر بگیرید. یک الگوریتم brute-force ابتداییممکن است تمام اعداد داخل محدوده را برای [[تقسیم پذیری]] امتحان کند. در حالیکه این مسئله را می‌توان بصورتبه صورت بسیار مؤثرتر با شروع از ۴۱۷ و اضافه کردن ۴۱۷ به عدد قبلی تا وقتی که عدد حاصل بیش از ۱٬۰۰۰٬۰۰۰ شود. بدین ترتیب تعداد نامزدها به ۲۳۹۸ (۱۰۰۰۰۰/۴۱۷) کاهش یافته و هیچ امتحانی نیاز نیست.

روش‌های جستجوی متعددی برای یافتن راه حل هنگامی که اطلاعات محدودی از جواب مسئله در دسترس است وجود دارد. همیشه راه‌های ابتکاری خاص هر مسئله می‌تواند کار را ساده‌تر نماید. برای مثال تعیین [[بیشینه و کمینه]] در مراحل ابتدایی حل یک مسئله می‌تواند بسیار مفید باشد. در بعضی موارد همانند تجزیه جملات، روش‌هایی مثل تجزیه نمودار ممکن است درجه سختی مسئله را از حد نمایی به سختی چندجمله‌ای تقلیل دهد. در بعضی موارد دیگر، ساده‌تر کردن مسئله می‌تواند جستجو را بسیار راحت‌تر کند. برای مثال در شطرنج کامپیوتری، برای انتخاب هر حرکت، بجای اینکه تمام گزینه‌ها تا انتهای بازی در نظر گرفته شود، تعداد محدودی از بیشینه و کمینه‌ها برای تعداد مشخصی از حرکت‌ها آینده بصورتبه صورت استاتیک بررسی می‌شود.

طول کلید تعیین کنندهٔ قابل اجرا بودن روش brute-force برای رمزگشایی می‌باشد. افزایش طول کلید می‌تواند استفاده از این روش را به صورت نمایی سختتر کند. کلیدهایی که بصورتبه صورت دلبخواه بی معنا یا گمراه کنندهگمراه‌کننده انتخاب شوند، می‌توانند کاربرد این روش را به شدت دشوارتر کنند. یکی از معیارهای قوت یک رمز، طول زمان رمزگشایی با استفاده از روش brute-force است.