Método de Monte Carlo
Origem: Wikipédia, a enciclopédia livre.
Em matemática, algoritmos Monte Carlo são algoritmos aleatórios que não garantem encontrar a solução do problema. Existem três classes de algoritmos Monte Carlo: Erro-Unilateral, Erro-Bilateral e Erro-Não-Limitado. Para detalhes, sugere-se a leitura de (HROMKOVIC,2001).
Índice |
[editar] Monte Carlo de Erro-Unilateral
Seja P um problema e A um algoritmo aleatório, A é um algoritmo Monte Carlo de Erro-Unilateral que resolve P se
i) para toda configuração x que é solução de P, 
, e
ii) para toda configuração x que não é solução de P, prob(A(x) = NÃO ) = 1
Ou seja, sempre que a resposta é NÃO, o algoritmo garante a certeza da resposta. Contudo, se a resposta for SIM, o algoritmo não garante que a resposta está correta.
[editar] Monte Carlo de Erro-Bilateral
Um algoritmo aleatório A é um algoritmo de Monte Carlo de Erro-Bilateral que computa o problema F se existe um número real ε, tal que para toda instância x de F
[editar] Monte Carlo de Erro-Não-Limitado
Os algoritmos Monte Carlo de Erro-Não-Limitado são comumente chamados de Algoritmos Monte Carlo. Um algoritmo aleatório A é um algoritmo de Monte Carlo se para qualquer entrada x do problema F
[editar] Referências
HROMKOVIC, J. Algorithms for Hard Problems: introduction to combinatorial optimization, randomization, approximation, and heuristics. [S.l.]: Springer-Verlag London Berlin Heidelberg New York, 2001.
