Giải thuật Tìm kiếm theo Cục bộ (Local Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Thuật toán Tìm kiếm theo Cục bộ là một phương pháp tìm kiếm giải pháp tốt nhất trong một vùng xung quanh trạng thái hiện tại. Phương pháp này thường được sử dụng để cải thiện giải pháp gần đúng bằng cách thay đổi từng phần tử một để tìm ra trạng thái tối ưu hơn.

Cách hoạt động

1. Khởi tạo: Bắt đầu với một trạng thái ban đầu.
2. Tạo lân cận: Tạo ra các trạng thái lân cận bằng cách thay đổi một phần tử trong trạng thái hiện tại.
3. Đánh giá: Đánh giá mức độ tốt của các trạng thái lân cận bằng hàm mục tiêu.
4. Chọn trạng thái tốt nhất: Chọn trạng thái lân cận có giá trị mục tiêu tốt nhất.
5. Lặp lại: Lặp lại quá trình từ bước 2 đến bước 4 cho đến khi không thể tìm thấy trạng thái lân cận tốt hơn nữa.

Ví dụ: Tối ưu hóa Hàm Số Fibonacci

Xét bài toán tối ưu hóa hàm số Fibonacci F(x) = F(x-1) + F(x-2) với F(0) = 0, F(1) = 1. Chúng ta muốn tìm giá trị x mà F(x) là lớn nhất. Ta có thể sử dụng phương pháp Tìm kiếm theo Cục bộ để tiến xa hơn từ mỗi bước.

Mã nguồn ví dụ trong 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;
}

Trong ví dụ này, chúng ta sử dụng phương pháp Tìm kiếm theo Cục bộ để tối ưu hóa hàm số Fibonacci. Chúng ta lặp qua các giá trị x và tính giá trị của hàm Fibonacci tại mỗi x. Khi tìm thấy giá trị tốt hơn, chúng ta cập nhật giá trị tốt nhất và x tương ứng.