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

| تصویر =

| زیرنویس تصویر =

| داده‌ها =

| زمان بدترین =

| زمان بهترین =

| زمان متوسط =

| پیچیدگی فضایی =

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

جستجو به روش 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 توسط الگوریتم زیر بیان می‌شود:

'''while''' ''c'' <math>\neq</math> Λ ''do''' ''if''' ''valid''(''P'',''c'') '''then''' ''output''(''P'', ''c'') ''c'' <math>\gets</math> ''next''(''P'',''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 می‌باشد. بدین ترتیب برای یافتن مقسوم علیه‌های یک عدد 16۱۶ رقمی، نیاز به اجرای حداقل 1015۱۰۱۵ جستجو می‌باشد که برای یک دستگاه رایانه معمولی چند روز طول خواهد کشید. اگر n یک عدد طبیعی 64۶۴ بیتی 19۱۹ رقمی تصادفی باشد به طور متوسط، جستجو حدود 10۱۰ سال طول می کشدمی‌کشد. این رشد سریع در تعداد نامزدها، با افزایش [[داده هاداده‌ها]] در تمام مسائل اتفاق می‌افتد. به عنوان مثال، جستجوی یک چیدمان خاص از 10۱۰ حرف، !10حرف،۱۰ = 3،628،800۳٬۶۲۸٬۸۰۰ نامزد خواهد داشت، که یک PC ی معمولی می‌تواند در کمتر از یک ثانیه ایجاد و تست نماید. با این حال، با اضافه کردن یک حرف (که تنها 10۱۰ درصد افزایش در حجم داده هاست) تعداد نامزدها را 11۱۱ برابر می‌کند (تعداد نامزدها %1000۱۰۰۰ افزایش می‌یابد). تعداد نامزدها برای 20۲۰ حرف،حرف،۲۰ !20است، است،یعنییعنی حدود 2.4۲٫۴ × 1018۱۰۱۸. این جستجو حدود 10،000۱۰٬۰۰۰ سال طول خواهد کشید. این پدیده ناخوشایند به نام انفجار ترکیبی معروف است.

از جمله راه‌های سرعت بخشیدن به الگوریتم brute-force استفاده از راه‌های ابتکاری مخصوص برای هر مسئله به منظور کاهش فضای جستجو و یا به عبارتی کاهش تعداد نامزدهای قابل قبول می‌باشد. به عنوان مثال، مسئله معروف 8۸ ملکه را در نظر بگیرید، در این مسئله 8۸ ملکه در [[صفحه شطرنج]] طوری باید قرار بگیرند که هیچ یکهیچ‌یک قادر به حمله به دیگری نباشد. از آنجا که هر یک از ملکه‌ها را می توانمی‌توان در هر یک از 64۶۴ مربع قرار داد، در اصل 281،474،976،710،656۲۸۱٬۴۷۴٬۹۷۶٬۷۱۰٬۶۵۶ =648۶۴۸ (بیش از 281۲۸۱ تریلیون) حالت امکان‌پذیر وجود دارد. با این حال، با در نظر گرفتن این موضوع که همه ملکه‌ها یکسان هستند، و این که هیچ دو ملکه ایملکه‌ای را نمی تواننمی‌توان در یک خانه قرار داد، نتیجه می‌گیریم که نامزدها تمام راه‌های ممکن از انتخاب مجموعه ایمجموعه‌ای از 8۸ مربع از مجموعه ایمجموعه‌ای از 64۶۴ مربع است که به معنی انتخاب 8۸ از 64۶۴ می‌باشد (64۶۴!/56۵۶!8۸! نامزد حل) در حدود 1۱/60،۶۰، 000۰۰۰ برآورد قبلی. همچنین، به سادگی می توانمی‌توان تشخیص داد که هیچ آرایشی با دو ملکه در یک سطر یا ستون نمی‌تواند یک راه حل باشد.باشد؛ بنابراین، می توانمی‌توان گفت که هر یک از ملکه‌ها در یک ردیف مثلاً ملکه 1۱ در ردیف 1،۱، ملکه 2۲ در ردیف 2،۲، و ...… به گونه ایگونه‌ای که هیچ یکهیچ‌یک در یک سطر نیز نباشند باید قرار بگیرند. در نتیجه تعداد نامزدها به 8۸! تقلیل می‌یابد. همان گونه که این مثال نشان می‌دهد، کمی تجزیه و تحلیل اغلب منجر به کاهش چشمگیر در تعداد نامزدها می‌شود، و ممکن است یک مسئله غیر‌قابلغیرقابل حل را به مسئله ایمسئله‌ای پیش پا افتاده تبدیل کند. این مثال همچنین نشان می‌دهد که روش شمارش نامزدها (اول و بعدی) برای مجموعه یمجموعهٔ محدود از نامزدها ممکن است به راحتی و یا حتی ساده‌تر از مجموعه اصلی باشد. در برخی موارد، تجزیه و تحلیل ممکن است نامزدها را محدود به تمامی جواب‌های مسئله نماید. به عنوان مثال، مسئله پیدا کردن تمام اعداد صحیح بین 1۱ و 1،000،000۱٬۰۰۰٬۰۰۰ که به طور مساوی بر 417۴۱۷ تقسیم پذیر باشند را در نظر بگیرید. یک الگوریتم brute-force ابتداییممکن است تمام اعداد داخل محدوده را برای [[تقسیم پذیری]] امتحان کند. در حالیکه این مسئله را می توانمی‌توان بصورت بسیار موثرتر با شروع از 417۴۱۷ و اضافه کردن 417۴۱۷ به عدد قبلی تا وقتی که عدد حاصل بیش از 1،000،000۱٬۰۰۰٬۰۰۰ شود. بدین ترتیب تعداد نامزدها به 2398۲۳۹۸ (100000۱۰۰۰۰۰/417۴۱۷) کاهش یافته و هیچ امتحانی نیاز نیست.

== جایگزین‌های روش brute-force ==

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

. Springer. p.&nbsp; 7. ISBN 3-642-04100-0.

* [[حمله جستجوی فراگیر]]

* [[نماد O بزرگ]]