1 /*
2 * SAT4J: a SATisfiability library for Java Copyright (C) 2004-2006 Daniel Le Berre
3 *
4 * Based on the original minisat specification from:
5 *
6 * An extensible SAT solver. Niklas E?n and Niklas S?rensson. Proceedings of the
7 * Sixth International Conference on Theory and Applications of Satisfiability
8 * Testing, LNCS 2919, pp 502-518, 2003.
9 *
10 * This library is free software; you can redistribute it and/or modify it under
11 * the terms of the GNU Lesser General Public License as published by the Free
12 * Software Foundation; either version 2.1 of the License, or (at your option)
13 * any later version.
14 *
15 * This library is distributed in the hope that it will be useful, but WITHOUT
16 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
17 * FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more
18 * details.
19 *
20 * You should have received a copy of the GNU Lesser General Public License
21 * along with this library; if not, write to the Free Software Foundation, Inc.,
22 * 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
23 *
24 */
25
26 package org.sat4j.minisat.orders;
27
28 import java.util.ArrayList;
29 import java.util.Collections;
30 import java.util.List;
31
32 import org.sat4j.minisat.core.ILits23;
33
34 /*
35 * Created on 16 oct. 2003
36 */
37
38 /**
39 * @author leberre Heuristique du prouveur. Changement par rapport au MiniSAT
40 * original : la gestion activity est faite ici et non plus dans Solver.
41 */
42 public class JWOrder extends VarOrder<ILits23> {
43
44 private static final long serialVersionUID = 1L;
45
46 private int computeWeight(int var) {
47 final int p = (var << 1);
48 int pos2 = lits.nBinaryClauses(p);
49 int neg2 = lits.nBinaryClauses(p ^ 1);
50 int pos3 = lits.nTernaryClauses(p);
51 int neg3 = lits.nTernaryClauses(p ^ 1);
52 long weight = (pos2 * neg2 * 100 + pos2 + neg2) * 5 + pos3 * neg3 * 10
53 + pos3 + neg3;
54 assert weight <= Integer.MAX_VALUE;
55 if (weight == 0) {
56 int pos = lits.watches(p).size();
57 int neg = lits.watches(p ^ 1).size();
58 weight = pos + neg;
59 }
60 return (int) weight;
61 }
62
63 /*
64 * (non-Javadoc)
65 *
66 * @see org.sat4j.minisat.IHeuristics#init()
67 */
68 @Override
69 public void init() {
70 super.init();
71 List<ValuedLit> v = new ArrayList<ValuedLit>(order.length);
72
73 for (int i = 1; i < order.length; i++) {
74 ValuedLit t = new ValuedLit(order[i],computeWeight(order[i]>> 1));
75 v.add(t);
76 }
77 Collections.sort(v);
78 // System.out.println(v);
79 for (int i = 0; i < v.size(); i++) {
80 ValuedLit t = v.get(i);
81 order[i + 1] = t.id;
82 int index = t.id >> 1;
83 varpos[index] = i + 1;
84 activity[t.id >> 1] = t.count;
85 }
86 lastVar = 1;
87
88 }
89
90 /*
91 * (non-Javadoc)
92 *
93 * @see org.sat4j.minisat.core.VarOrder#updateActivity(int)
94 */
95 @Override
96 protected void updateActivity(int var) {
97 activity[var] = computeWeight(var);
98 }
99
100 @Override
101 public String toString() {
102 return "Jeroslow-Wang static like heuristics updated when new clauses are learnt"; //$NON-NLS-1$
103 }
104 }