Algorithme de partition et sommes

Version imprimable

13/01/2010, 17h55
Patriarch24

Algorithme de partition et sommes

Bonjour à tous !
Voici mon problème : je dispose d'un ensemble fini d'éléments entiers non nuls. Je souhaite partitionner cet ensemble en p partitions (p variable) tel que la somme des éléments de toutes les partitions sont égales, à plus ou moins n% (n variable). On s'autorise à ne pas utiliser tous les éléments de l'ensemble initial (on parle de rejet). L'objectif est de maximiser la somme des partitions, et de diminuer les rejets.

Ex :
ensemble initial = {5,5,7,8,9,10,1,2,2} ; p = 2, n = 5%
partitions = {8,2,7,2,5}, {5,10,9,1} ; déchet = {}

autre Ex :
ensemble initial = {35,11,5,6} ; p = 2, n = 5%
partitions = {11}, {6,5} ; déchet = {35}

J'ai bien commencé à chercher, mais je n'arrive pas à trouver un algorithme correct. Quelques pistes seraient les bienvenues :mrgreen: (ps : je ne demande pas de preuve pour l'algo :zoubi:).

A première vue, ca ne m'a pas l'air évident comme problème. :koi:

Les tailles des ensembles et les valeurs p, n sont de quel ordre ?

Parce que si c'est assez petit, on peut faire une exploration totale des possibilités ( = (p+1)^taille(Ensemble) )

Code:

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
public static void main(String[] args) {
	int[] E = {5,5,7,8,9,10,1,2,2};
	int p = 2;
	double n=0.05;
 
	// meilleur résultat trouvé
	int bestsum=0, bestreject=E.length;
 
	// table d'assignation d'un élément aux Sets
	int[] assign = new int[E.length];
 
	// somme des Sets
	int[] sum = new int[p];
 
	while(true) {
 
		// nouvelle assignation des elements aux Sets (= compteur en base p+1)
		int k=0;
		while( k<E.length && assign[k]==p  ) assign[k++]=0;
		if (k>=E.length) break;
		assign[k]++;
 
		// calcul la somme dans chaque Set
		int rejectcount=0;
		for(int i=0;i<p;i++) sum[i]=0;
		for(int i=0;i<E.length;i++)
			if (assign[i]<p) sum[assign[i]]+=E[i];
			else rejectcount++;
 
		// Test de la tolerance sur les sommes 
		double min=sum[0], max=min;
		for(int i=1;i<p;i++) {
			if (sum[i]<min) min=sum[i];
			if (sum[i]>max) max=sum[i];
		}
		double tolerance = (max!=0) ? (max-min)/max : 0;
		if (tolerance>n) continue;
 
		// Conserve le meilleur résultat
		if (rejectcount>bestreject) continue;
		if (min<bestsum) continue;
		if (rejectcount==bestreject && min==bestsum) continue;
 
		// On a un nouveau gagnant
		bestreject=rejectcount;
		bestsum = (int)min;
 
		// affichage
		print(E,p,assign,sum);
	}
}
 
public static void print(int[] E, int p, int[] assign, int[] sum) {
	List[] Sets = new List[p];
	for(int i=0;i<p;i++) Sets[i] = new ArrayList();
	List Reject = new ArrayList();
	for(int i=0;i<E.length;i++)
		if (assign[i]<p) Sets[assign[i]].add(E[i]); else Reject.add(E[i]);
 
	for(int i=0;i<p;i++)
		System.out.printf("%s=%s , ", Arrays.toString(Sets[i].toArray()), sum[i]);
	System.out.printf("rejet=%s\n",Arrays.toString(Reject.toArray()));
}

Résultat du programme:

Citation:

[9, 10, 1, 2, 2]=24 , [5, 5, 7, 8]=25 , rejet=[]

l'exploration de toutes les possibilités explose hélas très vite :

pour E = {5,5,7,8,9,10,1,2,2}
Code:

1 2 3 4 5 6 7 time java Partition [9, 10, 1, 2, 2]=24 , [5, 5, 7, 8]=25 , rejet=[] real 0m0.163s user 0m0.115s sys 0m0.033s
pour E = {5,5,7,8,9,10,1,2,2,5,5,7,8,9,10,1,2,2}
Code:

1 2 3 4 5 6 7 8 time java Partition [1, 5, 5, 7, 8, 9, 10, 1, 2, 2]=50 , [5, 5, 7, 8, 9, 10, 2, 2]=48 , rejet=[] [5, 5, 7, 8, 9, 10, 1, 2, 2]=49 , [5, 5, 7, 8, 9, 10, 1, 2, 2]=49 , rejet=[] real 1m4.928s user 1m4.876s sys 0m0.045s
peut-être une stratégie visant à augmenter une solution petit à petit :

trier E
P bags vides : Bag[1..P]

prendre les P plus grands éléments de E
et en ajouter 1 à chaque bag en les distribuant par ordre croissant de Somme(Bag[i])
autrement dit mettre le plus grand dans le bag le moins "lourd" (rééquilibrage)
(et au premier tour, les bags sont vides…)

si il existe un Bag i telle que la somme des éléments restant de E + S(Bi) < max(S(Bi)) :
solution impossible : backtrack en enlevant le plus grand élément parmi ceux que l'on vient de placer
(autrement dit si le bag le plus léger ne peut pas rattraper le plus lourd en mettant ce qui reste : pas de solution)

s'il ne reste plus d'éléments de E à placer : condition de fin
vérifier la plus grande différence des S(Bi) par rapport à la tolérance
soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

sinon E étant maintenant E \ {les P éléments qu'on vient de placer} on "itère" à nouveau

si E contient des entiers négatifs il faudra modifier le test de la solution impossible,
car il faut examiner la possibilité de ré-équilibrage en donnant du "négatif" au bag trop chargé

15/01/2010, 17h06
pseudocode

Citation:

Envoyé par JeitEmgie

l'exploration de toutes les possibilités explose hélas très vite

Oui, ca explose très vite. D'où ma question sur le dimensionnement du problème.

Il faut dire aussi que j'ai codé ca rapidement, donc on peut sans doute optimiser deux ou trois choses. :aie:

Citation:

peut-être une stratégie visant à augmenter une solution petit à petit

Je ne sais pas si on peut trouver une heuristique qui nous garantisse de trouver la (une) solution optimale. Mais ca mérite d'y réfléchir.
15/01/2010, 21h18
JeitEmgie

Citation:

Envoyé par pseudocode

Oui, ca explose très vite. D'où ma question sur le dimensionnement du problème.

vu la vitesse à laquelle cela explose… on risque d'être à plus d'une heure pour quelques dizaines d'entiers dans E…

Citation:

Envoyé par pseudocode

Il faut dire aussi que j'ai codé ca rapidement, donc on peut sans doute optimiser deux ou trois choses. :aie:

un test pour détecter vite qu'on ne peut plus rien trouver… sans doute en travaillant sur un E trié pour le faciliter…

Citation:

Envoyé par pseudocode

Je ne sais pas si on peut trouver une heuristique qui nous garantisse de trouver la (une) solution optimale. Mais ca mérite d'y réfléchir.

un premier essai incomplet (ne s'occupe pas de la précision…) de ce que j'expliquais plus haut fonctionne…
mais pour trouver la solution "optimale" (ou toutes les solutions) çà va consommer pas mal de mémoire sur de grands E… (pour le backtracking…) on risque donc d'avoir un autre genre d'explosion… ;)
17/01/2010, 13h16
10_GOTO_10

C'est une variante du problème du sac à dos: pour un nombre p de partitions, il s'agit de trouver le meilleur remplissage de la partition de taille = somme totale / p (le sac à dos). Déjà là, c'est un problème NP complet. Et en plus, il faut réitérer pour les nombres restants, puis pour tous les p possibles (ou du moins les plus probables). Bon courage.

exemples de résultats obtenus sur base de l'idée décrire plus haut
çà ne trouve pas toutes les solutions mais au moins çà en trouve un dans une temps raisonnable…
(et cela ne s'occupe pas encore de la précision, çà indique juste celle du résultat…)

Code:

1
2
3
4
5
6
7
8
9
10
11
 
5 partitions out of { 1, 2, 3, 7, 20, 11, 15, 36, 18, 23, 16, 17, 19, 2, 5, 5, 7, 8, 9, 10, 1, 2, 2, 5, 5, 7, 8, 9, 10,  }
56 [ 36, 8, 7, 3, 2,  ]
56 [ 23, 11, 10, 8, 2, 2,  ]
57 [ 18, 17, 10, 5, 5, 2,  ]
57 [ 19, 16, 9, 7, 5, 1,  ]
57 [ 20, 15, 9, 7, 5, 1,  ]
solution at 1.75 %
real	0m0.164s
user	0m0.117s
sys	0m0.034s

Code:

1
2
3
4
5
6
 
3 partitions out of { 1, 2, 2, 5, 5, 7, 8, 9, 10,  }
16 [ 9, 5, 2,  ]
16 [ 10, 5, 1,  ]
17 [ 8, 7, 2,  ]
solution at 5.88 %

Code:

1
2
3
4
5
 
2 partitions out of { 1, 2, 2, 5, 5, 7, 8, 9, 10,  }
24 [ 10, 7, 5, 2,  ]
25 [ 9, 8, 5, 2, 1,  ]
solution at 3.99 %

Code:

1
2
3
4
5
 
2 partitions out of { 5, 6, 11, 35,  }
11 [ 6, 5,  ]
11 [ 11,  ]
-- rejected:	35,

Code:

1
2
3
4
 
2 partitions out of { 1, 2, 2, 5, 5, 7, 8, 9, 10, 1, 2, 2, 5, 5, 7, 8, 9, 10,  }
49 [ 10, 9, 8, 7, 5, 5, 2, 2, 1,  ]
49 [ 10, 9, 8, 7, 5, 5, 2, 2, 1,  ]

Code:

1
2
3
4
5
6
 
3 partitions out of { 1, 2, 2, 5, 5, 7, 8, 9, 10, 1, 2, 2, 5, 5, 7, 8, 9, 10,  }
32 [ 10, 8, 5, 5, 2, 2,  ]
33 [ 9, 9, 7, 5, 2, 1,  ]
33 [ 10, 8, 7, 5, 2, 1,  ]
solution at 3.03 %

Code:

1
2
3
4
5
6
7
8
9
10
11
 
5 partitions out of { 5, 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,  }
1011 [ 100, 91, 86, 85, 80, 71, 66, 65, 60, 51, 46, 45, 40, 31, 26, 25, 20, 11, 6, 5, 1,  ]
1011 [ 99, 92, 87, 84, 79, 72, 67, 64, 59, 52, 47, 44, 39, 32, 27, 24, 19, 12, 7, 5,  ]
1011 [ 98, 93, 88, 83, 78, 73, 68, 63, 58, 53, 48, 43, 38, 33, 28, 23, 18, 13, 8, 4,  ]
1011 [ 97, 94, 89, 82, 77, 74, 69, 62, 57, 54, 49, 42, 37, 34, 29, 22, 17, 14, 9, 3,  ]
1011 [ 96, 95, 90, 81, 76, 75, 70, 61, 56, 55, 50, 41, 36, 35, 30, 21, 16, 15, 10, 2,  ]
 
real	0m0.214s
user	0m0.149s
sys	0m0.039s

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
7 partitions out of { 1, 2, 3, 4, (... integers from 1 to 100… ), 98, 99, 100,  }
721 [ 96, 91, 84, 75, 68, 63, 56, 47, 40, 35, 28, 19, 12, 7,  ]
721 [ 97, 90, 83, 76, 69, 62, 55, 48, 41, 34, 27, 20, 13, 6,  ]
721 [ 98, 89, 82, 77, 70, 61, 54, 49, 42, 33, 26, 21, 14, 5,  ]
721 [ 99, 88, 81, 78, 71, 60, 53, 50, 43, 32, 25, 22, 15, 4,  ]
721 [ 100, 87, 80, 79, 72, 59, 52, 51, 44, 31, 24, 23, 16, 3,  ]
722 [ 95, 92, 85, 74, 67, 64, 57, 46, 39, 36, 29, 18, 11, 8, 1,  ]
723 [ 94, 93, 86, 73, 66, 65, 58, 45, 38, 37, 30, 17, 10, 9, 2,  ]
solution at 0.27 %
 
real	0m0.213s
user	0m0.138s
sys	0m0.036s

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
7 partitions out of { 1, 2, 3, (... integers from 1 to 1000…) , 997, 998, 999, 1000,  }
71497 [ 1000, 987, 980, 979, 972, 959, 952, 951, 944, 931, 924, 923, 916, 903, 896, 895, 888, 875, 868, 867, 860, 847, 840, 839, 832, 819, 812, 811, 804, 791, 784, 783, 776, 763, 756, 755, 748, 735, 728, 727, 720, 707, 700, 699, 692, 679, 672, 671, 664, 651, 644, 643, 636, 623, 616, 615, 608, 595, 588, 587, 580, 567, 560, 559, 552, 539, 532, 531, 524, 511, 504, 503, 496, 483, 476, 475, 468, 455, 448, 447, 440, 427, 420, 419, 412, 399, 392, 391, 384, 371, 364, 363, 356, 343, 336, 335, 328, 315, 308, 307, 300, 287, 280, 279, 272, 259, 252, 251, 244, 231, 224, 223, 216, 203, 196, 195, 188, 175, 168, 167, 160, 147, 140, 139, 132, 119, 112, 111, 104, 91, 84, 83, 76, 63, 56, 55, 48, 35, 28, 27, 20, 7,  ]
71498 [ 999, 988, 981, 978, 971, 960, 953, 950, 943, 932, 925, 922, 915, 904, 897, 894, 887, 876, 869, 866, 859, 848, 841, 838, 831, 820, 813, 810, 803, 792, 785, 782, 775, 764, 757, 754, 747, 736, 729, 726, 719, 708, 701, 698, 691, 680, 673, 670, 663, 652, 645, 642, 635, 624, 617, 614, 607, 596, 589, 586, 579, 568, 561, 558, 551, 540, 533, 530, 523, 512, 505, 502, 495, 484, 477, 474, 467, 456, 449, 446, 439, 428, 421, 418, 411, 400, 393, 390, 383, 372, 365, 362, 355, 344, 337, 334, 327, 316, 309, 306, 299, 288, 281, 278, 271, 260, 253, 250, 243, 232, 225, 222, 215, 204, 197, 194, 187, 176, 169, 166, 159, 148, 141, 138, 131, 120, 113, 110, 103, 92, 85, 82, 75, 64, 57, 54, 47, 36, 29, 26, 19, 8, 1,  ]
71499 [ 998, 989, 982, 977, 970, 961, 954, 949, 942, 933, 926, 921, 914, 905, 898, 893, 886, 877, 870, 865, 858, 849, 842, 837, 830, 821, 814, 809, 802, 793, 786, 781, 774, 765, 758, 753, 746, 737, 730, 725, 718, 709, 702, 697, 690, 681, 674, 669, 662, 653, 646, 641, 634, 625, 618, 613, 606, 597, 590, 585, 578, 569, 562, 557, 550, 541, 534, 529, 522, 513, 506, 501, 494, 485, 478, 473, 466, 457, 450, 445, 438, 429, 422, 417, 410, 401, 394, 389, 382, 373, 366, 361, 354, 345, 338, 333, 326, 317, 310, 305, 298, 289, 282, 277, 270, 261, 254, 249, 242, 233, 226, 221, 214, 205, 198, 193, 186, 177, 170, 165, 158, 149, 142, 137, 130, 121, 114, 109, 102, 93, 86, 81, 74, 65, 58, 53, 46, 37, 30, 25, 18, 9, 2,  ]
71500 [ 997, 990, 983, 976, 969, 962, 955, 948, 941, 934, 927, 920, 913, 906, 899, 892, 885, 878, 871, 864, 857, 850, 843, 836, 829, 822, 815, 808, 801, 794, 787, 780, 773, 766, 759, 752, 745, 738, 731, 724, 717, 710, 703, 696, 689, 682, 675, 668, 661, 654, 647, 640, 633, 626, 619, 612, 605, 598, 591, 584, 577, 570, 563, 556, 549, 542, 535, 528, 521, 514, 507, 500, 493, 486, 479, 472, 465, 458, 451, 444, 437, 430, 423, 416, 409, 402, 395, 388, 381, 374, 367, 360, 353, 346, 339, 332, 325, 318, 311, 304, 297, 290, 283, 276, 269, 262, 255, 248, 241, 234, 227, 220, 213, 206, 199, 192, 185, 178, 171, 164, 157, 150, 143, 136, 129, 122, 115, 108, 101, 94, 87, 80, 73, 66, 59, 52, 45, 38, 31, 24, 17, 10, 3,  ]
71501 [ 996, 991, 984, 975, 968, 963, 956, 947, 940, 935, 928, 919, 912, 907, 900, 891, 884, 879, 872, 863, 856, 851, 844, 835, 828, 823, 816, 807, 800, 795, 788, 779, 772, 767, 760, 751, 744, 739, 732, 723, 716, 711, 704, 695, 688, 683, 676, 667, 660, 655, 648, 639, 632, 627, 620, 611, 604, 599, 592, 583, 576, 571, 564, 555, 548, 543, 536, 527, 520, 515, 508, 499, 492, 487, 480, 471, 464, 459, 452, 443, 436, 431, 424, 415, 408, 403, 396, 387, 380, 375, 368, 359, 352, 347, 340, 331, 324, 319, 312, 303, 296, 291, 284, 275, 268, 263, 256, 247, 240, 235, 228, 219, 212, 207, 200, 191, 184, 179, 172, 163, 156, 151, 144, 135, 128, 123, 116, 107, 100, 95, 88, 79, 72, 67, 60, 51, 44, 39, 32, 23, 16, 11, 4,  ]
71502 [ 995, 992, 985, 974, 967, 964, 957, 946, 939, 936, 929, 918, 911, 908, 901, 890, 883, 880, 873, 862, 855, 852, 845, 834, 827, 824, 817, 806, 799, 796, 789, 778, 771, 768, 761, 750, 743, 740, 733, 722, 715, 712, 705, 694, 687, 684, 677, 666, 659, 656, 649, 638, 631, 628, 621, 610, 603, 600, 593, 582, 575, 572, 565, 554, 547, 544, 537, 526, 519, 516, 509, 498, 491, 488, 481, 470, 463, 460, 453, 442, 435, 432, 425, 414, 407, 404, 397, 386, 379, 376, 369, 358, 351, 348, 341, 330, 323, 320, 313, 302, 295, 292, 285, 274, 267, 264, 257, 246, 239, 236, 229, 218, 211, 208, 201, 190, 183, 180, 173, 162, 155, 152, 145, 134, 127, 124, 117, 106, 99, 96, 89, 78, 71, 68, 61, 50, 43, 40, 33, 22, 15, 12, 5,  ]
71503 [ 994, 993, 986, 973, 966, 965, 958, 945, 938, 937, 930, 917, 910, 909, 902, 889, 882, 881, 874, 861, 854, 853, 846, 833, 826, 825, 818, 805, 798, 797, 790, 777, 770, 769, 762, 749, 742, 741, 734, 721, 714, 713, 706, 693, 686, 685, 678, 665, 658, 657, 650, 637, 630, 629, 622, 609, 602, 601, 594, 581, 574, 573, 566, 553, 546, 545, 538, 525, 518, 517, 510, 497, 490, 489, 482, 469, 462, 461, 454, 441, 434, 433, 426, 413, 406, 405, 398, 385, 378, 377, 370, 357, 350, 349, 342, 329, 322, 321, 314, 301, 294, 293, 286, 273, 266, 265, 258, 245, 238, 237, 230, 217, 210, 209, 202, 189, 182, 181, 174, 161, 154, 153, 146, 133, 126, 125, 118, 105, 98, 97, 90, 77, 70, 69, 62, 49, 42, 41, 34, 21, 14, 13, 6,  ]
	near good solution at 0.0 %
 
real	0m0.564s
user	0m0.367s
sys	0m0.156s

Code:

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
 
37 partitions out of { 1, 2, 3, (... integers from 1 to 1000…) , 997, 998, 999, 1000,  }
13508 [ 1000, 927, 890, 889, 852, 779, 742, 741, 704, 631, 594, 593, 556, 483, 446, 445, 408, 335, 298, 297, 260, 187, 150, 149, 112, 39, 1,  ]
13509 [ 999, 928, 891, 888, 851, 780, 743, 740, 703, 632, 595, 592, 555, 484, 447, 444, 407, 336, 299, 296, 259, 188, 151, 148, 111, 40, 2,  ]
13510 [ 998, 929, 892, 887, 850, 781, 744, 739, 702, 633, 596, 591, 554, 485, 448, 443, 406, 337, 300, 295, 258, 189, 152, 147, 110, 41, 3,  ]
13511 [ 997, 930, 893, 886, 849, 782, 745, 738, 701, 634, 597, 590, 553, 486, 449, 442, 405, 338, 301, 294, 257, 190, 153, 146, 109, 42, 4,  ]
13512 [ 996, 931, 894, 885, 848, 783, 746, 737, 700, 635, 598, 589, 552, 487, 450, 441, 404, 339, 302, 293, 256, 191, 154, 145, 108, 43, 5,  ]
13513 [ 995, 932, 895, 884, 847, 784, 747, 736, 699, 636, 599, 588, 551, 488, 451, 440, 403, 340, 303, 292, 255, 192, 155, 144, 107, 44, 6,  ]
13514 [ 994, 933, 896, 883, 846, 785, 748, 735, 698, 637, 600, 587, 550, 489, 452, 439, 402, 341, 304, 291, 254, 193, 156, 143, 106, 45, 7,  ]
13515 [ 993, 934, 897, 882, 845, 786, 749, 734, 697, 638, 601, 586, 549, 490, 453, 438, 401, 342, 305, 290, 253, 194, 157, 142, 105, 46, 8,  ]
13516 [ 992, 935, 898, 881, 844, 787, 750, 733, 696, 639, 602, 585, 548, 491, 454, 437, 400, 343, 306, 289, 252, 195, 158, 141, 104, 47, 9,  ]
13517 [ 991, 936, 899, 880, 843, 788, 751, 732, 695, 640, 603, 584, 547, 492, 455, 436, 399, 344, 307, 288, 251, 196, 159, 140, 103, 48, 10,  ]
13518 [ 990, 937, 900, 879, 842, 789, 752, 731, 694, 641, 604, 583, 546, 493, 456, 435, 398, 345, 308, 287, 250, 197, 160, 139, 102, 49, 11,  ]
13519 [ 989, 938, 901, 878, 841, 790, 753, 730, 693, 642, 605, 582, 545, 494, 457, 434, 397, 346, 309, 286, 249, 198, 161, 138, 101, 50, 12,  ]
13520 [ 988, 939, 902, 877, 840, 791, 754, 729, 692, 643, 606, 581, 544, 495, 458, 433, 396, 347, 310, 285, 248, 199, 162, 137, 100, 51, 13,  ]
13521 [ 987, 940, 903, 876, 839, 792, 755, 728, 691, 644, 607, 580, 543, 496, 459, 432, 395, 348, 311, 284, 247, 200, 163, 136, 99, 52, 14,  ]
13522 [ 986, 941, 904, 875, 838, 793, 756, 727, 690, 645, 608, 579, 542, 497, 460, 431, 394, 349, 312, 283, 246, 201, 164, 135, 98, 53, 15,  ]
13523 [ 985, 942, 905, 874, 837, 794, 757, 726, 689, 646, 609, 578, 541, 498, 461, 430, 393, 350, 313, 282, 245, 202, 165, 134, 97, 54, 16,  ]
13524 [ 984, 943, 906, 873, 836, 795, 758, 725, 688, 647, 610, 577, 540, 499, 462, 429, 392, 351, 314, 281, 244, 203, 166, 133, 96, 55, 17,  ]
13525 [ 983, 944, 907, 872, 835, 796, 759, 724, 687, 648, 611, 576, 539, 500, 463, 428, 391, 352, 315, 280, 243, 204, 167, 132, 95, 56, 18,  ]
13526 [ 982, 945, 908, 871, 834, 797, 760, 723, 686, 649, 612, 575, 538, 501, 464, 427, 390, 353, 316, 279, 242, 205, 168, 131, 94, 57, 19,  ]
13527 [ 981, 946, 909, 870, 833, 798, 761, 722, 685, 650, 613, 574, 537, 502, 465, 426, 389, 354, 317, 278, 241, 206, 169, 130, 93, 58, 20,  ]
13528 [ 980, 947, 910, 869, 832, 799, 762, 721, 684, 651, 614, 573, 536, 503, 466, 425, 388, 355, 318, 277, 240, 207, 170, 129, 92, 59, 21,  ]
13529 [ 979, 948, 911, 868, 831, 800, 763, 720, 683, 652, 615, 572, 535, 504, 467, 424, 387, 356, 319, 276, 239, 208, 171, 128, 91, 60, 22,  ]
13530 [ 978, 949, 912, 867, 830, 801, 764, 719, 682, 653, 616, 571, 534, 505, 468, 423, 386, 357, 320, 275, 238, 209, 172, 127, 90, 61, 23,  ]
13531 [ 977, 950, 913, 866, 829, 802, 765, 718, 681, 654, 617, 570, 533, 506, 469, 422, 385, 358, 321, 274, 237, 210, 173, 126, 89, 62, 24,  ]
13532 [ 976, 951, 914, 865, 828, 803, 766, 717, 680, 655, 618, 569, 532, 507, 470, 421, 384, 359, 322, 273, 236, 211, 174, 125, 88, 63, 25,  ]
13533 [ 975, 952, 915, 864, 827, 804, 767, 716, 679, 656, 619, 568, 531, 508, 471, 420, 383, 360, 323, 272, 235, 212, 175, 124, 87, 64, 26,  ]
13534 [ 974, 953, 916, 863, 826, 805, 768, 715, 678, 657, 620, 567, 530, 509, 472, 419, 382, 361, 324, 271, 234, 213, 176, 123, 86, 65, 27,  ]
13535 [ 973, 954, 917, 862, 825, 806, 769, 714, 677, 658, 621, 566, 529, 510, 473, 418, 381, 362, 325, 270, 233, 214, 177, 122, 85, 66, 28,  ]
13536 [ 972, 955, 918, 861, 824, 807, 770, 713, 676, 659, 622, 565, 528, 511, 474, 417, 380, 363, 326, 269, 232, 215, 178, 121, 84, 67, 29,  ]
13537 [ 971, 956, 919, 860, 823, 808, 771, 712, 675, 660, 623, 564, 527, 512, 475, 416, 379, 364, 327, 268, 231, 216, 179, 120, 83, 68, 30,  ]
13538 [ 970, 957, 920, 859, 822, 809, 772, 711, 674, 661, 624, 563, 526, 513, 476, 415, 378, 365, 328, 267, 230, 217, 180, 119, 82, 69, 31,  ]
13539 [ 969, 958, 921, 858, 821, 810, 773, 710, 673, 662, 625, 562, 525, 514, 477, 414, 377, 366, 329, 266, 229, 218, 181, 118, 81, 70, 32,  ]
13540 [ 968, 959, 922, 857, 820, 811, 774, 709, 672, 663, 626, 561, 524, 515, 478, 413, 376, 367, 330, 265, 228, 219, 182, 117, 80, 71, 33,  ]
13541 [ 967, 960, 923, 856, 819, 812, 775, 708, 671, 664, 627, 560, 523, 516, 479, 412, 375, 368, 331, 264, 227, 220, 183, 116, 79, 72, 34,  ]
13542 [ 966, 961, 924, 855, 818, 813, 776, 707, 670, 665, 628, 559, 522, 517, 480, 411, 374, 369, 332, 263, 226, 221, 184, 115, 78, 73, 35,  ]
13543 [ 965, 962, 925, 854, 817, 814, 777, 706, 669, 666, 629, 558, 521, 518, 481, 410, 373, 370, 333, 262, 225, 222, 185, 114, 77, 74, 36,  ]
13544 [ 964, 963, 926, 853, 816, 815, 778, 705, 668, 667, 630, 557, 520, 519, 482, 409, 372, 371, 334, 261, 224, 223, 186, 113, 76, 75, 37,  ]
solution at 0.26 %
-- rejected:	38, 
 
real	0m0.313s
user	0m0.217s
sys	0m0.070s

Code:

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
 
37 partitions out of { 1, 11, 21, 31, 41, 51, 62, 72, 82, 92, 102, 112, 122, 132, 142, 152, 162, 173, 183, 193, 203, 213, 223, 233, 243, 253, 263, 273, 284, 294, 304, 314, 324, 334, 344, 354, 364, 374, 384, 395, 405, 415, 425, 435, 445, 455, 465, 475, 485, 495, 506, 516, 526, 536, 546, 556, 566, 576, 586, 596, 606, 617, 627, 637, 647, 657, 667, 677, 687, 697, 707, 717, 728, 738, 748, 758, 768, 778, 788, 798, 808, 818, 828, 839, 849, 859, 869, 879, 889, 899, 909, 919, 929, 939, 950, 960, 970, 980, 990, 1000,  }
1263 [ 667, 596,  ]
1263 [ 677, 586,  ]
1263 [ 687, 576,  ]
1263 [ 697, 566,  ]
1263 [ 707, 556,  ]
1263 [ 717, 546,  ]
1263 [ 768, 495,  ]
1263 [ 778, 485,  ]
1263 [ 788, 475,  ]
1263 [ 798, 465,  ]
1263 [ 808, 455,  ]
1263 [ 818, 445,  ]
1263 [ 828, 435,  ]
1263 [ 879, 384,  ]
1263 [ 889, 374,  ]
1263 [ 899, 364,  ]
1263 [ 909, 354,  ]
1263 [ 919, 344,  ]
1263 [ 929, 334,  ]
1263 [ 939, 324,  ]
1263 [ 990, 273,  ]
1263 [ 1000, 263,  ]
1264 [ 657, 606, 1,  ]
1264 [ 637, 627,  ]
1264 [ 647, 617,  ]
1264 [ 728, 536,  ]
1264 [ 738, 526,  ]
1264 [ 748, 516,  ]
1264 [ 758, 506,  ]
1264 [ 839, 425,  ]
1264 [ 849, 415,  ]
1264 [ 859, 405,  ]
1264 [ 869, 395,  ]
1264 [ 950, 314,  ]
1264 [ 960, 304,  ]
1264 [ 970, 294,  ]
1264 [ 980, 284,  ]
solution at 0.07 %
-- rejected:	253, 243, 233, 223, 213, 203, 193, 183, 173, 162, 152, 142, 132, 122, 112, 102, 92, 82, 72, 62, 51, 41, 31, 21, 11,
 
real	0m0.264s
user	0m0.126s
sys	0m0.038s

18/01/2010, 09h35
Patriarch24

Me revoilà ! Merci pour vos réponses.
Je précise un peu le problème, même si en effet, il est NP-complet donc je n'aurai jamais d'algorithme polynomial et déterministe.
p est compris entre 2 et 8 (au-delà je n'en ai pas l'utilité) et est fixé (donnée du problème), quant aux entiers dans l'ensemble de départ, ils sont positifs non-nuls et généralement compris entre 1 et 200 (avec une densité plus forte entre 20 et 50, et très faible au-delà de 100). Enfin, card(E) varie entre 1 et 5000 environ (mais on peut découper le problème en sous-ensembles de 50 par exemple.
Pour donner un peu de vie au problème, il s'agit en fait de composer des piles de feuilles de livres à imprimer sur des planches de papier.
18/01/2010, 09h47
pseudocode

Citation:

Envoyé par Patriarch24

Pour donner un peu de vie au problème, il s'agit en fait de composer des piles de feuilles de livres à imprimer sur des planches de papier.

:koi: ? Tu peux expliquer un peu plus le problème, parce que je ne vois pas trop le rapport avec ton premier post.

Alors le principe que je vous ait expliqué plus haut fonctionne bien…
vous n'avez besoin que d'une solution pourvu qu'elle soit suffisamment bonne…

génération d'un fichier test correspondant grosso modo à votre description (#E=5000) :
Code:

1 2 3 4 5 jot 480 1 20 >> e9.txt jot 4000 21 50 >> e9.txt jot 500 51 100 >> e9.txt jot 20 101 200 >> e9.txt
en faisant varier p de 2 à 8 :
Code:

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 p=2 real 0m23.640s user 0m18.264s sys 0m5.339s 2 bags de poids 93900 p=3 real 0m14.688s user 0m11.130s sys 0m3.521s 3 bags de poids 62600 p=4 real 0m11.104s user 0m8.356s sys 0m2.680s 4 bags de poids 46950 p=5 real 0m9.018s user 0m6.786s sys 0m2.188s 5 bags de poids 37560 p=6 real 0m7.519s user 0m5.696s sys 0m1.800s 6 bags de poids 31300 p=7 real 0m6.468s user 0m4.904s sys 0m1.559s 3 de 26828 et 4 de 26829 p=8 real 0m5.767s user 0m4.372s sys 0m1.362s 8 bags de poids 23475
au total 1 minute pour avoir les possibilités pour p de 2 à 8, vu l'objectif d'utilisation, me semble suffisamment rapide…

19/01/2010, 08h37
Patriarch24

Citation:

Tu peux expliquer un peu plus le problème, parce que je ne vois pas trop le rapport avec ton premier post.

En fait, j'ai un ensemble de livres à imprimer, avec un nombre de pages différents (le cas du même nombre de pages ne pose évidemment aucun problème !). Pour éviter la gâche papier, on compose sur une même feuille les pages de différents livres. Bien entendu, il faut que les piles de feuilles ainsi constituées ne soient pas trop déséquilibrées, sinon on gâche de nouveau du papier.
Ainsi, le nombre de partitions demandées est le nombre de pages qu'on compose sur une feuille, les entiers correspondant au nombre de pages de chaque livre.

J'espère avoir été assez clair :mrgreen:

Merci à JeitEmgie pour sa solution : je vais la tester. En fait j'avais une solution qui s'arrête lorsqu'on atteint l'objectif "tous les tas ont la même taille à n% près", ce qui est embêtant de mon point de vue (mieux vaut remplir au maximum les partitions).

Et merci à tous pour vos aides précieuses.
19/01/2010, 10h00
pseudocode

Citation:

Envoyé par Patriarch24

En fait, j'ai un ensemble de livres à imprimer, avec un nombre de pages différents (le cas du même nombre de pages ne pose évidemment aucun problème !). Pour éviter la gâche papier, on compose sur une même feuille les pages de différents livres. Bien entendu, il faut que les piles de feuilles ainsi constituées ne soient pas trop déséquilibrées, sinon on gâche de nouveau du papier.

Ok. Etant donné le nombre d'éléments dans ton ensemble, l'exploration complete est hors de question. Il faut donc recourir à des heuristiques.

L'heuristique "glouton" proposée par JeitEmgie te donneras une solution quasi-optimale à ton problème. Vue la taille de l'ensemble et la répartition des valeurs, il y a peu de chance de tomber sur un cas tordu (= système non canonique genre E={5,4,3,3,3} p=2 ). Au pire, comme l'algo est rapide, il suffit de le relancer en plusieurs fois en ajoutant un peu de "hasard" dans le processus de répartition.
19/01/2010, 10h35
JeitEmgie
FYI,
Code:

1 2 3 4 5 6 7 8 2 partitions out of { 5, 4, 3, 3, 3, } -- done -- 7 [ 4, 3, ] 8 [ 5, 3, ] solution at 12.5 % -- rejected: 3, -- end --
le hasard n'apportera rien sans modifier l'algorithme au point qu'on doive parler d'un autre algorithme : il est basé sur le fait que les données (E) soient triées au départ par ordre décroissant et que les bags soient triés à chaque itération par ordre croissant de poids.
19/01/2010, 10h52
pseudocode

Citation:

Envoyé par JeitEmgie

le hasard n'apportera rien sans modifier l'algorithme au point qu'on doive parler d'un autre algorithme : il est basé sur le fait que les données (E) soient triées au départ par ordre décroissant et que les bags soient triés à chaque itération par ordre croissant de poids.

Tu peux mettre une pointe de hasard lors de l'affectation du Bag dans une partition. Au lieu de toujours mettre le Bag dans la partition la plus légère, tu le mets avec une probabilité de 90 %.

E = { 5, 4, 3, 3, 3, }
P1=[] P2=[]

Step 1
- mettre "5" dans P1(50%) ou P2(50%) --> P1=[5] P2=[]

Step 2
- mettre "4" dans P1(10%) ou P2(90%) --> P1=[5] P2=[]

...
19/01/2010, 12h45
JeitEmgie

j'ai très bien compris l'idée…

mais entre la description générale donnée plus haut et l'implémentation, il y a quand même des subtilités non décrites qui ne fonctionneront plus de la même manière si l'on ajoute cette notion de probabilité… et on aura donc un autre algorithme…

par contre, au vu de la réalité physique sous-jacente, on pourrait aussi imaginer couper en 2 les éléments de E "trop lourds" : çàd (en gros, car là aussi il y aune subtilité qui se cache…) tels que leur poids est supérieur à la somme des poids de tous les autres… (le cas du 35 ci-dessus…) et ceci à chaque itération…
ou beaucoup plus simple : répartir le poids des rejetés dans les bags existants à la fin des itérations…
09/04/2011, 19h08
AlGo66
Citation:

Envoyé par JeitEmgie

peut-être une stratégie visant à augmenter une solution petit à petit :

trier E
P bags vides : Bag[1..P]

prendre les P plus grands éléments de E
et en ajouter 1 à chaque bag en les distribuant par ordre croissant de Somme(Bag[i])
autrement dit mettre le plus grand dans le bag le moins "lourd" (rééquilibrage)
(et au premier tour, les bags sont vides…)

si il existe un Bag i telle que la somme des éléments restant de E + S(Bi) < max(S(Bi)) :
solution impossible : backtrack en enlevant le plus grand élément parmi ceux que l'on vient de placer
(autrement dit si le bag le plus léger ne peut pas rattraper le plus lourd en mettant ce qui reste : pas de solution)

s'il ne reste plus d'éléments de E à placer : condition de fin
vérifier la plus grande différence des S(Bi) par rapport à la tolérance
soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

sinon E étant maintenant E \ {les P éléments qu'on vient de placer} on "itère" à nouveau

si E contient des entiers négatifs il faudra modifier le test de la solution impossible,
car il faut examiner la possibilité de ré-équilibrage en donnant du "négatif" au bag trop chargé

J'ai un problème similaire, je dois répartir 24 entiers en 6 groupes de 4 éléments, la somme de chaque groupe devant être le plus proche possible.

Je cherche la "meilleure" solution mais les (environ)10 meilleurs solutions m'intéressent. En effet la valeur des éléments résultant d'une fonction d'évaluation contenant plus de 10 paramètres, cette fonction d'évaluation comporte une part de subjectivité. En ce sens je ne peux pas affirmer que l'élément 1192 est toujours meilleur que le 1191, par contre il est clair que 1897 est de l'ordre de 3 fois meilleur que 622.

Mon but est de proposer a des utilisateurs des lots de groupes équilibrés et qu'ils choisissent celui qui leur convient le mieux en fonction d'autres paramètres personnels et subjectifs. Pour l'instant ma meilleur solution donne un écart de 72.

E= {1897, 1605, 1427, 1422, 1399, 1374, 1308, 1192, 1191, 1146, 1125, 1037, 1032, 1024, 982, 901, 875, 784, 770, 769, 749, 659, 622, 541 }

Je code en Java avec Eclipse. en suivant la méthode gloutonne de JeitEmgie, j'obtiens à la première itération:
Code:

1 2 3 4 5 6 1897 1605 1427 1422 1399 1374 1037 1125 1146 1191 1192 1308 784 875 1032 982 1024 901 541 659 749 769 622 770 somme des groupes: 4259 4264 4354 4364 4237 4353 écart max 127
Après, je ne comprends pas très bien la phrase :

Citation:

soit on a une solution soit il faut revenir en arrière en éliminant le plus grand élément placé à la dernière étape

dois je revenir au rang 3, enlever l'élément 1032, et recommencer à remplir les sacs avec 1024.

Quid de 1032, dois je le replacer en toute fin de la liste des éléments restants, ou bien après avoir rempli le rang 3, dois je le replacer en tête de liste.

D'une manière générale faut il faire les différents tests après le placement de chaque élément ou après avoir placer un nombre d'élément identique dans chaque bag.

Je me demande si l'algorithme glouton marche bien avec mon jeu de donnée, compte tenu du faible nombre d'éléments par rapport à la différence de valeur entre les éléments. Je suis en train d'étudier l'algorithme de différenciation de Karmarkar-Karp pour voir si j'obtiens de meilleur résultat.