tailieunhanh - SIMULATION AND THE MONTE CARLO METHOD Episode 11

Tham khảo tài liệu 'simulation and the monte carlo method episode 11', kỹ thuật - công nghệ, cơ khí - chế tạo máy phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | 280 COUNTING VIA MONTE CARLO Some Other P-complete problems include counting the number of perfect matches in a bipartite graph determining the permanent of a matrix counting the number of fixed-size cliques in a graph and counting the number of forests in a graph. It is interesting to note 23 30 that in many cases the counting problem is hard to solve while the associated decision or optimization problem is easy in other words decision is easy counting is hard. For example finding the shortest path between two fixed vertices in a graph is easy while finding the total number of paths between the two vertices is difficult. In this chapter we show how P-complete counting problems can be viewed as particular instances of estimation problems and as such can be solved efficiently using Monte Carlo techniques such as importance sampling and MCMC. We also show that when using the standard CE method to estimate adaptively the optimal importance sampling density one can encounter degeneracy in the likelihood ratio which leads to highly variable estimates for large-dimensional problems. We solve this problem by introducing a particular modification of the classic MinxEnt method 17 called the parametric MinxEnt PME method. We show that PME is able to overcome the curse of the dimensionality degeneracy of the likelihood ratio by decomposing it into low-dimensional parts. Much of the theory is illustrated via the satisfiability counting problem in the conjunctive normal form CNF which plays a central role in NP completeness. We also present here a different approach which is based on sequential sampling. The idea is to break a difficult counting problem into a combination of easier ones. In particular for the SAT problem in the disjunctive normal form DNF we design an importance sampling algorithm and show that it possesses nice complexity properties. Although P-complete problems and in particular SAT are of both theoretical and practical importance and have been well studied .