Restarts and exponential acceleration of the Davis-Putnam-Loveland-Logemann algorithm: A large deviation analysis of the generalized unit clause heuristic for random 3-SAT.
Simona CoccoRémi MonassonPublished in: Ann. Math. Artif. Intell. (2005)
Keyphrases
- davis putnam
- propositional logic
- sat problem
- propositional satisfiability
- satisfiability problem
- search space
- cnf formula
- tree search
- optimal solution
- clause learning
- dynamic programming
- randomly generated
- random sat
- objective function
- large deviations
- np complete
- tabu search
- computational complexity
- search algorithm
- orders of magnitude
- constraint satisfaction problems
- learning algorithm
- particle swarm optimization
- linear programming
- simulated annealing
- np hard
- evolutionary algorithm
- lower bound
- reinforcement learning