首页 | 本学科首页   官方微博 | 高级检索  
     检索      


How Many Needles are in a Haystack, or How to Solve #P-Complete Counting Problems Fast
Authors:Reuven Y Rubinstein
Institution:(1) Faculty of Industrial Engineering and Management, Technion, Haifa, Israel
Abstract:We present two randomized entropy-based algorithms for approximating quite general #P-complete counting problems, like the number of Hamiltonian cycles in a graph, the permanent, the number of self-avoiding walks and the satisfiability problem. In our algorithms we first cast the underlying counting problem into an associate rare-event probability estimation, and then apply dynamic importance sampling (IS) to estimate efficiently the desired counting quantity. We construct the IS distribution by using two different approaches: one based on the cross-entropy (CE) method and the other one on the stochastic version of the well known minimum entropy (MinxEnt) method. We also establish convergence of our algorithms and confidence intervals for some special settings and present supportive numerical results, which strongly suggest that both ones (CE and MinxEnt) have polynomial running time in the size of the problem.
Keywords:Cross-entropy  Rare-event probability estimation  Hamilton cycles  Self-avoiding walks  #P-complete problems  Stochastic and simulation-based optimization
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号