Reprise du message précédent :

 
tu sais où le downloader?

wpk a écrit a écrit : rufo> desole j'ai pas le .pas ni le zip mister...>les algos genetiques sont pas mal mais tres difficiles a manier. Le codage de tes chromosomes et la politique de mutation et de cross-over doivent etre regles au poil pour que ca marche pour le mieux. Du fait, en general, la vitesse de convergence de ce genre d'algos est moindre que celle du recuit ou les versions un peu plus ameliores de ce dernier. rufo>pourquoi tu ne mets pas tous tes fichiers du 1er coup dans le processus d'opti? Tu mets tout d'un coup, tu touille bien avec un algo (genetique ou recuit) et tu recupere un sol. Ensuite, s'il reste un cd qui n'est qu'a moitie rempli, tu l'ejecte a la mano. En principe, l'utilisateur possede ce qui se fait de mieux en IA : un cerveau .

 
mais tu perds de vue que certains fichiers qui seraient classés sur le cd à moitié rempli pourraient très bien faire partie d'un autre cd et qui permettrait de perdre encore moins de place...

Non je sais pas c pour ca que j'ai poster en esperant que qq'un le trouverait mais je vais mieux chercher

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.

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  
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)

Ca y est je pense avoir compris ...

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

Pas bete ca risque de degenerer en backtrack a mon avis mais c'est pas mal du tout... Bravo

 
ben je pense au contraire que ça va accélérer la convergence vers la solution (ou une des solutions) du fait qu'on permute pas les fichiers "au hazard"
 
sinon, y'a qq'un qu'a trouvé un soft, Burn To The Brim et qui fait à peu près ce qu'on cherche à faire
http://members.ams.chello.nl/e.m.oost/bttb.html
 
j'ai testé, c'est pas pile poil ce que je veux, mais bon

up

up

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]

 
algo simple mais qui ne répond pas au problème. De plus, Cet algo, a priori, n'est pas optimisé (je veux dire qu'on ne minimse pas la place perdu sur chaque cd). Ton algo est de type LPT (last processing time first, en ordo). Je l'ai déjà implémenté, mais il donne rarement la meilleure solution.
De plus, le pb est le suivant : je fixe le nombre de CDs à graver et le soft, à partir d'une liste de fichiers, les prend tous ou en partie afin de remplir au max les cds.

>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+,

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.

Parce que c'est pas parce que tu prends les plus gros fichiers d'abord que l'espace perdu sera minmale...

 
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.
 
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é).

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.

et après ton étude stat, tu interprète comment les résultats obtenus? à priori, juste à le vue des tailles de fichiers, plusieurs chercheurs (en ordo, pour ordonnancer des jobs ayant chacun une durée) auraient montré qu'on pouvait rien en déduire quant à l'ordo de ceux-ci... J'ai pas vérifié perso, mais c'est vrai qu'après avoir fait quelques tests, j'ai pas réussi à mettre en avant une quelconque relation entre l'ordo et les tailles de fichiers...

>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+,

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

up

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!)

Largo a écrit a écrit : 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!)

 
désolé de te contredire Largo (Winch? ) mais je l'ai déjà téléchargé ce soft et testé. Il est pas mal, mais assez lent et n'intègre pas des contraintes que j'aimerais intégrer à mon soft... Du genre, si c'est possible, que 2 fichiers soient tous les 2 sur le même cd (ex: un film en 2 parties).
En fait, j'ai l'impression que ce soft essaye de bourrer le 1er cd avec les fichiers proposés, puis, avec ce qui reste des fichiers, essaye de bourrer le cd suivant, etc... jusqu'à ce qu'il n'y arrive plus. Mais ça, c'est pas de l'optimisation multi-cds car peut-être qu'en bourrant un peu moins le 1er cd, on aurait pu bourrer plus un autre cd... Tu vois le truc?

rufo a écrit a écrit :     désolé de te contredire Largo (Winch? ) mais je l'ai déjà ..... ---snip---

Désolé, Mea Culpa..., j'avais pas vu ton post ou tu donnais l'adresse dudit logiciel et tes critiques (c'était la fin de semaine.... BTTB peut rendre service a de nombreuses personnes je pense.... Mais c'est vrai qu'il est peut-être un peu simpliste au niveau de la méthode (j'en mets jusqu'à "plus soif" !
Tiens nous au courant pour ton soft... pour ma part, la discussion devient trop compliquée mais je suis potentiellement intéressé par le logiciel.

Largo a écrit a écrit :   Désolé, Mea Culpa..., j'avais pas vu ton post ou tu donnais l'adresse dudit logiciel et tes critiques (c'était la fin de semaine.... BTTB peut rendre service a de nombreuses personnes je pense.... Mais c'est vrai qu'il est peut-être un peu simpliste au niveau de la méthode (j'en mets jusqu'à "plus soif" ! Tiens nous au courant pour ton soft... pour ma part, la discussion devient trop compliquée mais je suis potentiellement intéressé par le logiciel.

 
t'as récupéré mon soft sur mon site?
http://perso.libertysurf.fr/chris.jav
 
Tiens, la semaine dernière, je suis allé voir un de mes profs, spécialiste dans les algos pour machines parallèles et pour l'instant, il m'a confirmé qu'il n'y a pas d'algo qui résout notre pb parce que c'est un pb NP-difficile. Il m'a dit (j'ai bien aimé la réponse du spécialiste): "ça marche ton truc? Ca te suffit pour ce que toi tu veux faire? T'as le temps d'attendre, alors ne change pas et garde ton algo puisqu'il fait ce que tu veux..." traduc-> "je connais pas d'algo, là j'ai aps le temps de me prendre la tête avec ton truc, alors casse toi"

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.

JoWiLe a écrit a écrit :     hey chris on te voit plus sur icq ?

 
normal, je suis en stage, et le soir, je dois faire tous les trucs que j'ai pas pu faire durant la journée...

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...

 
tu vas utilisé quoi comme algo? parce que si c'est pour implémenté un algo basé sur un LPT (trier les fichiers par ordre décroissant et les placer sur les cds jusqu'à ce que ça ne rentre plus) ou une évaluation de toutes les combinaisons, c'est pas la pein, je l'ai déjà fait et le soft est sur mon site:
http://perso.libertysurf.fr/chris.jav
 
par contre, si t'as un algo qui résoud le LMax (ou LMin), alors, là, je suis preneur
La modélisation de ce pb est la suivante : pb de type machines parallèles, avec :
n jobs (fichiers)
pi processing time des jobs (taille des fichiers)
m machines (cds)
pas de préemption (fichiers pas découpables)
dead line sur chaque machine (taille de chaque cd)
pas de temps mort (pas de trou entre les fichiers)
 
le critère à minimiser est la perte sur chaque cd.
 
Voilà, celui qui trouve une heuristique qui résout ça sans passer par un LPT ou une combinatoire a gagné Le pb est NP-difficile, c'est pour ça qu'au jour d'aujourd'hui le pb n'a jamais été résolu...de façon exacten, que par des méthodes approchées.

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)

 
justement, tu peux gagner en nb de cds... Et puis moi, le principe, c'est que je lui fixe ne nb de cds. Ah lui de faire tenir, si c'est possible, tous les fichiers sélectionnés ou au moins, d'en prendre certains pour perdre le moins de place possible

finalement il s'appelle ignition et est dispo sur le forum de mon site

 
   
 
Voila le premier post dans lequel on parlait de Ignition !
 
au final actuellement tu utilises quel algo ?
 
PS : si un jour tu as du temps pour rajouter cette option -> http://forum.hardware.fr/hardwaref [...] m#t1271963
 
manque juste une petite option pour deplacer les fichiers (optimisés) directement dans des dossiers de la taille désiré.
 
ça serait trop TOP    
 
en tout cas felicitation pour ce soft !

ya pas que moi que ca interresse