PPT Slide

B) Stochastic Search Methods

• GSAT: Randomized local search for SAT testing. Viable alternative to systematic, complete methods.

• Progress:

  • 1991: 10 vars, 500 clause theories.
  • 1995: 2,000 to 20,000 vars, up to 500,000 clauses

• Approaches size of practical applications. E.g. in scheduling, planning, diagnosis, circuit design,  and constraint-logic programming.

See proceedings for many additional pointers.

Previous slide

Next slide

Back to first slide

View graphic version