Abstract:
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.
Registration: ISBN 978-0-262-51091-2