local_searchby simply replacing the
guesspredicate by the predicate
local_search(Vars) :- conflict_constraints(cs,List), ( List =  -> set_to_tent(Vars) ; List = [Constraint|_] -> term_variables(Constraint,[Var|_]), move(Var), local_search(Vars) ). move(Var) :- Var tent_get Value, NewValue is (1-Value), Var tent_set NewValue.
local_searchwith the predicate
hill_climb(Vars) :- conflict_constraints(cs,List), length(List,Count), ( Count = 0 -> set_to_tent(Vars) ; try_move(List,NewCount), NewCount < Count -> hill_climb(Vars) ; write('local optimum: '), writeln(Count) ). try_move(List,NewCount) :- select_var(List,Var), move(Var), conflict_constraints(cs,NewList), length(NewList,NewCount). select_var(List,Var) :- member(Constraint,List), term_variables(Constraint,Vars), member(Var,Vars).
try_moveis very inefficient, because it repeatedly goes through the whole list of conflict constraints to count the number of constraints in conflict. The facility to propagate tentative values supports more efficient maintenance of the number constraints in conflict. This technique is known as maintenance of invariants (see ). For the propositional satisfiability example we can maintain the number of satisfied clauses to make the hill climbing implementation more efficient.
BSumrecords for any tentative assignment of the propositional variables, the number of satisfied clauses. This speeds up hill climbing because, after each move, its effect on the number of satisfied clauses is automatically computed by the propagation of tentative values.
prop_sat_2(Vars) :- Vars = [X1,X2,X3], tent_init(Vars), clause_cons(X1 or neg X2 or X3,B1), clause_cons(neg X1 or neg X2,B2), clause_cons(X2 or neg X3,B3), BSum tent_is B1+B2+B3, hill_climb_2(Vars,BSum). clause_cons(Clause,B) :- Clause $= 1 r_conflict cs, B tent_is Clause. hill_climb_2(Vars,BSum) :- conflict_constraints(cs,List), BSum tent_get Satisfied, ( List= -> set_to_tent(Vars) ; select_var(List,Var), move(Var), tent_get(BSum) > Satisfied -> hill_climb_2(Vars,BSum) ; write('local optimum: '), writeln(Count) ).
BSumbefore and after the move is done. Remember that, since the move operator changes the tentative values of some variable, the
tent_isprimitive will automatically update the
Local search can be implemented in ECLiPSe with the repair library. Invariants can be implemented by tentative value propagation using tent_is/2.
Figure 13.4: Local Search and Invariants