Choisir le représentant par minimisation de la distance de Chebyshev

[laowantong]

On évalue une solution en calculant le maximum des poids du bin 1 et du bin 2. Une solution est meilleure qu'une autre si cette valeur est inférieure.

Or, au moment de choisir un représentant, c'est un autre critère qui est appliqué : au lieu de comparer les max de deux couples, on compare ces couples. Ça ne me paraît pas logique.

Même s'il est probable que le choix d'un représentant dans la case importe peu jusqu'à l'avant-dernière étape, il se peut très bien que, lors de la dernière, la meilleure valeur (au sens du max) vienne juste d'être éliminée au profit d'une autre (au sens du couple). C'est potentiellement contre-productif. Je propose donc de faire cette simple modification.

J'ai lancé ça sur mes 20 instances de test, vous pouvez voir le résultat en 9cc09df. En résumé :

• dans la quasi totalité des cas, on génère moins d'états ;
• aucun c_max n'est modifié.

Pour voir apparaître une amélioration, il faudrait sans doute jouer sur l'epsilon.

NB: le nom de la branche vient du fait que j'ai cru dans un premier temps que c'était une distance de Manhattan. Il s'agit en fait de la distance de Chebyshev:

[imedk]

Au fait, il peut y avoir plusieurs choix possibles pour le représentant d’un box dans la grille. On peut prendre l’état avec le meilleur a ou le meilleur b... On peut aussi prendre le meilleur max(a,b). La complexité ne change pas et la précision algorithmique n’est pas modifiée. On peut aussi prendre la meilleure pondération. Par contre, expérimentalement, on ne peut pas deviner sans tester cela. Après, on doit adapter un peu la preuve si on opte pour un autre choix, mais c’est faisable en 2 heures...

[laowantong]

Edit : j'ai modifié le texte de l'issue avec le nom de cette distance. Je ne pensais pas que ça avait un impact sur la preuve, mais s'il est minime, je suis d'avis de mettre en cohérence la métrique du meilleur représentant avec celle de la meilleure solution.

[codecov-io]

Codecov Report

Merging #15 into master will not change coverage. The diff coverage is 100.00%.

@@           Coverage Diff           @@
##           master      #15   +/-   ##
=======================================
  Coverage   48.86%   48.86%           
=======================================
  Files           9        9           
  Lines         440      440           
=======================================
  Hits          215      215           
  Misses        225      225           

Impacted Files	Coverage Δ
solver_fptas.py	87.00% <100.00%> (ø)

---

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update db277c8...3eb9bfd. Read the comment docs.