search

pagination-problem / tree_structure

0 stars 0 forks source link

Tests manquants pour le FPTAS « amélioré » #10

Closed laowantong closed 4 years ago

laowantong commented 4 years ago

Il y a quelque temps, à ma demande, tu avais écrit un test du FPTAS de base sur une instance. J'ai l'impression que ce travail n'a pas été fait sur le FPTAS amélioré, ou je ne sais pas où il est. S'il n'y en a pas, peux-tu vérifier le déroulement suivant ? https://github.com/pagination-problem/tree_structure/blob/0aec5d109eb7bfea383aa090548c3273cc0a49db/tests/test_fptas.py#L95-L101

NB: j'ai changé alpha pour que les valeurs soient 1 et 2 (numéro du bin) et supprimé les conditionnelles dont je n'ai pas bien vu l'utilité, d'autant qu'elles n'apparaissaient pas dans l'article.

SarahMinich commented 4 years ago

Je n'ai pas la même chose dans mon exécution à la main (dont je joins les photos comme la dernière fois). Il faut que je souligne que j'ai fait l'exécution avant votre renumérotation alors sur les photos, j'ai corrigé au crayon à papier la valeur de k (les numéros de tuiles) et les valeurs de alpha. Photo_1 Photo_2

Cependant, je ne sais pas où mettre la liste des états comme vous m'avez demandé de ne pas écrire dans refactoring alors je la mets dans ce commentaire. 

expected_log_result = [
        [(0, 0, -1, 2)],
        [(8, 0, -1, 1), (0, 8, -1, 2)],
        [(11, 0, -1, 1), (8, 8, 1, 2), (0, 11, -1, 2)],
        [(15, 0, -1, 1), (11, 11, 2, 2), (14, 8, 2, 1), (8, 12, 1, 2), (0, 15, -1, 2)],
        [(27, 0, -1, 1), (15, 12, 3, 2), (23, 11, 3, 1), (11, 23, 2, 2), (26, 8, 2, 1), (14, 20, 3, 2), (20, 12, 3, 1), (8, 24, 1, 2), (12, 15, 3, 1), (0, 27, -1, 2)],
        [(32, 0, -1, 1), (27, 14, 4, 2), (29, 12, 4, 1), (15, 17, 3, 2), (28, 11, 3, 1), (23, 25, 4, 2), (25, 23, 4, 1), (11, 28, 2, 2), (31, 8, 2, 1), (26, 22, 4, 2), (28, 20, 4, 1), (14, 25, 3, 2), (25, 12, 3, 1), (20, 26, 4, 2), (22, 24, 4, 1), (8, 29, 1, 2), (17, 15, 3, 1), (12, 29, 4, 2), (14, 27, 4, 1), (0, 32, -1, 2)],
    ]
laowantong commented 4 years ago

D'accord, super. Oui, corriger à la main sur le déroulement suffisait, merci. Je ne comprends pas trop bien ce FPTAS. Je regarderai un peu plus tard et reviendrai vers toi.

laowantong commented 4 years ago

Ce FPTAS est le même que l'autre, cf. #8