48 const int MAX_MINC_FACTORS = 400;
49 extern const double mincFactors[MAX_MINC_FACTORS];
52 getMincFactor(
int domSize) {
53 return mincFactors[domSize - 1];
63 const int WIDTH_LIANG_BAI_FACTORS = 400;
64 extern const double liangBaiFactors[WIDTH_LIANG_BAI_FACTORS * WIDTH_LIANG_BAI_FACTORS];
67 getLiangBaiFactor(
int index,
int domSize) {
68 return liangBaiFactors[index*WIDTH_LIANG_BAI_FACTORS + domSize - 1];
85 ValToUpdate(
const ViewArray<View>& x,
86 int minDomVal,
int maxDomVal, Region& r);
92 double getMincUpdate(
int val,
unsigned int varSize)
const;
99 double getLiangUpdate(
int val,
unsigned int idx,
unsigned int varSize)
const;
104 ValToUpdate::ValToUpdate(
const ViewArray<View>&
x,
105 int minDomVal,
int maxDomVal, Region&
r)
106 : minVal(minDomVal) {
107 unsigned int width = maxDomVal - minDomVal + 1;
108 mincUpdate =
r.alloc<
double>(width);
109 std::fill(mincUpdate, mincUpdate + width, 1);
110 liangUpdate =
r.alloc<
double>(width);
111 std::fill(liangUpdate, liangUpdate + width, 1);
113 for (
int i=0;
i<
x.size();
i++) {
115 size_t s =
x[
i].size();
116 for (ViewValues<View> val(x[i]); val(); ++val) {
117 int idx = val.val() - minVal;
118 mincUpdate[idx] *= getMincFactor(s-1) / getMincFactor(s);
119 liangUpdate[idx] *= getLiangBaiFactor(i, s-1) / getLiangBaiFactor(i, s);
125 ValToUpdate::getMincUpdate(
int val,
unsigned int varSize)
const {
126 return mincUpdate[val-minVal] / getMincFactor(varSize-1);
130 ValToUpdate::getLiangUpdate(
int val,
unsigned int idx,
131 unsigned int varSize)
const {
132 return liangUpdate[val-minVal] / getLiangBaiFactor(idx, varSize-1);
137 void cbsdistinct(Space&,
unsigned int prop_id,
const ViewArray<View>& x,
138 Propagator::SendMarginal send) {
147 for (
int i=0;
i<
x.size();
i++) {
148 unsigned int s =
x[
i].size();
149 if ((s >= MAX_MINC_FACTORS) || (s >= WIDTH_LIANG_BAI_FACTORS))
151 "Variable cardinality too big for using counting-based"
152 "search with distinct constraints");
153 ub.minc *= getMincFactor(s);
154 ub.liangBai *= getLiangBaiFactor(i, s);
158 int minVal = std::numeric_limits<int>::max();
159 int maxVal = std::numeric_limits<int>::min();
160 for (
const auto& v : x) {
161 if (
v.assigned())
continue;
162 minVal = std::min(
v.min(), minVal);
163 maxVal = std::max(
v.max(), maxVal);
169 ValToUpdate valToUpdate(x, minVal, maxVal, r);
173 double* solCounts =
r.alloc<
double>(maxVal - minVal + 1);
175 for (
int i=0;
i<
x.size();
i++) {
179 double normalization = 0;
181 for (ViewValues<View> val(x[i]); val(); ++val) {
184 unsigned int s =
x[
i].size();
188 localUB.minc *= valToUpdate.getMincUpdate(v, s);
189 localUB.liangBai *= valToUpdate.getLiangUpdate(v, i, s);
192 double lowerUB = std::min(localUB.minc, ::sqrt(localUB.liangBai));
193 solCounts[val.val() - minVal] = lowerUB;
194 normalization += lowerUB;
199 for (ViewValues<View> val(x[i]); val(); ++val) {
207 x[i].baseval(val.val()),
208 solCounts[val.val() - minVal] / normalization);
214 void cbssize(
const ViewArray<View>& x, Propagator::InDecision in,
215 unsigned int& size,
unsigned int& size_b) {
218 for (
const auto& v : x) {
Exception: Base-class for exceptions
bool assigned(View x, int v)
Whether x is assigned to value v.
unsigned int size(I &i)
Size of all ranges of range iterator i.
Gecode toplevel namespace
Post propagator for SetVar SetOpType SetVar SetRelType r
Post propagator for SetVar x
Gecode::IntArgs i({1, 2, 3, 4})