خوارزمية البحث المحلي (Local Search) في C ++- شرح ومثال ورمز

تعد خوارزمية البحث المحلي طريقة للعثور على أفضل حل في محيط الحالة الحالية. غالبًا ما تُستخدم هذه التقنية لتحسين الحلول التقريبية عن طريق تعديل المكونات الفردية بشكل متكرر لاكتشاف حالات أفضل.

كيف تعمل

1. التهيئة: ابدأ بالحالة الأولية.
2. إنشاء الجيران: قم بإنشاء دول مجاورة عن طريق تغيير أحد مكونات الحالة الحالية.
3. التقييم: تقييم جودة الدول المجاورة باستخدام وظيفة موضوعية.
4. حدد أفضل حالة: اختر الدولة المجاورة بأفضل قيمة موضوعية.
5. كرر: كرر الخطوات من 2 إلى 4 حتى لا يمكن العثور على دولة مجاورة أفضل.

مثال: تحسين Fibonacci الوظيفة

ضع في اعتبارك مشكلة التحسين للدالة Fibonacci F(x) = F(x-1) + F(x-2) مع F(0) = 0 ، F(1) = 1. نريد إيجاد قيمة x من أجلها تم تكبير F(x). يمكننا استخدام نهج البحث المحلي لاستكشاف أبعد من كل خطوة بشكل متكرر.

مثال رمز في C ++

#include <iostream>  
  
int fibonacci(int n) {  
    if(n <= 0) return 0;  
    if(n == 1) return 1;  
    return fibonacci(n- 1) + fibonacci(n- 2);  
}  
  
int localSearchFibonacci(int maxIterations) {  
    int bestX = 0;  
    int bestValue = 0;  
  
    for(int x = 0; x < maxIterations; ++x) {  
        int value = fibonacci(x);  
        if(value > bestValue) {  
            bestValue = value;  
            bestX = x;  
        }  
    }  
  
    return bestX;  
}  
  
int main() {  
    int maxIterations = 20;  
    int result = localSearchFibonacci(maxIterations);  
  
    std::cout << "Optimal x for maximum Fibonacci value: " << result << std::endl;  
  
    return 0;  
}  

في هذا المثال ، نستخدم طريقة البحث المحلي لتحسين الوظيفة Fibonacci. نحن نكرر القيم المختلفة لـ x ونحسب Fibonacci القيمة عند كل x. عندما يتم العثور على قيمة أفضل ، نقوم بتحديث أفضل قيمة و x المقابلة لها.