O'Reilly logo

Fast Sequential Monte Carlo Methods for Counting and Optimization by Radislav Vaisman, Ad Ridder, Reuven Y. Rubinstein

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Chapter 5

Stochastic Enumeration Method

5.1 Introduction

In this chapter, we introduce a new generic sequential importance sampling (SIS) algorithm, called stochastic enumeration (SE) for counting #P problems. SE represents a natural generalization of one-step-look-ahead (OSLA) algorithms. We briefly introduce these concepts here and defer explanation of the algorithms in detail to the subsequent sections.

Consider a simple walk in the integer lattice c05-math-0001. It starts at the origin (0,0) and it repeatedly takes unit steps in any of the four directions, North (N), South (S), East (E), or West (W). For instance, an 8-step walk could be

equation

We impose the condition that the walk may not revisit a point that it has previously visited. These walks are called self-avoiding walks (SAW). SAWs are often used to model the real-life behavior of chain-like entities such as polymers, whose physical volume prohibits multiple occupation of the same spatial point. They also play a central role in modeling of the topological and knot-theoretic behavior of molecules such as proteins.

Clearly, the 8-step walk above is not a SAW inasmuch as it revisits point c05-math-0003. Figure 5.1 presents an example of a 130-step SAW. Counting ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required