 |
||
| ||
| |||||
| Dernière réponse | |
|---|---|
| Sujet : Optimisation de Cd-R | |
| Profil supprimé | ya pas que moi que ca interresse :D |
| Aperçu |
|---|
| Vue Rapide de la discussion |
|---|
| ya pas que moi que ca interresse :D |
| psychoboust |
|
| Kyle_Katarn | finalement il s'appelle ignition et est dispo sur le forum de mon site |
| rufo |
|
| Kyle_Katarn | Je pense commencer par un LPT tout bête que j'optimiserai par la suite. De toute façon, je cherche plutôt à faire un soft qui minimise le nombre de CD pour les très gros archivages (qui à respecter qq contraintes comme 2 fichiers sur le même CD, un fichier sur tous....) plutôt que minimiser le waste sur chaque support.
En effet quel intérêt ? Si le nombre de CD est le même et le nombre total de clusters occupés, je ne vois pas ce que tu gagnes en temps (vitesse de graveur constante) ou en argent (même nombre de CD) |
| rufo |
|
| Kyle_Katarn | Je vais programmer un soft comme ça.
Je l'appellerai K-Burn et il sera sur mon site. J'espère que vous me donnerez votre avis... |
| rufo |
|
| rufo | au fait, y'a pas que moi qui suis dans une école d'ingénieurs et qui fait de l'ordo! Alors, les autres, bougez-vous quoi :)
Le type d'algo serait en fait un algo pour résoudre le critère LMax. |
| rufo |
|
| Largo |
|
| rufo |
|
| Largo | tsss y'en a qu'on vraiment la flemme de chercher! :)
google => "Burn to the brim" => j'ai de la chance. =>zdnet site officiel: http://members.ams.chello.nl/e.m.oost/bttb.html j'ai pas essayé le programme mais il a l'air pas mal. (peut-être pas optimisé et tout mais il fait ce qu'on lui demande et c'est déjà ça!) |
| rufo | up |
| rufo | bon, j'ai du nouveau pour résoudre ce pb o'optimisation de cds. J'en ai parlé à un de mes profs et il m'a dit que mon pb était NP difficile (sans blague, voilà pourquoi on a du mal à trouver la solution) et que c'était un pb du type FPCmax. Je suis bien avancé avec ça, vu que je sais pas ce que ça veut dire ni quel algo résout ce type de pb. Et mon prof avait pas le temps de me dire comment on résolvait ce pb. Donc si qq'un connait un algo qui résout le FPCmax, merci de m'aider :) |
| gilou | >Ma méthode LPT essaye de placer les fichiers de manière à remplir Cd après cd. Dans le cas où un fichier rentre pas sur un cd, on le place sur le cd suivant (s'il reste assez de Cd, si non, il est rejeté).
Oui, elle n'est optimale que si tu a un nombre de CD illimite. Des que tu as un nombre de CD a graver limite, elle n'est plus optimale. Quand je t'ai dit que je ne voyais pas de methode a priori, c'est parce qu'il est assez clair (on peut facilement imaginer le cas) ou l'ajout d'un fichier a la liste des fichiers a graver implique une reorganisation totale de l'ensemble des CD. Et je ne pense pas que la solution pour N+1 CD soit deductible de celle pour N CDs, a nombre de fichiers constant. A+, |
| rufo |
|
| bol | Mystereetbouledegomme a écrit :
-------------------------------------------------------------------------------- Parce que c'est pas parce que tu prends les plus gros fichiers d'abord que l'espace perdu sera minmale... -------------------------------------------------------------------------------- Rufo moi qui ait implémenté cette méthode dite LPT (tri dans l'ordre décroissant), je peux vour affirmer qu'elle n'est pas optimale, seulement de temps en temps. Du reste, vousa vez qu'à télécharger mon soft et faire les tests. Mon soft propose les 2 méthodes : LPT et combinatoire, qui donne la meilleure solution mais pour un nb de fichiers < 18. C'est pour ça que je proposais 1 étape d'"étude" stat avant la répartition sur les CD. |
| rufo |
|
| mystereetbouledegomme | Parce que c'est pas parce que tu prends les plus gros fichiers d'abord que l'espace perdu sera minmale... |
| bol | Comme ça, à vue de nez, sans faire de calcul d'optimisation car j'en suis incapable, je verrais 2 niveaux pour l'algorithme:
1/ rapide étude statistisque sur les fichiers (nombre, taille, moyenne, médiane et écart type) et suivant les résultat utiliser certaine méthode. 2/c'est un exemple de méthode qui doit pas être mauvaise pour les grands nombre de fichiers avec un écart type important (ce qui n'est peut-être pas les cas pour les fichiers vidéo). 1/classement das fichiers dans l'ordre décroissant 2/on prend les fichiers du plus gros vers le plus petit on le met sur le premier CD s'il rentre, sinon, on le met sur le second, sur le troisième.... Je me demande pourquoi cette méthode n'a pas été signalé avant (a moins de ne pas avoir compris tous les posts) ... il doit donc y avoir une couille quelque part. |
| gilou | >De plus, Cet algo, a priori, n'est pas optimisé (je veux dire qu'on ne minimse pas la place perdu sur chaque cd). Il me semble qu'il optimise a partir du moment ou tu graves tout, du fait du classement par taille decroissante. Oui, j'ai relu tes hypotheses de depart ensuite, et j'ai vire une mofication pour ton pb de l'algo precedent, qui n'etait pas optimale. A+, |
| rufo |
|
| gilou | Voici un algo pour Calculer le nombre optimal (minimal) de CD (de taille maximale TAILLE_MAX) pour graver toute une liste de fichiers.
Donnees de depart: Liste_des_fichiers, et TAILLE_MAX (d'un CD) 1) Ordonner la liste par taille decroissante. 2) Virer de la liste (Ranger dans une liste annexe, celle des fichiers trop gros) les fichiers f de Liste_des_fichiers pour lesquels Taille(f)>TAILLE_MAX. 3) appliquer l'algo suivant: Boucler sur f de Liste_des_fichiers (ordonne par taille decroissante). Ajouter (f, Liste_des_CD); Fin_Boucle. et ou (un CD etant une liste de fichiers), Ajouter (f, Liste_des_CD) Si Liste_des_CD est vide Alors Creer cd (nouveau CD); Ajouter cd a Liste_des_CD; retirer f de liste_des_Fichiers Ajouter f a cd. Sortir de Ajouter(f, Liste_des_CD). Sinon Boucler sur cd de Liste_des_CD. Si Taille(f)+Taille(cd) <= TAILLE_MAX Alors retirer f de liste_des_Fichiers Ajouter f a cd. Sortir de Ajouter(f, Liste_des_CD). Fin_Si /* Si Taille(f)+Taille(cd) <= TAILLE_MAX */ Fin_Boucle /* Si on arrive ici, on n'a pas reussi a ranger f dans un CD de la liste. On en cree un nouveau, on l'ajoute EN FIN DE LISTE (des CD), et on y range f */ Creer cd (nouveau CD); Ajouter cd a Liste_des_CD (en fin de liste) retirer f de liste_des_Fichiers Ajouter f a cd. Sortir de Ajouter(f, Liste_des_CD). Fin_Si /* Si Liste_des_CD est vide */ A+, [edit]--Message édité par gilou--[/edit] |
| rufo | up |
| rufo | up |
| rufo |
|
| mystereetbouledegomme | Pas bete ca risque de degenerer en backtrack a mon avis mais c'est pas mal du tout... Bravo |
| rufo | bon, je crois avoir trouvé un truc imparable... une PSE (procedure par Séparation et Evaluation). On commence par classer les fichiers dans l'ordre décroissant. Ensuite, on va découper l'ensemble initial des fichiers en sous-ens de taille la plus proche des Cds donnés. Ensuite, on va compléter les cds les plus remplis avec des fichiers provenant du cd le moins rempli. Une fois le cd le moins rempli vide (ça peut être la liste initiale, privée des fichiers répartis sur les autres cds), ben c'est fini. Si on n'arrive pas à vider le cd (ou la liste initiale), on commence à faire une rotation du fichier le plus gros de chaque cd, d'un cd à un autre pour voir si on peut faire rentrer un des fichiers restant à placer. Si c'est possible, on recommence à faire une permutation, jusqu'à ce qu'on ne puisse plus diminuer la perte...
c'est pas vraiment évident à expliquer. pour ce qui est de fixer des contraintes, genre tous les fichiers d'un répertoire ensemble, il suffit de dire que finalement le répertoire, c'est un unique fichier. Et au lieu d'ordonnancer des fichiers, on ordonnance des répertoires |
| mystereetbouledegomme | Ca y est je pense avoir compris ... |
| mystereetbouledegomme | C'est juste dans l'article quand il parlait d'une loi normale centree ca m'a fait faire des cauchemars et rappelle un de mes cours de proba... Tu peux pas t'imaginer l'horreur :sol: Merci pour le petit cours de math image sur les minima locaux :) Mais le recuit sert a minimiser ou maximiser une fonction a plusieurs variables. Et l'intelligence du truc est de pas rester coince a certains moment en pensant avoir trouve un minimum alors qu'il y en a un meilleure "plus loin". Ce que je ne comprend pas (peut etre suis je debile) c'est comment l'adapter au probleme concret ici present...(je vais peut etre relire les post precedent c peut etre explique) |
| wpk | et la on reviens a ce que je disais un peu plus haut sur l'interdepence des differents fichiers : la creation d'entites d'optimisation.
Une entite d'optimisation est dans mon esprit un ensemble de fichiers, repertoires, etc qui est indivisible et qui doit forcement se retrouver sur un cd. myster> pour le recuit, c'est pas bien complique, y'a pas besoin de maitriser les proba (c'est utile juste pour une demo qui prouve que ca marche). En gros, le principe c'est que tu permute des entites d'optimisation entre cds et si l'espace libre que tu trouve est moins grand que pour la solution d'avant, ben t'as une nouvelle solution que tu va encore essayer d'ameliorer. La ou le bat blesse c'est que si tu fais ca, tu risque de te retrouver dans un minimum local. C'est l'histoire de la montagne en gros tu tombe dans une crevasse :). Donc pour eviter ce probleme, tu t'autorise a prendre des solutions moins bonnes que ta solution courrante (tu escalade courageusement les parois de la crevasse) avec une certaine proba cf article ce qui te permet de sortir de ces min et atteindre (on l'espere) le vrai min global. |
| mystereetbouledegomme | Non je sais pas c pour ca que j'ai poster en esperant que qq'un le trouverait mais je vais mieux chercher |
| rufo |
|
| rufo |
|
