search

pagination-problem / tree_structure

0 stars 0 forks source link

Suppression de nœuds lors de la génération d'instances #9

Closed laowantong closed 4 years ago

laowantong commented 4 years ago

Avec la nouvelle numérotation, je pense qu'il n'y a plus aucune raison de conserver des symboles de poids nul, qui ne font qu'encombrer les données manipulées lors de la résolution.

Je m'aperçois que dans ton instance fétiche, le poids de la racine était à zéro (autrement dit, il n'y a pas de symbole commun à toutes les tuiles). Je ne me souviens plus trop de notre discussion à ce sujet, il me semble que j'en était arrivé à la conclusion que tu avais besoin de conserver systématiquement la racine et les feuilles, mais je n'en vois plus l'utilité. Dans la méthode ci-dessous : https://github.com/pagination-problem/tree_structure/blob/21a843dfc7d25e0598830efe19c75f1f669bb58a/instance_maker.py#L32-L42 j'envisage donc de supprimer les deux appels à différence() en ligne 38. Pas d'objection ?

SarahMinich commented 4 years ago

Ce n'est pas mon instance «fétiche», c'est une instance que j'avais sous la main quand vous m'avez demandé de créé un test pour le FPTAS, je l'ai donc exécutée à la main et mise en ligne.

C'est un erreur qu'il n'y ait pas de poids à la racine, c'est le seul sommet pour lequel on est sûr qu'il doit y avoir un poids car il faut que les tuiles aient une hiérarchie en forme d'arbre.

Je ne suis pas sûre de bien comprendre le deuxième appel à difference() mais je suis presque sûre qu'il faille laisser le premier car je crois qu'il dit qu'il ne faut pas supprimer la racine.

laowantong commented 4 years ago

Je suis étonné que tu aies pu passer une demi-heure à dérouler une instance que tu as toi-même construite sans te rendre compte que la racine avait un poids de zéro. Maintenant que je te le fais remarquer, tu dis que ce poids doit être non nul et que c'était une erreur.

Jusqu'à plus ample informé, je pense quant à moi que rien n'empêche que le poids de la racine soit nul, idem pour les feuilles (leaves en anglais) ou tout autre nœud, et je vais modifier en conséquence l'algorithme de génération.

Bien sûr, je reviendrai volontiers en arrière si tu me fournis une preuve que l'existence d'une racine de poids non nul est requis. Une petite instance contre-exemple fera aussi parfaitement l'affaire.

Écrire « il faut », même en gras, n'est pas suffisant.

SarahMinich commented 4 years ago

Je ne dis pas que les algorithmes risquent de ne pas marcher ou quoi que ce soit. Je dis que c'est nécessaire qu'il y ait une racine car c'est le cas dans lequel on s'est placés pour effectuer ce travail. Je n'ai pas de contre exemple à donner car il n'y en a pas. Nous avons fait une réflexion sur le cas où il y a une hiérarchie dans les tuiles, je ne vais pas abandonner maintenant cette hiérarchie.

laowantong commented 4 years ago

Il ne s'agit « d'abandonner » cette hiérarchie. Juste de ne pas exclure arbitrairement les cas, parfaitement valides, qu'on appelle « dégénérés ».

Si tu écris un algorithme ou une preuve sur les triangles (par exemple un calcul d'aire), tu ne vas pas exclure a priori les triangles plats. Ce n'est pas pour autant que tu abandonneras la notion de triangle.

Une hiérarchie sans racine, avec des feuilles manquantes, ou même un bin-packing (i.e., sans symbole commun) sont autant de cas dégénérés parfaitement dignes de considération.

Le débat est donc clos, sauf contre-argument mathématique ou algorithmique de ta part, auquel cas je t'engage à rouvrir cette issue.

laowantong commented 4 years ago

En ebac760 j'ai ajouté trois paramètres permettant de configurer le générateur d'instances :

NB: Ces éventuels symboles communs étant forcément affectés aux 2 bins, c'est dans un pré-traitement qu'il faudrait les affecter, et non dans l'algorithme proprement dit. Pour faciliter cela, j'ai ajouté un champ common_symbols dans l'instance générée. Mais clairement le mieux serait qu'il n'y ait pas de symboles communs du tout (i.e., common_symbol_min_count == common_symbol_max_count == 0).