Discussion :

[Patriarch24]

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 (ps : je ne demande pas de preuve pour l'algo ).

[pseudocode]

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

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 java :

Sélectionner tout - Visualiser dans une fenêtre à part

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:

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

[JeitEmgie]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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é

[pseudocode]

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.

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.

[JeitEmgie]

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…

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

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

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…

[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.

[JeitEmgie]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[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.

[pseudocode]

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.

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

[JeitEmgie]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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…

[Patriarch24]

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

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.

[pseudocode]

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.

[JeitEmgie]

FYI,

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[pseudocode]

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=[]

...

[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…

[AlGo66]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

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.