voilà, je recherche un soft qui permette d'optimiser la gravure de CD. On lui passe une liste de fichiers à graver sur un certain nombre de CD (on spécifie leur taille, 650 ou 700) et le soft calcule l'odonnancementd des fichiers (tels fichiers vont sur tel cd) afin de minimiser l'espace perdu par CD. Bien entendu, tous les fichiers ne sont pas obligés d'être pris pour être gravés.  
 
     J'ai déjà programmé un soft qui fait ça, mais je suis limité à 17 fichiers et pour 2 cds. Mais en plus, il calcule pas très rapidement.
 
     En fait, c'est un pb d'ordo à n machines (les cds), m jobs -les fichiers) avec un processing time pour chaque job (la taille des fichiers) et des dead line (les capacités des cds). Donc tous ceux qui sont dans une école d'ingénieurs et qui font de l'ordo sont les bien venus

C'est un programme sur les graphes de Petri si je ne m'abuse il y a pas mal de bouquin d'algo qui parle de sujet en long et en large.  

un pb de réseaux de Pétri? tiens, je vois pas trop comme modéliser ce pb avec Pétri...Un pb d'ordo est la chosequim'a apparu le plus logique...Une petite explication serait la bien-venue

Ben je sais pas trop mais c'est le premier truc qui m'est passe par la tete, si tu dois ordnner des jobs Petri c'est ce qu'il fait mais je ne puis t'en dire plus peut etre que Petri ne resoud pas le probleme j'ai juste dit ca en esperant que ca te dise qq chose a laquelle tu n'avais pas pense mais j'en connais pas plus sur Petri. Sorry

merci de la piste, je vais y réfléchir...

je crains que ton probleme ne soit NP complet (enfin faudrait le demontrer mais bon nous on s'en fout on fait de l'info )donc si t'as que peu de fichiers et peu de CD ca passe mais si t'as des milliers de fichiers et qcq centaines de CD eh bien, t'es ds la m*. Du coup, si tu veux aller vite, faut prendre des solutions approches (le recuit simule serait pas trop mal je pense a l'extreme limite que les algos genetiques serait egalement pas mal).  
Pour le recuit, c'est plutot simple :  
- tu tire aleatoirement une config (peu importe si elle est bonne ou pas).  
- Tu definis un systeme de voisinage (!! tres important, faut que ca respecte certaines regles) pour pouvoir passer d'une solution a une autre (Permutation de fichiers entre CD me parrait pas mal mais sans verif ).
- Tu applique le recuit simule.
Cet algo est probabiliste, c'est a dire qu'en propabilite, il converge vers la solution optimale.

eh wpk, ça a l'air pas mal ta solution...mais j'ai pas tout capté. Tu pourrais expliquer un peu plus en détail svp? Merci beaucoup...

c'est un tres vaste sujet qui fait l'objet de bouquins de centaines de page donc resumer en qcq lignes c'est pas simple  
 
Sur le principe de la bete : toi tu veux trouver une solution qui minimise l'espace perdu sur chaque CD.  
Tu cree une solution admissible (pas optimale). A partir de cette solution qui peut etre vraiement mauvaise, tu veux obtenir une solution un poil meilleure => tu applique un systeme de voisinage (une fonction qui te fait passer de l'etat A a l'etat B
en permutant pas exemple 2 fichiers sur 2CD).  
Si la solution ainsi obtenue est meilleure que la precedente, tu accepte la transition, l'etat B devient ton nouvel etat courrant.  
Sinon, avec une certaine probabilité (Gibbs par exemple) tu accepte une solution plus mauvaise dans l'espoir qu'a partir de celle ci tu puisse trouver une solution encore meilleure.
 
C'est comme a la montagne quand tu veux descendre dans la vallee. Des fois, il faut remonter pour descendre encore mieux apres .
 
 
pour un algo, essaye ca
http://cedric.brun.free.fr/Databas [...] mes/96.rtf

Put1 ca m'a l'air puissant et interressant ton truc mais ca converge ton truc parce que on dirait que non ou alors apres un temps tres grand?

On peut (me demande pas de le faire) prouver que ca converge (chaines de markov + proba) a condition de verifier certaines proprietes pour le sys de voisinage. En fait, la convergence est en proba (tu peux tres bien tomber a cote du min en plus la y'en a sans doute plusieurs mais meme si t'as pas le vrai min, tu vas obtenir en genral une tres bon majorant de ta solution)
Ce que j'ai pas dit au dessus c'est que la proba de l'acceptation des mauvaises transitions est de plus en plus faible avec la "temperature" qui descend au cours du temps c'est le principe du recuit (cf thermo)
 
Qd a la vitesse, c'est toujours plus rapide que de verifier toutes les config

C'est clair que c'est mieux que faire un bon gros backtracking :=)
Ta solution est interressente meme si j'ai toujours rate tout les cours de proba    

Effectivement mais est-est-ce que ton algo prend en compte le fait que le soft est pas obligé de prendre tous les fichiers de la liste que je lui passe? Dans ce cas là faudrait, je pense, faire une permutation entre 1 fichier de chaque cd et 1 qui est resté dans la liste...

je ne suis pas sur que perturber le systeme a ce point soit une tres bonne idee. Si tu fais entrer (et sortir) des fichiers dans ton sys, tu changes les min et tu risque de te retrouver nulle part alors que t'etait peut etre tout pres d'une bonne solution.
 
En plus, on n'a pas du tout parlé des contraintes, je suppose que tout tes fichiers ne sont pas forcement independants (genre pour une install, tu veux surement pas te retrouver avec ses fic sur 2cd) => ca simplifie un peu le probleme, ce qu'il faut optimiser c'est la repartition de plus grosses entites que les fichiers.

à vrai dire, c'est plutôt pour graver des fichiers vidéos...

je te conseille le OCaml pour faire ca .. c'est un langage tres puissant et tres simple en ce qui conserne le traige d'arbre binaire de recherche. et je pense que c'est un peu ce que tu cherches à faire..

Je vois pas tres bien ce que vienne faire les arbre binaire la dedans?  

moi non plus à vrai dire...Mais on va découragé les bonnes intentions Toute proposition est la bienvenue.
Sinon, y'a prolog comme soft pour traiter les pbs en récurcivité (avec backtracking). Mais je veux que mon soft soit un .exe

G 17 Go de MP3 a graver
 
UP

alors, t'en est ou?

 
ben pour l'instant, j'ai pas mal de boulot à mon école (des projets de RF, matlab...) donc j'ai même pas eu le temps de regarder ton algo... je vais m'y mettre ce week-end

je viens de lire le fichier sur l'algo du recuit. Ca a l'air pas mal ce truc. Dans l'article, ils parlent d'un fichier zip avec un .pas. Tu l'aurais pas sous la main?

pour télécharger le soft, tenez, voilà mon petit site:
http://perso.libertysurf.fr/chris.jav/

on m'a suggéré de faire l'algo du knapsack. C'est pas mal, mais il me semble qu'il est assez gourmand en temps. Qu'en pensez-vous?

Connais pas c'est koi le principe?

le pricipe, c'est qu'on a un sac-à-dos qui peut porter un poids max. On a un ensemble d'objets avec pour chacun, un poids. le but est de prendre un ensemble d'objets permettant de transporter un poids max. Ca colle bien avec mon pb, mais l'ennui, je crois, c'est que cet algo est assez coûteux en temps car il travaille sur des variables entières.

en fait, ce pc est un pb qui pourrait se résoudre avec un algo faisant appel à la programmation dynamique. Avis aux amateurs et aux connaisseurs.

Mon prof d'algo avait fait ce truc la enfin une version modifiee, il avait un sac a dos et donc un poids connaissant le poids de chaque objet il fallait determiner les objets dans le sac...
Mais il a fait un backtrack il me semble pour le resoudre ...

oui, c'est ça, c'est un algo assez lourd...Et pas très différent du mien, mais bon un peu plus rapide quand même...

en plus, le knapsack, c'est pour optimiser un seul sac-à-dos (ici un cd) et moi, je veux en optimiser plusieurs.

up

A mon avis à part le backtrack ou le truc probabiliste y a pas grand chose d'autre

voici un site mirroir qui permet de mieux télécharger mes 2 prgms
 
http://perso.wanadoo.fr/cyber69z/chris/

BOn je suis en train de regarder du cote des algos genetiques c pas sur qu'il soit plus rapide mais bon..
En fait (je commence suelement a lire l'article) ils disent que :
Au debut tu generes une solution(en genetique tu aurais des cellules viables) ensuites tu evalues leur potentiel de survie via des criteres definis avant.  
Ensuite tu as un nouvel ensemble de solutions et tu croises les solutions entre elle(reproduction= combinaison de l'ADN) et tu reevalue le potetniel de survie....
 
En gros tu joues a la selection naturel...
Bon le type utilise ca pour le knapsack alors je vais lire et faire un rapport plus tard (demain surement)

Mystereetbouledegomme a écrit a écrit : BOn je suis en train de regarder du cote des algos genetiques c pas sur qu'il soit plus rapide mais bon.. En fait (je commence suelement a lire l'article) ils disent que : Au debut tu generes une solution(en genetique tu aurais des cellules viables) ensuites tu evalues leur potentiel de survie via des criteres definis avant.   Ensuite tu as un nouvel ensemble de solutions et tu croises les solutions entre elle(reproduction= combinaison de l'ADN) et tu reevalue le potetniel de survie....   En gros tu joues a la selection naturel... Bon le type utilise ca pour le knapsack alors je vais lire et faire un rapport plus tard (demain surement)

 
je vois à peu près le genre d'algo. Finalement, la plupart des algos partent d'une solution et essaye de l'améliorer. Le pb, c'est qu'il faut prendre en compte le fait qu'on est pas obligé de prendre tous les fichiers passés dans la liste. De ce fait, la solution dont on part au début pour ces algos ne contient donc pas tous les fichiers. Et certains des fichiers non sélectionnés pourraient très bien faire partie de la solution optimale.
En ce qui concerne le knapsack, il ne travaille que sur un sac (ici, un cd). Il faudrait trouver une version qui travaille sur plusieurs sacs. Par contre, cet algo respecte bien la contrainte qu'on est pas obligé de prendre tous les fichiers.

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 .

Je suis d'accord avec toi wpk, l'auteur de l'article le dit parfois les algos genetiques c'est pas rapide...
Mais c'est parce que je ne vois pas tres bien comment appliquer le recuit ici. (Moi et les probas ca fait au moins 10)

Quelqu'un sur ICQ me dit que le programme "burn to the brim" permet justement de faire ce que tu as besoin rufo mais je sais pas quelle methode il utilise...

Cette discution me depasse largement.Mais ce logiciel est bien pour du mp3 et moins adapte aux autres type de fichiers(a moins de vouloir absolument remplir un cd avec uniquement des fichiers Word... ).Du moins je pense.Car si pour un logiciel qui a des repertoires/sous-repertoires il commence a retirer tel fichier pour le caser sur un autre cd, on est mal.A moins de lui dire de ne pas reorganiser l'arboressence. Mais second pb dans le cas ou un de ces logiciels necessite la presence de certains fichiers a la racine. Dans ce cas, il faut pouvoir lui indiquer tres clairement les fichiers a ignorer.
Mais, a voir le niveau de certains dans ce post,wpk pour n'en citer qu'un, je pense qu'ils ont deja pense a ce pb...

 
tu sais où le downloader?