جستجوی بروت-فورس

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

(first (P: ایجاد اولین نامزد برای حل P.

(next (P, c: ایجاد نامزد بعدی برای حل P پس از نامزد فعلی c.

(valid (P, c: بررسی مقبولیت نامزد c به عنوان یک راه حل برای P.

(output (P, c: استفاده از جواب c در برنامه P.

مرحله next می‌بایست زمانی که نامزد دیگری برای حل P وجود ندارد، را تشخیص دهد. یک راه مناسب برای انجام این کار بازگرداندن «نامزد پوچ» به عنوان نامزد بعدی می‌باشد، برخی از دادهٔ Λ به صورت معمول برای که تمایز از نامزدهای واقعی استفاده می‌شود. به همین ترتیب در صورتی که هیچ نامزدی برای حل P موجود نباشد مرحله first نیز باید دادهٔ Λ برگرداند. در این صورت روش brute-force توسط الگوریتم زیر بیان می‌شود:

c ${\displaystyle \gets }$
 first(P)
while c ${\displaystyle \neq }$
 Λ do if valid(P,c) then output(P, c) c ${\displaystyle \gets }$
 next(P,c)

پیاده‌سازی الگوریتم به زبان c:

 int i, j;
 /* Searching */
 for (j = 0; j <= n - m; ++j) {
 for (i = 0; i <m && x[i] == y[i + j]; ++i);
 if (i>= m)
 OUTPUT(j);

نقطه ضعف اصلی استفاده از روش Brute-force در بسیاری از مسائل عملی این است که تعداد نامزدهای حل مسئله بسیار زیاد است. به عنوان مثال، تعداد نامزدهای حل مسئله برای یافتن مقسوم علیه‌های عدد n, n می‌باشد. بدین ترتیب برای یافتن مقسوم علیه‌های یک عدد ۱۶ رقمی، نیاز به اجرای حداقل ۱۰ به توان ۱۵ جستجو می‌باشد که برای یک دستگاه رایانه معمولی چند روز طول خواهد کشید. اگر n یک عدد طبیعی ۶۴ بیتی ۱۹ رقمی تصادفی باشد به‌طور متوسط، جستجو حدود ۱۰ سال طول می‌کشد. این رشد سریع در تعداد نامزدها، با افزایش داده‌ها در تمام مسائل اتفاق می‌افتد. به عنوان مثال، جستجوی یک چیدمان خاص از ۱۰ حرف، ۱۰ = ۳٬۶۲۸٬۸۰۰ نامزد خواهد داشت، که یک PC ی معمولی می‌تواند در کمتر از یک ثانیه ایجاد و تست نماید. با این حال، با اضافه کردن یک حرف (که تنها ۱۰ درصد افزایش در حجم داده هاست) تعداد نامزدها را ۱۱ برابر می‌کند (تعداد نامزدها %۱۰۰۰ افزایش می‌یابد). تعداد نامزدها برای ۲۰ حرف، ۲۰ است، یعنی حدود ۲٫۴ × ۱۰۱۸. این جستجو حدود ۱۰٬۰۰۰ سال طول خواهد کشید. این پدیده ناخوشایند به نام انفجار ترکیبی معروف است.

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

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

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

هم چنین ببینید:

این الگوریتم به زبان جاوا