Algoritma Pencarian Lokal (Local Search) di C++- Penjelasan, Contoh dan Kode

Algoritma Pencarian Lokal adalah metode untuk menemukan solusi terbaik di sekitar keadaan saat ini. Teknik ini sering digunakan untuk menyempurnakan solusi perkiraan dengan memodifikasi komponen individu secara iteratif untuk menemukan keadaan yang lebih baik.

Bagaimana itu bekerja

1. Inisialisasi: Mulailah dengan keadaan awal.
2. Hasilkan Tetangga: Hasilkan status tetangga dengan mengubah komponen dari status saat ini.
3. Evaluasi: Mengevaluasi kualitas negara tetangga menggunakan fungsi tujuan.
4. Select Best State: Pilih negara tetangga dengan nilai objektif terbaik.
5. Ulangi: Lakukan iterasi melalui langkah 2 hingga 4 hingga tidak ada status tetangga yang lebih baik yang dapat ditemukan.

Contoh: Mengoptimalkan Fibonacci Fungsi

Perhatikan masalah optimisasi fungsi Fibonacci F(x) = F(x-1) + F(x-2) dengan F(0) = 0, F(1) = 1. Kita ingin mencari nilai x yang F(x) dimaksimalkan. Kita dapat menggunakan pendekatan Penelusuran Lokal untuk menjelajahi lebih jauh secara iteratif dari setiap langkah.

Contoh Kode di 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 metode Pencarian Lokal untuk mengoptimalkan Fibonacci fungsi. Kami beralih melalui nilai x yang berbeda dan menghitung Fibonacci nilai pada setiap x. Ketika nilai yang lebih baik ditemukan, kami memperbarui nilai terbaik dan x yang sesuai.