Portal de Periódicos da CAPES

Artigo Produção Nacional Revisado por pares

BIBTEX RIS

Amostragem por Importância para Estimar Valores Esperados: uma Abordagem com Heurísticas para Problemas Intervalares NP-Difíceis

2005; Sociedade Brasileira de Matemática Aplicada e Computacional; Volume: 6; Issue: 2 Linguagem: Português

10.5540/tema.2005.06.02.0261

2179-8451

Aline Brum Loreto, Roberto da Silva, L.V. Toscani, Luiz Antônio Ribeiro, Dalcídio Moraes Cláudio, L.A.S Leal,

Algorithms and Data Compression

O presente trabalho tem como objetivo mostrar a possibilidade de aproximar um problema NP-Dificil da computacao intervalar, atraves do uso de heuristicas com enfase em algoritmos baseados no Metodo de Monte Carlo. A fim de apresentar heuristicas para o problema generico de estimar numericamente, dada uma precisao , o valor esperado de uma funcao racional f(x1, ..., xn) com (x1, ..., xn) 2 Qn k=1 ×Ik escolhidos de acordo com uma funcao de densidade de probabilidade P(x1, ..., xn) conjunta, com Ik sendo intervalos, mostramos para o particular caso de um grafo regular de grau 2, cujos vertices podem assumir somente dois valores −1 e +1, o que restringe os intervalos a serem todos discretos Ik = [−1, 1] Z, k = 1, ..., n. Verificamos que o problema do valor esperado entre os pares de vertices adjacentes, tivera seu custo reduzido de O(2n) operacoes, atraves do calculo exato, para O(Nsample) que seria a complexidade encontrada quando aproximamos o resultado obtido pela Heuristica, onde Nsample e o numero de amostras de configuracoes escolhidas atraves do processo de amostragem por importância no contexto do algoritmo de Metropolis.