Algoritmo de Pesquisa Aleatória (Random Search) em C++- Explicação, Exemplo e Código

O algoritmo Random Search é um método de busca baseado em selecionar aleatoriamente um conjunto de soluções do espaço de busca e verificar se elas podem resolver o problema. Essa abordagem é frequentemente utilizada quando não há informações ou estratégias específicas para orientar a busca.

Como funciona

1. Inicialização: Comece com um conjunto gerado aleatoriamente de soluções iniciais.
2. Avaliação: Avalie a qualidade de cada solução com base na função objetivo ou critérios de avaliação.
3. Seleção: Selecione um subconjunto das melhores soluções do conjunto com base em probabilidades ou seleção aleatória.
4. Teste: Testa se as soluções selecionadas são capazes de resolver o problema.
5. Repetir: Repita as etapas 2 a 4 até que um resultado satisfatório seja alcançado ou um número predefinido de iterações seja alcançado.

Exemplo: Otimizando a Fibonacci Função

Considere o problema de otimização da Fibonacci função F(x) = F(x-1) + F(x-2) com F(0) = 0, F(1) = 1. Queremos encontrar o valor de x para o qual F(x) é maximizado. O método Random Search pode selecionar aleatoriamente valores de x, calcular o Fibonacci valor em cada x e escolher o valor de x correspondente ao maior Fibonacci valor obtido.

Exemplo de código em 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;  
}  

Neste exemplo, usamos o método Random Search para otimizar a Fibonacci função. Selecionamos valores de x aleatoriamente, calculamos o Fibonacci valor em cada x e, em seguida, escolhemos o valor de x correspondente ao Fibonacci valor mais alto que calculamos.