pagination-problem / tree_structure

0 stars 0 forks source link

Résolution par coupe naïve #11

Open laowantong opened 4 years ago

laowantong commented 4 years ago

En 378c61b, j'ai ajouté un solveur trivial pour comparer avec le FPTAS.

Partition the tile list into the best two lists of CONSECUTIVE tiles. Due to the hierarchy constraint, the optimal solution tends to partition the tiles in such a way that most tiles of bin1 have an index lesser than that of all tiles of bin2. This simple linear search finds the “cut” i minimizing |weight(tiles[:i]) - weight(tiles[i:])|.

Les résultats sur un jeu de 20 instances aléatoires sont les suivants, avec les valeurs de C_max et leur comparaison dans les 3 dernières colonnes :

numéro nom naive cut FPTAS gain
1 h=04_t=003_s=006_m=06__S1M4.json 15 15 0,0 %
2 h=04_t=004_s=007_m=02__3LP0.json 9 9 0,0 %
3 h=04_t=006_s=010_m=01__PCM6.json 6 6 0,0 %
4 h=04_t=006_s=010_m=06__11ZZ.json 29 23 26,1 %
5 h=05_t=003_s=012_m=02__177Z.json 14 12 16,7 %
6 h=06_t=007_s=022_m=07__3S34.json 52 52 0,0 %
7 h=06_t=008_s=015_m=03__AQDP.json 14 14 0,0 %
8 h=06_t=012_s=031_m=06__6BJV.json 56 54 3,7 %
9 h=06_t=013_s=025_m=07__3QMV.json 58 54 7,4 %
10 h=06_t=013_s=025_m=07__4I1G.json 59 55 7,3 %
11 h=06_t=023_s=049_m=05__1BH7.json 75 75 0,0 %
12 h=07_t=014_s=041_m=05__69H9.json 66 66 0,0 %
13 h=07_t=015_s=042_m=05__20QD.json 78 72 8,3 %
14 h=07_t=024_s=056_m=02__4SBO.json 43 43 0,0 %
15 h=07_t=030_s=067_m=08__32FA.json 169 169 0,0 %
16 h=08_t=050_s=120_m=08__6AQN.json 277 277 0,0 %
17 h=08_t=059_s=125_m=04__34B6.json 172 167 3,0 %
18 h=08_t=081_s=155_m=02__5G3E.json 119 119 0,0 %
19 h=09_t=061_s=184_m=05__37JB.json 299 296 1,0 %
20 h=09_t=069_s=212_m=05__1KVE.json 328 321 2,2 %
    96,90 94,95 3,78 %

Quelques réflexions sur ces résultats :

  1. Le gain moyen du FPTAS n'est pas énorme.
  2. Il ne semble pas croître avec la taille de l'instance, au contraire.
  3. Je me demande si le problème est vraiment si difficile en pratique.
  4. À partir du résultat de naive cut, j'ai l'impression qu'on pourrait très facilement améliorer le résultat en changeant aléatoirement les affectations des tuiles autour de l'index de la coupe. Par exemple, dans la plus grosse instance, les affectations du FPTAS sont (index de tuiles) :
    
    [0, 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,
    29, 31, 32, 35],

[28, 30, 33, 34, 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]

Tandis que celles de _naive cut_ sont :

[0, 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]


Vous voyez qu'il y a juste 8 tuiles concernées par les changements. Il serait très rapide d'énumérer les 2**8 permutations possibles pour retrouver celle du FPTAS, et peut-être une meilleure...

Vu la structure très contrainte des instances, je doute que ce cas soit une singularité.