موضوع مقاله: جستجوی بروت-فورس | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # جستجوی بروت-فورس | مقدمه: این روش که شامل شمارش نظام مند تمام نامزدهای ممکن برای حل و چک کردن اینکه آیا هر یک از نامزدها قادر به برقراری شرط مسئله است. | ## بخش 1: جستجوی بروت-فورس | به عنوان مثال، یک الگوریتم Brute-force برای پیدا کردن مقسوم علیه‌های یک عدد طبیعی N، شامل شمردن تمام اعداد صحیح از ۱ تا ریشهٔ دوم از n است، و بررسی اینکه آیا n به هر یک از آن‌ها تقسیم پذیر است یا خیر. با این حال، به دلیل اینکه هزینه‌های آن متناسب با تعداد نامزدهای حل مسئله است، استفاده از آن در بسیاری از مسائل عملی، که تعداد نامزدهای حل مسئله تمایل به رشد بسیار سریع با افزایش اندازه مسئله را دارد، امکانپذیر نمی‌باشد. این روش هنگامی به کار می‌رود که اندازه مسئله محدود می‌باشد یا روش‌های ابتکاری برای کاهش تعداد مجموعه نامزدهای حل مسئله وجود دارد. به عنوان مثال، در برنامه‌های حساس که در آن هر گونه خطا در الگوریتم می‌تواند عواقب بسیار جدی داشته باشد، یا در هنگام استفاده از رایانه برای اثبات یک قضیه ریاضی این روش به کار برده می‌شود. هر یک از این روش‌ها، داده P از یک مسئله را به عنوان یک پارامتر در نظر گرفته و مراحل زیر را انجام می‌دهد: (first (P: ایجاد اولین نامزد برای حل P. یک راه مناسب برای انجام این کار بازگرداندن «نامزد پوچ» به عنوان نامزد بعدی می‌باشد، برخی از دادهٔ Λ به صورت معمول برای که تمایز از نامزدهای واقعی استفاده می‌شود. به همین ترتیب در صورتی که هیچ نامزدی برای حل P موجود نباشد مرحله first نیز باید دادهٔ Λ برگرداند. به عنوان مثال، تعداد نامزدهای حل مسئله برای یافتن مقسوم علیه‌های عدد n, n می‌باشد. بدین ترتیب برای یافتن مقسوم علیه‌های یک عدد ۱۶ رقمی، نیاز به اجرای حداقل ۱۰ به توان ۱۵ جستجو می‌باشد که برای یک دستگاه رایانه معمولی چند روز طول خواهد کشید. اگر n یک عدد طبیعی ۶۴ بیتی ۱۹ رقمی تصادفی باشد به‌طور متوسط، جستجو حدود ۱۰ سال طول می‌کشد. | ## بخش 2: جستجوی بروت-فورس | به عنوان مثال، جستجوی یک چیدمان خاص از ۱۰ حرف، ۱۰ = ۳٬۶۲۸٬۸۰۰ نامزد خواهد داشت، که یک PC ی معمولی می‌تواند در کمتر از یک ثانیه ایجاد و تست نماید. با این حال، با اضافه کردن یک حرف (که تنها ۱۰ درصد افزایش در حجم داده هاست) تعداد نامزدها را ۱۱ برابر می‌کند (تعداد نامزدها %۱۰۰۰ افزایش می‌یابد). سرعت بخشیدن به الگوریتم از جمله راه‌های سرعت بخشیدن به الگوریتم Brute-force استفاده از راه‌های ابتکاری مخصوص برای هر مسئله به منظور کاهش فضای جستجو یا به عبارتی کاهش تعداد نامزدهای قابل قبول می‌باشد. به عنوان مثال، مسئله معروف ۸ ملکه را در نظر بگیرید، در این مسئله ۸ ملکه در صفحه شطرنج طوری باید قرار بگیرند که هیچ‌یک قادر به حمله به دیگری نباشد. از آنجا که هر یک از ملکه‌ها را می‌توان در هر یک از ۶۴ مربع قرار داد، در اصل ۲۸۱٬۴۷۴٬۹۷۶٬۷۱۰٬۶۵۶ =۶۴۸ (بیش از ۲۸۱ تریلیون) حالت امکان‌پذیر وجود دارد. با این حال، با در نظر گرفتن این موضوع که همه ملکه‌ها یکسان هستند، و این که هیچ دو ملکه‌ای را نمی‌توان در یک خانه قرار داد، نتیجه می‌گیریم که نامزدها تمام راه‌های ممکن از انتخاب مجموعه‌ای از ۸ مربع از مجموعه‌ای از ۶۴ مربع است که به معنی انتخاب ۸ از ۶۴ می‌باشد (۶۴!/۵۶!۸! همچنین، به سادگی می‌توان تشخیص داد که هیچ آرایشی با دو ملکه در یک سطر یا ستون نمی‌تواند یک راه حل باشد؛ بنابراین، می‌توان گفت که هر یک از ملکه‌ها در یک ردیف مثلاً ملکه ۱ در ردیف ۱، ملکه ۲ در ردیف ۲، و … به گونه‌ای که هیچ‌یک در یک سطر نیز نباشند باید قرار بگیرند. همان گونه که این مثال نشان می‌دهد، کمی تجزیه و تحلیل اغلب منجر به کاهش چشمگیر در تعداد نامزدها می‌شود، و ممکن است یک مسئله غیرقابل حل را به مسئله‌ای پیش پا افتاده تبدیل کند. این مثال همچنین نشان می‌دهد که روش شمارش نامزدها (اول و بعدی) برای مجموعهٔ محدود از نامزدها ممکن است به راحتی یا حتی ساده‌تر از مجموعه اصلی باشد. در برخی موارد، تجزیه و تحلیل ممکن است نامزدها را محدود به تمامی جواب‌های مسئله نماید. | ## بخش 3: جستجوی بروت-فورس | به عنوان مثال، مسئله پیدا کردن تمام اعداد صحیح بین ۱ و ۱٬۰۰۰٬۰۰۰ که به‌طور مساوی بر ۴۱۷ تقسیم پذیر باشند را در نظر بگیرید. در حالیکه این مسئله را می‌توان به صورت بسیار مؤثرتر با شروع از ۴۱۷ و اضافه کردن ۴۱۷ به عدد قبلی تا وقتی که عدد حاصل بیش از ۱٬۰۰۰٬۰۰۰ شود. بدین ترتیب تعداد نامزدها به ۲۳۹۸ (۱۰۰۰۰۰/۴۱۷) کاهش یافته و هیچ امتحانی نیاز نیست. جایگزین‌های روش Brute-force روش‌های جستجوی متعددی برای یافتن راه حل هنگامی که اطلاعات محدودی از جواب مسئله در دسترس است وجود دارد. برای مثال تعیین بیشینه و کمینه در مراحل ابتدایی حل یک مسئله می‌تواند بسیار مفید باشد. در بعضی موارد همانند تجزیه جملات، روش‌هایی مثل تجزیه نمودار ممکن است درجه سختی مسئله را از حد نمایی به سختی چندجمله‌ای تقلیل دهد. برای مثال در شطرنج کامپیوتری، برای انتخاب هر حرکت، بجای اینکه تمام گزینه‌ها تا انتهای بازی در نظر گرفته شود، تعداد محدودی از بیشینه و کمینه‌ها برای تعداد مشخصی از حرکت‌ها آینده به صورت استاتیک بررسی می‌شود. این روش همیشه، به وسیله کسی که نتواند از کاستی‌های سامانه رمزنگاری شده‌استفاده کند، قابل بکارگیری می‌باشد. | ## جمع‌بندی | کلیدهایی که به صورت دلبخواه بی معنا یا گمراه‌کننده انتخاب شوند، می‌توانند کاربرد این روش را به شدت دشوارتر کنند.