Αναζήτηση

Πλοήγηση

• Κοινότητες
• Συγγραφείς
• Έτος
• Τίτλοι
• Θέματα

Ο Χώρος μου

• Είσοδος

Learning to select branching rules in the DPLL procedure for satisfiability

Lagoudakis Michael, Littman, M.

Πλήρης Εγγραφή

---

Περίληψη

The DPLL procedure is the most popular completesatisfiability (SAT) solver. While its worstcase complexity is exponential, the actual runningtime is greatly affected by the orderingof branch variables during the search. Severalbranching rules have been proposed, but noneis the best in all cases. This work investigatesthe use of automated methods for choosing themost appropriate branching rule at each node inthe search tree. We consider a reinforcementlearningapproach where a value function, whichpredicts the performance of each branching rulein each case, is learned through trial runs on atypical problem set of the target class of SATproblems. Our results indicate that, providedsufficient training on a given class, the resultingstrategy performs as well as (and, in some cases,better than) the best branching rule for that class.

Υπηρεσίες