Approaches to AI 29
Consider a SAT problem where formula F is given by: F = (a v ¬b) ∧ (¬a v b v c) ∧ (¬c v d) ∧ d ∧ (¬a v b v d) ∧ (¬a v ¬d) The heuristic function h(F) returns the number of satisfied clauses in the formula F. Observe that one has to maximize the heuristic value. A candidate assignment, or state, is of the form (abcd). If the state is 0000, then the assignment is a a=0, b=0, c=0 and d=0. Let the MoveGen function be such that it changes 1 bit in a candidate. For example, from the state 0000 with one-bit change we get 0001, 0010, 0100 and 1000 as the neighbors. Now let the initial state be 1010.
