อัลกอริทึม การค้นหาในท้องถิ่น (Local Search) ใน C ++- คำอธิบาย ตัวอย่าง และโค้ด

อัลกอริทึม Local Search เป็นวิธีการค้นหาโซลูชันที่ดีที่สุดภายในบริเวณใกล้เคียงกับสถานะปัจจุบัน เทคนิคนี้มักใช้ในการปรับแต่งวิธีแก้ปัญหาโดยประมาณโดยการปรับเปลี่ยนส่วนประกอบแต่ละส่วนซ้ำๆ เพื่อค้นหาสถานะที่ดีขึ้น

มันทำงานอย่างไร

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;  
}  

ในตัวอย่างนี้ เราใช้วิธี Local Search เพื่อเพิ่มประสิทธิภาพ Fibonacci ฟังก์ชัน เราวนซ้ำผ่านค่าต่างๆ ของ x และคำนวณ Fibonacci ค่าที่แต่ละ x เมื่อพบค่าที่ดีกว่า เราจะอัปเดตค่าที่ดีที่สุดและค่า x ที่สอดคล้องกัน