Discussion :

[barbot]

Bonjour a tous,
je souhaiterai savoir si qqn connait un site ou possede un algorithme de type nextbestfit pour la separation d'un probleme de type bin packing (ranger de facon optimale x objets de poids différents dans n boites de tailles fixes) car là j'ai du mal... .
Merci d'avance..

[ErwanVDF]

Salut,
En fait j'ai pas une soluce directe à ton pb, mais c'est le genre d'algo qui me branche. Si tu veux bien m'en dire plus, je me ferais un plaisir de te faire un joli algo. (me semble en effet que le poids n'a pas trop de rapport avec la taille de la boite, mais que c'est plus une question de volumes).

[barbot]

donc le probleme exact est :

nous disposons de :
X medias (cd) de taille identique T
N fichiers de tailles differents (tailles contenu ds un tableau C)

Nous cherchons à minimiser le nombre de Cd utilisés, pour cela j'ai opté pour trier les medias et les cd par ordre decroissant puis d'inserer le premier fichier (donc le plus gros) ds le premier CD ou il y a assez de place pour le stocker.
Les medias sont soit ouvert (on enregistre des choses dessus), soit fermé (ils sont plein) soit rien (pas encore utilisé).

Nous faisons donc une Guerre eclair (permettant de trouver vite une solution ), nous construisons un arbre puis nous faisons une Guerre de front qui a partir de l arbre construit permettra de trouver LA solution. Je ne sais pas si tu est familier avec ces notions "Guerre Eclair" et "Guerre de Front", si c'est le cas cool sinon renvoi moi un message et je te repondrai plus precisément.

Notre "séparation", pour la creation de l arbre (savoir ce qu'on met ds le fils Gauche et ds le fils droit), est "trouver un media suffisament grand pour le prochain fichier a mettre (en regardant en priorité ds les médias deja ouvert)" et notre separation .. bne justement on en a pas.. (rappel : sepration : ce qui sera contenu ds les noeuds de l arbre et qui permettra de savoir si nous allons ds le fils gauche ou droit lors des différentes guerres, il s agit en fait d'une formule mathématique -à trouver- mais qui devrait ressembler à :
{
nb de media ferme +
nb de media ouvert +
[
(taille des fichiers restant apres insertion du fichier en cours)-
(la taille dispo sur les medias ouverts)
]
/ (taille initiale du cd)
}

Voila voila ... merci d'avance et bonne chane pour la comprehension de mon superbe énoncer .. si tu as une autre solution pour ce qui est de la programmation je suis ouvert a tout ..
merci et bonne année

[ErwanVDF]

Salut,
Suis pas familier avec tes termes, mais bon ce que j'en ai compris :
Tu crées un arbre binaire pour pouvoir ranger tes fichiers, à chaque noeud est associé un CD et la grande question est de savoir comment déterminer le poids de chaque noeud...
En ce qui concerne ta guerre éclair/guerre de front... euh.. c'est quoi ça?
Ce que j'en ai compris : Ta "guerre de front" est une seconde passe d'optimisation. Tu pourrais m'en dire plus stp? Sinon, j'essaie de te trouver un algo rapide s'appuyant sur un btree

[ErwanVDF]

euh,
ben ta solution est dans ton énoncé en fait..
Avec un btree équilibré où le déterminant est l'espace restant du média tu peux rapidement trouver le cd optimal ou placer ton fichier.
Ensuite, ben si t'es pas familier avec les btree équilibrés, l'algo de suppression d'un noeud est pas trop évident...

En gros pour moi t'as :

Pool Fichiers Pool Medias vierges


Arbre des Médias ouverts

1) Recherche d'un média ouvert dans lequel placer le fichier
1.a) Si trouvé : Intégrer le fichier, Repositionner le noeud par suppression/réinsertion dans l'arbre
1.b) Sinon : Intégrer le fichier dans un média vierge, et insérer le média dans l'arbre

Voilà, tu fais ça en boucle jusqu'à ce que ton pool fichiers soit vide...
Ensuite il reste la question de l'optimisation du stockage (ta seconde passe), vais me pencher dessus

[ShootDX]

Voila ce que je ferais: on fait tout en une passe.

Variables:
Liste des CD, avec liste des fichiers qu'ils contiennent.
Liste des CD où l'on peut encore insérer des fichiers.

Algorithme:
Pour tous les fichiers
Pour tous les CD pas pleins
Si taille restante > taille fichier alors
Insérer fichier sur le CD courant.
sinon si taille restante == taille fichier alors
Insérer fichier sur le CD courant.
Suppression du CD courant de la liste des CD pas pleins.
Fin Si
Fin Pour
Fin Pour

[ErwanVDF]

euh, shootdx, pas beau de post avant de lire..

L'algo que j'ai donné juste avant résoud la même chose que le tien mais devrait être plus rapide (btree équilibré).

Le problème de la seconde passe (l'optimisation du stockage) est le suivant :

Si on suppose des CDs de taille 10
La suite de fichiers : 7 6 5 5 3 3 3 2 2 2 2

Le résultat en première passe est :
7+3, 6+3, 5+5, 3+2+2+2, 2

Le résultat optimisé est :
7+3, 6+2+2, 5+5, 3+3+2+2

D'où la necessité de la seconde passe. Actuellement je me penche sur un algo par permutations qui pourrait peut-être s'inscrire dans la première passe. Mais j'ai pas encore fini ma réfléxion à ce sujet.

Barbot, suis pas contre le fait que tu confirmes la problématique de la seconde passe (ton guerre de front)

[ShootDX]

Désolé, j'avais pas vu ton post, ErwanVDF . Par contre, je penses qu'il aurait été plus judicieux de mettre ça sur le forum algorithmes, pour que plus de personnes puissent se pencher dessus.

[barbot]

rebonjour bonne annee à tous ..
vos idées sont intéressantes.
Voila ce qu'est une guerre de front : il s'agit en fait d'une (comme tu l avais dit) seconde optimisation afin de trouver LA solution. L'idée est de reparcourir l'arbre créé au début (par une guerre eclair) et "d'ébrancher" l'arbre (ds le sens ou si une evaluation d'un noeud est superieur a la solution trouvée alors nous ne descendons pas dans ses fils).

Sinon j'ai hate de connaitre ton algo pour pouvoir le comparer avec celui que je suis en train de faire...(etude de complexité et autre...)
a plus et merci de l 'interet que vous portez au sujet...

[ErwanVDF]

re,
Bon, j'ai trouvé des approches pour la seconde passe, mais j'aurais besoin d'un peu plus de précision. Me faudrait une idée des volumes traités en fait, car la structure à employer (voir l'algo) y sont liés...
De plus, après réfléxion, un arbre équilibré serait pas adapté, ptet qu'une simple liste chainée devrait suffire en fait...

Pour l'instant ma méthode de permutation ressemblerait à ça :
Pour tous les médias non pleins (triés par espace libre)
Recherche dans les médias suivants d'un couple F1 + F2, ou taille de F1+F2 > Taille de mon plus petit fichier (FP) et <= à taille FP + Espace libre.
Sachant que la contrainte est Taille F1 < Taille FP et que les fichiers sont triés par taille vu la première passe, l'algo devrait pas être trop long.
(On permute FP avec F1+F2 si on trouve)

Je pense que des améliorations sont possibles (travailler sur n'importe quel fichier, faire des permutations avec des ensembles plus grands, ...), mais les contraintes de temps d'éxécution entrent alors en jeu. D'où ma question sur les volumes : Nbre et Taille des médias, Nbre et taille moyenne des fichiers... (Si t'as un jeu d'essai je suis preneur et on pourrait faire des tests comparatifs)

Erf, je viens de remarquer que t'avais déjà un post sur ce forum avec problème mathématique.. Bon, je précise, je suis pas mauvais en math, mais mes connaissances sont limités. De plus, en informatique, il est assez rare que j'ai besoin d'une formule de math compliquée. En général j'utilise plutot de la simple logique. Tout ça pour dire que si tu cherches des formules de math je pourrais pas trop t'aider...

[tomtom7]

Salut,

rappel : sepration : ce qui sera contenu ds les noeuds de l arbre et qui permettra de savoir si nous allons ds le fils gauche ou droit lors des différentes guerres, il s agit en fait d'une formule mathématique -à trouver- mais qui devrait ressembler à :
{
nb de media ferme +
nb de media ouvert +
[
(taille des fichiers restant apres insertion du fichier en cours)-
(la taille dispo sur les medias ouverts)
]
/ (taille initiale du cd)
}

Tu confonds évaluation et séparation je crois.
Tu doit avoir une règle de séparation pour partitionner l'espace des solutions.
Tu dois avoir une fonction d'évaluation pour borner le coût de toute solution contenue dans un noeud.

C'est pas clair je sais mais c'est pas super simple.
Je vais essayer d'être plus clair en repartant du début car je ne crois pas que tout ait été expliqué en détail.

Au sommet de l'arbre, le noeud racine (S0) représente l'ensemble des solutions. L'évaluation de S0 est le coût de la solution trouvée pendant ce que tu appelles la guerre éclair cela donne à la fois une solution réalisable et son coût qui peut servir de borne au delà de laquelle on refuse toute solution car elle coûterait plus cher.
La règle de séparation lui donne n fils (je ne sais pas s'il est possible dans ton cas que l'arbre soit binaire...) (S1,S2,..,Sn) distincts. S1US2U...USn=S0 (S0 est partitionné). Chaque arête liant un noeud à son père correspond à un état de la solution (exemple : séparation = le fichier i dans le média j)
Chacun de ces noeuds Sx va être évalué avec la même fonction qui va donner une borne inférieure du coût de toute solution contenue dans Sx. Si ce coût est supérieur (ou égal) au coût min courant => aucune solution de Sx n'est meilleure que celle que l'on a actuellement. Donc on coupe la branche reliant Sx à son père et ainsi on restreint l'espace des solutions à explorer.
Et ainsi de suite on explore les noeuds restants jusqu'à parvenir en bas de l'arbre => si le coût est inférieur au coût min courant => on a une solution meilleure que la solution courante. Si on n'a pas exploré tous les noeuds valides => on remonte l'arbre et on continue.

Par contre la fonction d'évaluation doit être sûre. Celle que tu as définie plus haut l'est je pense car on est sûr qu'il n'y aura pas moins de médias utilisés que le résultat qu'elle donne puisqu'on calcule la borne pour des fichiers sécables.

Ainsi on est sûr d'avoir un optimum. On a épuisé toutes les solutions sans les énumérer toutes.

J'espère avoir été clair.
En tout cas c'était une belle révision... Merci barbot.