search

pagination-problem / tree_structure

0 stars 0 forks source link

Backtracking du FPTAS #14

Open laowantong opened 4 years ago

laowantong commented 4 years ago

Je me suis rendu compte qu’il y avait dans quelques instances une incohérence entre le c_max calculé et celui que je retrouvais par backtracking. Il s’avère que mon backtracking était faux. Et après m’être arraché quelques cheveux (des blancs, quitte à faire), j’en suis arrivé à la quasi-certitude que là encore, il n’y avait pas suffisamment d’informations dans le quadruplet pour faire la remontée.

Alors bien sûr, il y a la possibilité de stocker une information de plus pour pouvoir remonter. Mais ce serait contourner un problème qui me paraît en soi relativement intéressant. Est-ce qu'on pourrait : soit prouver l’impossibilité, soit trouver une méthode pour remonter sans erreur ?

À creuser !

laowantong commented 4 years ago

NB: actuellement, le backtracking proposé donne un résultat faux sur certaines instances, comme on peut s'en convaincre en décommentant l'avant-dernière ligne de cette fonction : https://github.com/pagination-problem/tree_structure/blob/9c4e1e801e056876eaddc26195efe2930cea4cad/solver_fptas.py#L42-L72

laowantong commented 4 years ago

@SarahMinich Après discussion avec @imedk , on pense que c'est un bon petit problème pour toi : que le résultat soit positif (tu prouves que la remontée est possible avec seulement les informations nécessaires à la descente) ou négatif (tu construis un contre-exemple), c'est quelque chose que tu peux faire apparaître dans ton rapport de thèse.

SarahMinich commented 4 years ago

Je me penche sur la question !

laowantong commented 4 years ago

Quand tu auras les réponses, j'écrirai si nécessaire le stockage des informations permettant la remontée en m'arrangeant pour ne pas pénaliser le solveur si on ne veut pas les calculer.