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

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

رده	الگوریتم جستجو

جستجوی بروت-فورس یا جستجوی غیرهوشمندانه (به انگلیسی: Brute-force search) یا جستجوی جامع (فراگیر) (به انگیسی: exhaustive search)، که همچنین در علوم کامپیوتر به نام جستجوی تولید و تِست (به انگلیسی: generate and test) شناخته شده، روشی بدیهی در عین حال بسیار کلی برای حل مسئله می‌باشد. این روش که شامل شمارش نظام مند تمام نامزدهای ممکن برای حل و چک کردن اینکه آیا هر یک از نامزدها قادر به برقراری شرط مسئله است. به عنوان مثال، یک الگوریتم Brute-force برای پیدا کردن مقسوم علیه‌های یک عدد طبیعی N، شامل شمردن تمام اعداد صحیح از ۱ تا ریشهٔ دوم از n است، و بررسی اینکه آیا n به هر یک از آن‌ها تقسیم پذیر است یا خیر.

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

به عنوان مثال، در برنامه‌های حساس که در آن هر گونه خطا در الگوریتم می‌تواند عواقب بسیار جدی داشته باشد، یا در هنگام استفاده از رایانه برای اثبات یک قضیه ریاضی این روش به کار برده می‌شود. جستجو به روش Brute-force به عنوان روش «پایه» در هنگام تعیین معیار الگوریتم‌های دیگر یا metaheuristics مفید می‌باشد. در واقع، جستجو به روش Brute-force را می‌توان ساده‌ترین metaheuristic نام نهاد. با این وجود نباید این روش را با روش پسگرد اشتباه گرفت. در روش عقبگرد، مجموعه بزرگی از راه حل‌ها را می‌توان بدون شمارش حذف کرد. روش Brute-force برای پیدا کردن یک آیتم در یک جدول جستجوی خطی نامیده می‌شود.

پیاده‌سازی جستجوی Brute-force

الگوریتم پایه

به منظور استفاده از روش 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 $\gets$ first(P)
while c $\neq$ Λ do if valid(P,c) then output(P, c) c $\gets$ next(P,c)

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

void BF(char *x, int m, char *y, int n)
{
  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 شامل امتحان کردن تمامی کلیدهای ممکن تا وقتی که کلید صحیح پیدا شود. این روش همیشه، به وسیله کسی که نتواند از کاستی‌های سامانه رمزنگاری شده‌استفاده کند، قابل بکارگیری می‌باشد. طول کلید تعیین کنندهٔ قابل اجرا بودن روش Brute-force برای رمزگشایی می‌باشد. افزایش طول کلید می‌تواند استفاده از این روش را به صورت نمایی سختتر کند. کلیدهایی که به صورت دلبخواه بی معنا یا گمراه‌کننده انتخاب شوند، می‌توانند کاربرد این روش را به شدت دشوارتر کنند. یکی از معیارهای قوت یک رمز، طول زمان رمزگشایی با استفاده از روش Brute-force است.

منابع

^ Christof Paar, Jan Pelzl, Bart Preneel (2010). Understanding Cryptography: A Textbook for Students and Practitioners . Springer. p. 7. ISBN 3-642-04100-0.

http://www-igm.univ-mlv.fr/~lecroq/string/node3.html

http://en.wikipedia.org/wiki/Brute-force_search

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

• حمله جستجوی فراگیر
• نماد O بزرگ