جستجوی جامع

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو
جستجوی جامع
کلاس الگوریتم جستجو

در علوم کامپیوتر، جستجوی خام و بی‌خردانه (به انگلیسی: brute-force search) و یا جستجوی جامع(فراگیر) (به انگیسی: exhaustive search)، همچنین به نام جستجوی تولید و تِست (به انگلیسی: generate and test) شناخته شده، روشی بدیهی در عین حال بسیار کلی برای حل مسأله می باشد. این روش که شامل شمارش نظام مند تمام نامزدهای ممکن برای حل و چک کردن اینکه آیا هر یک از نامزدها قادر به ارضا شرط مسأله است. به عنوان مثال، یک الگوریتم brute-force برای پیدا کردن مقسوم علیه های یک عدد طبیعی N، شامل شمردن تمام اعداد صحیح از 1 تا ریشه ی دوم از 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 می باشد. بدین ترتیب برای یافتن مقسوم علیه های یک عدد 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 شامل امتحان کردن تمامی کلیدهای ممکن تا وقتی که کلید صحیح پیدا شود. این روش همیشه، به وسیله کسی که نتواند از کاستی های سیستم رمزنگاری شده استفاده کند، قابل بکارگیری می باشد. طول کلید تعیین کننده ی قابل اجرا بودن روش 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

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

پیوند به بیرون[ویرایش]

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