در این قسمت تیم کدگیت را با آموزش جستجوی Brute Force در جاوا (Brute Force Search) همراهی کنید. همانند جلسات گذشته ابتدا الگوریتم Brute Force را توضیح و سپس به پیاده سازی آن میپردازیم. پیشنهاد میکنیم قبل از مطالعه این جلسه، آموزشهای زیر را بررسی کنید:
جستجوی Brute force
جستجوی Brute force یا جستجوی جامع (exhaustive search) برای حل مسائل استفاده میشود و در این روش تمامی حالت مسئله بررسی میشود. جستجو به روش brute-force به سادگی قابل پیادهسازی میباشد و همیشه جواب مسئله را در صورت وجود مییابد. با این حال، به دلیل اینکه هزینههای آن متناسب با تعداد کاندیدهای حل مسئله است، استفاده از آن در بسیاری از مسائل، که تعداد کاندیدهای حل مسئله تمایل به رشد بسیار سریع با افزایش اندازه مسئله را دارد، امکانپذیر نمیباشد.
به عنوان مثال ، تصور کنید که یک قفل کوچک با 4 رقم دارید (هر کدام بین 0-9). شما رمز خود را فراموش کرده اید ، اما نمی خواهید قفل دیگری خریداری کنید. از آنجایی که شما نمی توانید هیچ یک از ارقام را به یاد آورید، برای باز کردن قفل باید از روش جستجوی Brute Force استفاده کنید و تمام حالات رمز خود را امتحان کنید تا قفل شما باز شود.
جستجوی Brute force در جاوا
فرض کنید ما یک تابع به فرمول (x-1) * (x-1) =y را داریم. میخواهیم با استفاده از روش جستجوی Brute Force در جاوا، مینیمم این تابع را در محدوده (1- و 2) پیدا کنیم. یک کلاس به نام BruteForce میسازیم و در آن یک متد به نام f(double x) مینویسیم که در ورودی مقدار x را دریافت کرده و در خروجی تابع، مقدار y را میدهد. کد این قسمت به صورت زیر است:
public double f(double x) {
return (x - 1) * (x - 1);
}</pre></div>
دو متغیر(فیلد کلاس Brute Force) برای تعیین محدوده جستجوی خود تعریف میکنیم:
private static final double START_X = -1;
private static final double END_X = 2;
در این مسئله تعداد قدمهای برای بررسی x را 0.01 در نظر میگیریم. در جاوا آن را dx نامگذاری میکنیم. یک متد به نام BruteForce میسازیم و به صورت زیر پیاده سازی میکنیم:
public void bruteForceSearch() {
double startingPointX = START_X;
double min = f(startingPointX);
double dx = 0.01;
double minX = START_X;
for (double i = startingPointX; i < END_X; i += dx) {
if (f(i) < min) {
min = f(i);
minX = i;
}
}
System.out.println("The minimum value is f(x) = " + min + " and x = " + minX);
}
در کد بالا ما از نقطه شروع X اقدام به جستجوی مینمم میکنیم و در هر مرحله به اندازه dx یا 0.01 به جلو میرویم. این کار را تا نقطه پایان X ادامه میدهیم. سپس مقدار مینمم را چاپ میکنیم.
تست کد جستجوی Brute force در جاوا
برای تست کدهای بالا، کد Main زیر را پیاده سازی کنید:
public static void main(String[] args) {
BruteForce bruteForce = new BruteForce();
bruteForce.bruteForceSearch();
}
خروجی کد بالا به صورت زیر است:
The minimum value is f(x) = 1.7749370367472766E-30 and x = 1.0000000000000013
در زیر تصویری از نمودار (x-1) * (x-1) =y آوردهایم (جهت بررسی مینیمم):
همانطور که در تصویر میبینید مینیمم در نقطه x=1 میباشد و با جواب ما برابری میکند.
