1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
| #include "types.h"
/*********************************************************************
This file has 5 parts:
0. This introduction.
1. A main() function, which can be used to demonstrate MakeURBCSP().
2. MakeURBCSP().
3. ran2(), a random number generator.
4. The four functions StartCSP(), AddConstraint(), AddNogood(), and
EndCSP(), which are called by MakeURBCSP(). The versions
of these functions given here print out each instance, listing
the incompatible value pairs of each constraint. You will need
to replace these functions with versions that mesh with your
system and data structures.
*********************************************************************/
/*********************************************************************
1. A simple main() function which reads in command line parameters
and generates CSPs.
*********************************************************************/
int main (int argc, char **argv)
{
int err = 0;
if (argc != 7)
{
puts ("usage: urbcsp #vars #vals #constraints #nogoods seed "
"instances");
err = EXIT_FAILURE;
}
else
{
int N, D, I, i;
double densite, tightness;
char *chaine1;
char *chaine2;
long S;
chaine1 = argv[3];
chaine2 = argv[4];
N = atoi (argv[1]);
D = atoi (argv[2]);
densite = atof (chaine1);
tightness = atof (chaine2);
S = atoi (argv[5]);
I = atoi (argv[6]);
initialisations (N, D);
/* Seed passed to ran2() must initially be negative. */
if (S > 0)
S = -S;
for (i = 0; i < I; ++i)
if (!MakeURBCSP (N, D, densite, tightness, &S))
{
err = EXIT_FAILURE;
break;
}
}
return err;
}
void initialisations (int N, int D)
{
/*initialisation des variables globales */
int i = 0, j = 0;
NB_VAR = N;
NB_VAL = D;
rel = malloc (sizeof *rel);
csp = malloc (sizeof *csp);
for (i = 0; i < NB_VAL; i++)
for (j = 0; j < NB_VAL; j++)
*rel[i][j] = FAUX;
for (i = 0; i < NB_VAR; i++)
for (j = 0; j < NB_VAR; j++)
csp->C[i][j] = NULL;
}
/*********************************************************************
2. MakeURBCSP() creates a uniform binary constraint satisfaction
problem with a specified number of variables, domain size,
tightness, and number of constraints. MakeURBCSP() calls
four functions, StartCSP(), AddConstraint(), AddNogood(), and
EndCSP(), which actually create the CSP (that is, build a data
structure). Feel free to change the signatures of these functions.
Note that numbering starts from 0: the variables are numbered 0..N-1,
and the values are numbered 0..K-1.
INPUT PARAMETERS:
N: number of variables
D: size of each variable's domain
densite: number of constraints allowed/total number of constraint
T: number of compatible value pairs in each constraint
Seed: a negative number means start a new sequence of
pseudo-random numbers; a positive number means continue
with the same sequence. S is turned positive by ran2().
RETURN VALUE:
Returns 0 if there is a problem; 1 for normal completion.
*********************************************************************/
int MakeURBCSP (int N, int D, double densite, double tightness, long *Seed)
{
int PossibleCTs, PossibleNGs; /* CT means "constraint" */
unsigned long *CTarray, *NGarray; /* NG means "nogood pair" */
long selectedCT, selectedNG;
int c, r;
int var1, var2;
static int instance;
int nb_clauses_total;
int C; //nbre de clauses permises
int T; //nbre de tuples autorisees
int T_tot; //nbre de tuples total
int variable1, variable2;
int valeur1, valeur2;
/* Check for valid values of N, D, C, and T. */
if (N < 2 || N > NB_VAR)
{
printf ("MakeURBCSP: ***Illegal value for N: %d\n", N);
return 0;
}
if (D < 2 || D > NB_VAL)
{
printf ("MakeURBCSP: ***Illegal value for D: %d\n", D);
return 0;
}
if (densite < 0.0 || densite > 1.0)
{
printf ("MakeURBCSP: ***Illegal value for densite: %f\n", densite);
return 0;
}
if (tightness < 0.0 || tightness > 1.0)
{
printf ("MakeURBCSP: ***Illegal value for T: %f\n", tightness);
return 0;
}
else
{
T = (int) ((D * D)) * (1.0 - tightness);
printf ("T = %d\n", T);
}
if (*Seed < 0) /* starting a new sequence of random numbers */
instance = 0;
else
++instance; /* increment static variable */
StartCSP (instance);
/* The program has to choose randomly and uniformly m values from
n possibilities. It uses the following logic for both constraints
and nogood value pairs:
1. Let t[] be an array of the n possibilities
2. for i = 0 to m-1
3. r = random(i, n-1) ; random() returns an int in [i,n-1]
4. swap t[i] and t[r]
5. end-for
At the end of the for loop, the elements from t[0] to t[m-1] are
the m randomly selected elements.
*/
/* Create an array for each possible binary constraint. */
PossibleCTs = N * (N - 1) / 2;
CTarray = malloc (PossibleCTs * sizeof *CTarray);
/* Create an array for each possible value pair. */
PossibleNGs = D * D;
NGarray = malloc (PossibleNGs * sizeof *NGarray);
/* Initialize the CTarray. Each entry has one var in the high two
bytes, and the other in the low two bytes. */
c = 0;
for (var1 = 0; var1 < (N - 1); ++var1)
for (var2 = var1 + 1; var2 < N; ++var2)
CTarray[c++] = (var1 << 16) | var2;
/*Calcul du nombre de contraintes permises a partir de la densite */
/*et du nombre de contraintes total */
nb_clauses_total = N * (N - 1) / 2;
C = densite * nb_clauses_total;
printf ("\n nbre de clauses total : %d", nb_clauses_total);
printf ("\n nbre de clauses permises : %d\n", C);
/*calcul du nbre de tuples autorises a partir de la tightness */
/*et de la valeure du nbre total de tuples generable */
T_tot = puiss2 (D); //2 a la puissance le nbre de variables
T = T_tot * tightness;
printf ("\nnbre de tuples total: %d\n", T_tot);
printf ("nbre de tuples autorisees: %d\n", T);
/* Select C constraints. */
for (c = 0; c < C; ++c)
{
int i;
/* Choose a random number between c and PossibleCTs - 1, inclusive. */
r = c + (int) (ran2 (Seed) * (PossibleCTs - c));
/* Swap elements [c] and [r]. */
selectedCT = CTarray[r];
CTarray[r] = CTarray[c];
CTarray[c] = selectedCT;
/* Broadcast the constraint. */
variable1 = (int) (CTarray[c] >> 16);
variable2 = (int) (CTarray[c] & 0x0000FFFF);
/*contrainte entre variable1 et variable2 */
AddConstraint (variable1, variable2);
/* For each constraint, select T illegal value pairs. */
/* Initialize the NGarray. */
for (i = 0; i < (D * D); ++i)
NGarray[i] = i;
/* Select T incompatible pairs. */
//init_rel_tmp();//re-initialisation du tableau de realtions
for (i = 0; i < T; ++i)
{
/* Choose a random number between t and PossibleNGs - 1, inclusive. */
r = i + (int) (ran2 (Seed) * (PossibleNGs - i));
selectedNG = NGarray[r];
NGarray[r] = NGarray[i];
NGarray[i] = selectedNG;
/* Broadcast the nogood value pair */
valeur1 = (int) (NGarray[i] / D);
valeur2 = (int) (NGarray[i] % D);
/*ajout des valeurs compatibles à la relation en cours de construction */
AddNogood (valeur1, valeur2);
}
/*reinitialisation de la table des relations */
}
affiche_csp ();
EndCSP ();
free (CTarray);
free (NGarray);
return 1;
}
/*********************************************************************
3. This random number generator is from William H. Press, et al.,
_Numerical Recipes in C_, Second Ed. with corrections (1994),
p. 282. This excellent book is available through the
WWW at http://nr.harvard.edu/nr/bookc.html.
The specific section concerning ran2, Section 7.1, is in
http://cfatab.harvard.edu/nr/bookc/c7-1.ps
*********************************************************************/
#define IM1 2147483563
#define IM2 2147483399
#define AM (1.0/IM1)
#define IMM1 (IM1-1)
#define IA1 40014
#define IA2 40692
#define IQ1 53668
#define IQ2 52774
#define IR1 12211
#define IR2 3791
#define NTAB 32
#define NDIV (1+IMM1/NTAB)
#define EPS 1.2e-7
#define RNMX (1.0 - EPS)
/* ran2() - Return a random doubleing point value between 0.0 and
1.0 exclusive. If idum is negative, a new series starts (and
idum is made positive so that subsequent calls using an unchanged
idum will continue in the same sequence). */
double ran2 (long *idum)
{
int j;
long k;
static long idum2 = 123456789;
static long iy = 0;
static long iv[NTAB];
double temp;
if (*idum <= 0)
{ /* initialize */
if (-(*idum) < 1) /* prevent idum == 0 */
*idum = 1;
else
*idum = -(*idum); /* make idum positive */
idum2 = (*idum);
for (j = NTAB + 7; j >= 0; j--)
{ /* load the shuffle table */
k = (*idum) / IQ1;
*idum = IA1 * (*idum - k * IQ1) - k * IR1;
if (*idum < 0)
*idum += IM1;
if (j < NTAB)
iv[j] = *idum;
}
iy = iv[0];
}
k = (*idum) / IQ1;
*idum = IA1 * (*idum - k * IQ1) - k * IR1;
if (*idum < 0)
*idum += IM1;
k = idum2 / IQ2;
idum2 = IA2 * (idum2 - k * IQ2) - k * IR2;
if (idum2 < 0)
idum2 += IM2;
j = iy / NDIV;
iy = iv[j] - idum2;
iv[j] = *idum;
if (iy < 1)
iy += IMM1;
if ((temp = AM * iy) > RNMX)
return RNMX; /* avoid endpoint */
else
return temp;
}
/*********************************************************************
4. An implementation of StartCSP, AddConstraint, AddNogood, and EndCSP
which prints out the CSP, just listing incompatible value pairs.
Each constraint starts one a new line, and the id-numbers of the
variables appear before the colon. For instance, the output of
urbcsp 10 5 4 3 9999 10
begins
Instance 0
8 9: (1 1) (4 0) (0 4)
2 4: (0 3) (3 1) (4 0)
6 9: (4 1) (2 0) (0 3)
1 5: (0 3) (4 0) (0 0)
*********************************************************************/
void StartCSP (int instance)
{
printf ("\nInstance %d", instance);
}
void AddConstraint (int var1, int var2)
{
printf ("\n%3d %3d: ", var1, var2);
ajout_relation (var1, var2);
}
void AddNogood (int val1, int val2)
{
printf ("(%d %d) ", val1, val2);
ajout_valeurs_compatibles (val1, val2);
}
void ajout_valeurs_compatibles (int val1, int val2)
{
*rel[val1][val2] = VRAI;
}
void ajout_relation (int var1, int var2)
{
int i, j;
relations *r;
r = malloc (sizeof *r);
for (i = 0; i < NB_VAL; i++)
for (j = 0; j < NB_VAL; j++)
{
*r[i][j] = *rel[i][j];
}
csp->C[var1][var2] = r;
for (i = 0; i < NB_VAL; i++)
for (j = 0; j < NB_VAL; j++)
*rel[i][j] = FAUX;
}
void EndCSP (void)
{
puts ("");
}
void affiche_csp (void)
{
/*affichage du csp */
/*verifiacation: réaffichage du CSP */
int i, j, k, l;
contrainte ctr;
puts ("");
puts ("\n le nouveau affichage apres envoie de CSP génerée a la structure de données");
for (i = 0; i < NB_VAR; i++)
for (j = 0; j < NB_VAR; j++)
{
if (i != j)
{
ctr = csp->C[i][j];
if (ctr != NULL)
{
printf ("%d<->%d : ", i, j);
for (k = 0; k < NB_VAL; k++)
for (l = 0; l < NB_VAL; l++)
{
if (*ctr[k][l] == VRAI)
printf ("(%d,%d)", k, l);
}
puts ("");
}
}
}
}
int puiss2 (int n)
{
int i = 0;
int res = 1;
while (i < n)
{
res = res * 2;
i++;
}
return res;
} |
SOS aidez moi SVP
Répondre avec citation
Envoyé par boudji
Partager