Weighting for Godot: Learning Heuristics for GSAT

Jeremy Frank

We investigate an improvement to GSAT which associates a weight with each clause. GSAT moves to assignments maximizing the weight of satisfied clauses and this weight is incremented when GSAT moves to an assignment in which this clause is unsatisfied. We present results showing that this algorithm and its variants outperform one of the best known modifications of GSAT to date using two metrics: number of solved problems on a single try, and minimum mean number of flips to solve a test suite of problems.


This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.