Giải thuật Tìm kiếm Ngẫu nhiên (Random Search) trong C++ - Giải thích, Ví dụ và Mã nguồn

Thuật toán Tìm kiếm Ngẫu nhiên là một phương pháp tìm kiếm dựa trên việc lựa chọn ngẫu nhiên một số giải pháp từ không gian tìm kiếm và kiểm tra xem chúng có thể làm giải pháp cho vấn đề hay không. Phương pháp này thường được sử dụng khi không có thông tin hoặc chiến lược cụ thể để hướng dẫn tìm kiếm.

Cách hoạt động

1. Khởi tạo: Bắt đầu với một tập hợp ngẫu nhiên các giải pháp ban đầu.
2. Đánh giá: Đánh giá chất lượng của từng giải pháp dựa trên hàm mục tiêu hoặc tiêu chí đánh giá.
3. Chọn lựa: Chọn một số giải pháp tốt nhất từ tập hợp dựa trên xác suất hoặc ngẫu nhiên.
4. Kiểm tra: Kiểm tra xem các giải pháp đã chọn có giải quyết vấn đề hay không.
5. Lặp lại: Lặp lại quá trình từ bước 2 đến bước 4 cho đến khi đạt được kết quả đủ tốt hoặc hết số lần lặp.

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. Phương pháp Tìm kiếm Ngẫu nhiên có thể chọn ngẫu nhiên các giá trị x và tính giá trị của hàm Fibonacci tại mỗi x, sau đó chọn giá trị x tương ứng với giá trị lớn nhất.

Mã nguồn ví dụ trong C++

#include <iostream>
#include <cstdlib>
#include <ctime>

int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int randomSearchFibonacci(int maxIterations) {
    int bestX = 0;
    int bestValue = 0;

    srand(time(0));

    for (int i = 0; i < maxIterations; ++i) {
        int x = rand() % maxIterations;
        int value = fibonacci(x);
        if (value > bestValue) {
            bestValue = value;
            bestX = x;
        }
    }

    return bestX;
}

int main() {
    int maxIterations = 20;
    int result = randomSearchFibonacci(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 Ngẫu nhiên để tối ưu hóa hàm số Fibonacci. Chúng ta chọn ngẫu nhiên các giá trị x và tính giá trị của hàm Fibonacci tại mỗi giá trị x. Sau đó, chúng ta chọn giá trị x tương ứng với giá trị lớn nhất mà chúng ta đã tính được.