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

Abstract

O presente trabalho tem como objetivo mostrar a possibilidade de aproximar um problema NP-Difícil da computação intervalar, através do uso de heurísticas com ênfase em algoritmos baseados no Método de Monte Carlo. A fim de apresentar heurísticas para o problema genérico de estimar numericamente, dada uma precisão ", o valor esperado de uma função racional f(x1, ..., xn) com (x1, ..., xn) 2 Qn k=1 ×Ik escolhidos de acordo com uma função 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 vértices 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 vértices adjacentes, tivera seu custo reduzido de O(2n) operações, através do cálculo exato, para O(Nsample) que seria a complexidade encontrada quando aproximamos o resultado obtido pela Heurística, onde Nsample é o número de amostras de configurações escolhidas através do processo de amostragem por importância no contexto do algoritmo de Metrópolis.