Algoritma Carian Tempatan (Local Search) dalam C++- Penjelasan, Contoh dan Kod

Algoritma Carian Tempatan ialah kaedah untuk mencari penyelesaian terbaik dalam persekitaran keadaan semasa. Teknik ini sering digunakan untuk memperhalusi penyelesaian anggaran dengan mengubah suai komponen individu secara berulang untuk menemui keadaan yang lebih baik.

Bagaimana ia berfungsi

1. Permulaan: Mulakan dengan keadaan awal.
2. Jana Jiran: Jana negeri jiran dengan menukar komponen keadaan semasa.
3. Penilaian: Nilaikan kualiti negeri jiran menggunakan fungsi objektif.
4. Pilih Negeri Terbaik: Pilih negeri jiran dengan nilai objektif terbaik.
5. Ulang: Ulangi langkah 2 hingga 4 sehingga tiada keadaan jiran yang lebih baik dapat ditemui.

Contoh: Mengoptimumkan Fibonacci Fungsi

Pertimbangkan masalah pengoptimuman fungsi Fibonacci F(x) = F(x-1) + F(x-2) dengan F(0) = 0, F(1) = 1. Kami ingin mencari nilai x yang mana F(x) dimaksimumkan. Kita boleh menggunakan pendekatan Carian Tempatan untuk meneroka secara berulang dari setiap langkah.

Contoh Kod dalam 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;  
}  

Dalam contoh ini, kami menggunakan kaedah Carian Tempatan untuk mengoptimumkan Fibonacci fungsi. Kami mengulangi nilai x yang berbeza dan mengira Fibonacci nilai pada setiap x. Apabila nilai yang lebih baik ditemui, kami mengemas kini nilai terbaik dan x yang sepadan.