26 std::vector<bool> var_mask;
27 std::vector<bool> values;
30 if (var_mask != rhs.var_mask)
32 if (values.size() != rhs.values.size())
34 for (std::size_t i=0; i<values.size(); i++)
38 if (values[i] != rhs.values[i])
59 std::vector<bool> row_is_consistent;
60 std::size_t parent_idx;
66 pa.var_mask.resize(num_vars,
false);
67 pa.values.resize(num_vars,
false);
75 std::vector<std::size_t> antecedents;
76 std::size_t consequent;
78 std::vector<ConjunctionImplication> conjunction_implications;
79 void add_conjunction_implication(
80 std::vector<std::size_t> antecedents, std::size_t consequent)
83 x.antecedents = antecedents;
84 x.consequent = consequent;
85 conjunction_implications.push_back(x);
88 std::vector< std::vector<bool> > truth_table;
96 std::vector<bool> row(num_vars,
false);
100 std::vector<ConjunctionImplication>::iterator implit;
101 for (implit=conjunction_implications.begin();
102 implit!=conjunction_implications.end(); implit++)
104 if (row[implit->consequent])
106 std::vector<std::size_t>::iterator anteit;
107 for (anteit=implit->antecedents.begin();
108 anteit!=implit->antecedents.end(); anteit++)
111 if (anteit!=implit->antecedents.end())
115 if (implit==conjunction_implications.end())
116 truth_table.push_back(row);
120 for (iconst=0; iconst<num_vars; iconst++)
122 row[iconst] = !row[iconst];
126 if (!(iconst<num_vars))
135 void cheapest(
const Assignment & current,
136 const VarVal & target_assignment,
137 const std::vector<double> & var_costs,
138 std::vector<AssignmentDelta> & deltas)
141 std::vector<SearchVertex> generated;
144 SearchVertex v_start;
145 v_start.cost_sofar = 0.0;
146 v_start.delta.result = current;
147 v_start.row_is_consistent.resize(truth_table.size());
148 v_start.parent_idx = 0;
149 for (std::size_t irow=0; irow<truth_table.size(); irow++)
153 for (; ic<num_vars; ic++)
155 if (!current.var_mask[ic])
157 if (current.values[ic] != truth_table[irow][ic])
161 v_start.row_is_consistent[irow] =
false;
163 v_start.row_is_consistent[irow] =
true;
165 heap.insert(generated.size(), v_start.cost_sofar);
166 generated.push_back(v_start);
174 fprintf(stderr,
"error, no path found!\n");
177 top_idx = heap.top_idx();
178 SearchVertex v_top = generated[top_idx];
182 if (v_top.delta.result.var_mask[target_assignment.var])
184 if (v_top.delta.result.values[target_assignment.var]
185 == target_assignment.value)
191 for (std::size_t ic_new=0; ic_new<num_vars; ic_new++)
193 if (v_top.delta.result.var_mask[ic_new])
196 for (
int valnum=0; valnum<2; valnum++)
198 bool value = valnum ?
true :
false;
200 SearchVertex v_succ = v_top;
201 v_succ.delta.new_varval.var = ic_new;
202 v_succ.delta.new_varval.value = value;
203 v_succ.cost_sofar += var_costs[ic_new];
204 v_succ.parent_idx = top_idx;
207 for (std::size_t irow=0; irow<truth_table.size(); irow++)
209 if (!v_succ.row_is_consistent[irow])
211 if (truth_table[irow][ic_new] != value)
212 v_succ.row_is_consistent[irow] =
false;
216 std::size_t irow_first;
217 for (irow_first=0; irow_first<truth_table.size(); irow_first++)
218 if (v_succ.row_is_consistent[irow_first])
220 if (!(irow_first<truth_table.size()))
224 v_succ.delta.result.var_mask[ic_new] =
true;
225 v_succ.delta.result.values[ic_new] = value;
226 for (std::size_t ic=0; ic<num_vars; ic++)
228 if (v_succ.delta.result.var_mask[ic])
230 bool candidate_value = truth_table[irow_first][ic];
231 std::size_t irow_different;
232 for (irow_different=irow_first+1; irow_different<truth_table.size(); irow_different++)
234 if (!v_succ.row_is_consistent[irow_different])
236 if (truth_table[irow_different][ic] != candidate_value)
239 if (irow_different<truth_table.size())
241 v_succ.delta.result.var_mask[ic] =
true;
242 v_succ.delta.result.values[ic] = candidate_value;
247 for (gi=0; gi<generated.size(); gi++)
248 if (v_succ.delta.result == generated[gi].delta.result)
250 if (gi<generated.size())
252 if (v_succ.cost_sofar < generated[gi].cost_sofar)
254 generated[gi].cost_sofar = v_succ.cost_sofar;
255 generated[gi].parent_idx = top_idx;
256 heap.update(gi, v_succ.cost_sofar);
261 heap.insert(generated.size(), v_succ.cost_sofar);
262 generated.push_back(v_succ);
268 std::vector<std::size_t> path_idxs;
269 path_idxs.push_back(top_idx);
270 while (path_idxs.back())
271 path_idxs.push_back(generated[path_idxs.back()].parent_idx);
272 std::reverse(path_idxs.begin(), path_idxs.end());
274 for (std::size_t ip=1; ip<path_idxs.size(); ip++)
275 deltas.push_back(generated[path_idxs[ip]].delta);
Definition: logic_engine.h:55
Definition: logic_engine.h:50
Definition: logic_engine.h:73
Definition: logic_engine.h:13
Definition: logic_engine.h:24
Definition: logic_engine.h:45