search

pagination-problem / tree_structure

0 stars 0 forks source link

FPTAS basé sur la modification des p_i #19

Closed laowantong closed 4 years ago

laowantong commented 4 years ago

Je l'ai effectivement programmé et testé le 10 mai, voici ce que j'ai écrit à Imed à ce moment:

Bon, j’ai ajouté ça, et j’en ai profité pour revoir la structure pour faciliter l’ajout de variantes ultérieures. Celle-là en tout cas ne semble pas supporter la montée en charge, mais il se peut que je n’aie pas compris, car en l’état ça revient simplement à diminuer la borne du poids des symboles d’une instance, et ça n’apporte rien par rapport au FPTAS initial. Le calcul est fait là essentiellement : https://github.com/pagination-problem/tree_structure/blob/355a24897048904b125f4856ef52b2192e333fd1/instance.py#L56-L60 Grosso modo, comme dirait Imed 😉, je copie l’instance, je réduis les poids des symboles et je lance le calcul normalement, sauf que je n’ai plus besoin de « cache » puisque je garde tous les états d’une étape.

Pour moi, ce FPTAS revient à « hacher » les symboles au lieu de « hacher » les états générés. Ce hachage intervient sur l'instance elle-même, et est donc équivalent à choisir une instance avec des poids plus petits. Ce qui veut dire que si l'on souhaite appliquer ce FPTAS à un jeu d'instances donné, il suffit d'appliquer la programmation dynamique normale à un jeu d'instances modifiées par la fonction donnée ci-dessus.

Ce code qui d'un côté me paraissait inutile, et de l'autre compliquait l'architecture, est passé à la poubelle le 13 mai au moment d'un important refactoring du solveur (7e4ee9461371639d382df0610c2284512f1deefc). Il ne peut pas être rétabli facilement, par contre il est facile de créer un dossier parallèle avec les instances modifiées par hachage des poids, et lancer n'importe quel solveur dessus. Je n'en verrais juste pas l'intérêt.

Une autre hypothèse est que je n'aie pas compris l'idée d'Imed concernant ce FPTAS. Auquel cas mon implantation est erronée, et donc très bien dans la poubelle.

laowantong commented 4 years ago

Mail d'@imedk :

Au fait, la deuxième FPTAS utilise une technique de modification des données de l’instance. L’objectif d’un article n’est pas de montrer seulement le meilleur FPTAS (le tout premier). Bien entendu, si le deuxième ne donne pas de bons résultats, cela est également intéressant à mentionner. Ces tests mettront en évidence que le premier FPTAS est meilleur (et par conséquent que la technique de modifier l’algo exact est plus performante que la technique de modifier l’instance pour notre problème). Sur d’autres problèmes, ce n’est pas toujours le cas. Cela éviterait aussi des remarques des referees comme « pourquoi vous n’avez pas testé la technique de modification de l’instance ?».

Donc c'est bien ce que je pensais, il n'y a pas de FPTAS spécial à programmer, il suffit juste de créer un dossier d'instances modifiées, et j'ai laissé la fonction qui permet de faire la conversion d'une instance.

Cela clôt donc la question.