#1 Le 18/10/2008, à 23:03
- thurston
[RESOLU] Combiner x repertoires parmi y pour remplir un CD
Bonjour,
Je suis en train d'écrire un soft qui m'automatise la création de CD Mp3s pour écoute en voiture. Je prends donc y repertoires (1 repertoire = 1 album), je les passe tous à la moulinette mp3, et je me retrouve avec mes y repertoires, dont la somme représente bien plus que la capacité d'un CD.
Avez vous déjà écrit un script qui permette de déterminer quelle est la combinaison gagnante pour arriver à remplir au mieux un CD?
On parle à mon avis de prendre toutes les combinaisons possibles, de n repertoire et d'en additionner la taille, et de ne garder que la plus élevée tant qu'inférieure à 650Mb par exemple. Bien sûr, one ne connait pas n, et il faut tester n, de 1 à y, tout en n'oubliant aucune possibilité.
Je vais m'y atteler tout doucement; si vous avez déjà fait ce script, je prends, sinon, je posterai un jour, quand je serai devenu plus malin...:rolleyes:
Amitiés
Thurston
Dernière modification par thurston (Le 24/10/2008, à 16:33)
Hors ligne
#2 Le 19/10/2008, à 02:11
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
C'est un problème d'optimisation combinatoire classique qui peut se formuler sous la forme d'un programme linéaire en nombres entiers (PLNE) :
a1*x1 + a2*x2 + ... + an*xn <= N (1)
ai >= 0 qq soit 1 <= i <= n
xi >= 0, xi entiers qq soit 1 <= i <= n (2)
-----------------------------------------------------
n -> Nombre d'albums
ai -> Taille du ième l'album
xi -> Variable représentant le ième l'album
N -> Taille du CD (ex : 650 Mb)En résumé, on souhaite trouver une certaine combinaison d'albums qui maximise (1) sous les contraintes (2). La formulation de ton problème est simple mais sa résolution l'est nettement moins : lorsque n est peu élevé, ton script pourra tester chaque combinaison dans un temps raisonnable. En revanche, lorsque n devient grand, il est inconcevable d'envisager un dénombrement exhaustif puisque le nombre de solutions est égal à 2^n : la résolution d'un PLNE appartient à la classe des problèmes NP-difficiles.
Dès lors, il convient de s'orienter vers des algorithmes polynomiaux comme le simplexe ou la méthode des points intérieurs.
En pratique, pour l'algorithme du simplex, tu peux utiliser des logiciels comme SoPlex, GLPK (GNU Linear Programming Kit) ou bien lp_solve. Vu la nature de ton problème, ça ne devrait pas prendre trop de temps à résoudre. Sinon combien penses-tu avoir d'albums ?
Dernière modification par nicolas66 (Le 19/10/2008, à 02:12)
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#3 Le 19/10/2008, à 03:06
- ®om
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Ton problème est équivalent au problème du sac à dos. 
Hors ligne
#4 Le 19/10/2008, à 04:05
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Oui c'est effectivement le problème du sac-à-dos. Bah si veux t'amuser, tu peux aussi commencer par implémenter un algorithme glouton puis passer à un algorithme génétique
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#5 Le 19/10/2008, à 04:10
- ®om
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Dès lors, il convient de s'orienter vers des algorithmes polynomiaux comme le simplexe ou la méthode des points intérieurs.
En pratique, pour l'algorithme du simplex, tu peux utiliser des logiciels comme SoPlex, GLPK (GNU Linear Programming Kit) ou bien lp_solve. Vu la nature de ton problème, ça ne devrait pas prendre trop de temps à résoudre. Sinon combien penses-tu avoir d'albums ?
Juste une précision, le simplexe résoud le "problème du sac à dos relâché" (PL et non PLNE).
Et dans certains cas, la solution des 2 problèmes n'est pas la même
Hors ligne
#6 Le 19/10/2008, à 07:51
- thurston
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Oui ok, merci pour l'info, je ne connaissais pas l'expression du sac à dos.
Je pense que cela doit pouvoir s'écrire simplement en bash.
Je vais bosser dessus. J'étais plus parti sur un algorithme genetique.
A+
Thurston
Hors ligne
#7 Le 19/10/2008, à 08:17
- cep
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Je suis en train d'écrire un soft qui m'automatise la création de CD Mp3s . . .inférieure à 650Mb
Tu peux t'inspirer de datapacker :
http://www.cepcasa.info/blog/?p=154
Hors ligne
#8 Le 19/10/2008, à 12:53
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
@Rom
Oui tu as raison de préciser ^^
@thurston
Je pense que cela doit pouvoir s'écrire simplement en bash.
Bash n'est pas vraiment adapté à ce genre de chose. Perso, je te conseillerai plutôt de le faire en C ou C++ 
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#9 Le 19/10/2008, à 13:11
- thurston
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Ok, je le prends comme exercice. Ce ne sont que quelques boucles à priori, avec quelques tests d'échappement.
Je ne suis franchement pas programmeur, et je souhaite me restreindre à bash, car pas le temps de me cogner le langage C ou C++, même si pas très éloigné de bash. Je préferre mieux connaitre un langage plutot qu'un peu plusieurs.
A+
Thurston
Hors ligne
#10 Le 19/10/2008, à 15:54
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Ok pas de soucis. En tout cas, tiens-nous au courant lorsque tu auras obtenu des résultats
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#11 Le 21/10/2008, à 02:06
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
De mon côté, après avoir tâtonné un peu sur la syntaxe de GLPK, je pense avoir trouvé un truc pas mal.
Fichier du PL `albums.mod'
/******* Set *******/
set I;
/**** Parameters ***/
param size{i in I};
param N := 700;
/**** Variables ****/
var x{i in I} binary;
/**** Objective ****/
maximize profit: sum{i in I} size[i]*x[i];
/*** Constraints ***/
subject to
constraint: sum{i in I} size[i]*x[i] <= N;
end;Fichier de données `albums.dat'
/******* Data ******/
data;
set I := "Selection Naturelle",
"Amore",
"Bel Canto",
"Meteora",
"Experience",
"Diorama",
"L'air de rien",
"Le Sacre des Lemmings",
"The Fat of the Land",
"Not sokute",
"Rouge sang",
"Attache ta Tuque",
"La Radiolina",
"Thriller 2008",
"Eye to the Telescope",
"Cocoon Crash",
"All the Lost Souls",
"Back to Bedlam",
"Allo le Monde",
"Black Holes and Revelations",
"Au Milieu des Autres",
"Break Syndical",
"La Grand-Messe",
"A Plus Tard Crocodile";
param size := "Selection Naturelle" 97,
"Amore" 82,
"Bel Canto" 154,
"Meteora" 44,
"Experience" 63,
"Diorama" 79,
"L'air de rien" 80,
"Le Sacre des Lemmings" 49,
"The Fat of the Land" 78,
"Not sokute" 92,
"Rouge sang" 80,
"Attache ta Tuque" 194,
"La Radiolina" 72,
"Thriller 2008" 97,
"Eye to the Telescope" 66,
"Cocoon Crash" 69,
"All the Lost Souls" 59,
"Back to Bedlam" 91,
"Allo le Monde" 58,
"Black Holes and Revelations" 105,
"Au Milieu des Autres" 40,
"Break Syndical" 68,
"La Grand-Messe" 58,
"A Plus Tard Crocodile" 85;On exécute le solveur via :
glpsol --binarize --model albums.mod --data albums.dat --output results.txtSortie du fichier `results.txt'
Problem: albums
Rows: 2
Columns: 24 (24 integer, 24 binary)
Non-zeros: 48
Status: INTEGER OPTIMAL
Objective: profit = 700 (MAXimum)
No. Row name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 profit 700
2 constraint 700 700
No. Column name Activity Lower bound Upper bound
------ ------------ ------------- ------------- -------------
1 x['Selection Naturelle']
* 0 0 1
2 x[Amore] * 0 0 1
3 x['Bel Canto']
* 1 0 1
4 x[Meteora] * 0 0 1
5 x[Experience]
* 0 0 1
6 x[Diorama] * 0 0 1
7 x['L''air de rien']
* 0 0 1
8 x['Le Sacre des Lemmings']
* 0 0 1
9 x['The Fat of the Land']
* 0 0 1
10 x['Not sokute']
* 1 0 1
11 x['Rouge sang']
* 0 0 1
12 x['Attache ta Tuque']
* 1 0 1
13 x['La Radiolina']
* 0 0 1
14 x['Thriller 2008']
* 1 0 1
15 x['Eye to the Telescope']
* 0 0 1
16 x['Cocoon Crash']
* 0 0 1
17 x['All the Lost Souls']
* 0 0 1
18 x['Back to Bedlam']
* 0 0 1
19 x['Allo le Monde']
* 0 0 1
20 x['Black Holes and Revelations']
* 1 0 1
21 x['Au Milieu des Autres']
* 0 0 1
22 x['Break Syndical']
* 0 0 1
23 x['La Grand-Messe']
* 1 0 1
24 x['A Plus Tard Crocodile']
* 0 0 1
Integer feasibility conditions:
INT.PE: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
INT.PB: max.abs.err. = 0.00e+00 on row 0
max.rel.err. = 0.00e+00 on row 0
High quality
End of outputEn espérant que ça puisse aider
Dernière modification par nicolas66 (Le 21/10/2008, à 02:16)
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#12 Le 21/10/2008, à 07:56
- thurston
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
oui je bosse dessus avec un pote cale en informatique et on tente de faire du recursif dans le meme genre.
A bientot
Thurston
Hors ligne
#13 Le 21/10/2008, à 20:55
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Bonsoir,
Voici un script qui devrait répondre à la demande (même s'il n'est pas optimisé) :
#!/bin/ksh
DOSSIER_SOURCE="$1"
TAILLE_MAX=$2
FICHIER_RESULTAT="$3"
FICHIER_TMP=~/"$(basename $0).tmp"
# creation tableaux des noms de dossiers et tailles
INDICE=-1
find ${DOSSIER_SOURCE} -maxdepth 1 -type d|sed 1d|while read dossier
do
INDICE=$((INDICE+1))
T_DOSSIERS[${INDICE}]="${dossier}"
T_TAILLES[${INDICE}]=$(du -k "${dossier}"|tail -1|cut -f1)
done
LAST_INDICE=$((INDICE))
# indique si fin de traitement ou pas 1=fin, 0=pas fin
FinTraitement()
{
# le traitement continue s'il reste au moins un dossier dont la taille est <= à TAILLE_MAX
FIN=1
for((indice=0;indice<=${LAST_INDICE};indice++))
do
if [ -n "${T_TAILLES[${indice}]}" ]; then
# il y a une taille à cet indice, est-elle <= TAILLE_MAX
if [ ${T_TAILLES[${indice}]} -le ${TAILLE_MAX} ]; then
FIN=0
fi
fi
done
echo ${FIN}
}
# recherche de toutes les tailles possibles et les combinaisons de dossiers correspondantes avec les dossiers restants
RechercheCombinaisons()
{
indice=$1
taille=$2
chemin=$3
if [ $indice -gt ${LAST_INDICE} ]; then
# on a dépassé l'indice max, on s'arrète de chercher
[[ -n "${chemin}" ]] && echo "${taille} : ${chemin}" >> ${FICHIER_TMP}
return
fi
if [ -n "${T_TAILLES[${indice}]}" ]; then
# recherche des combinaisons avec ce dossier
taille_dossier=T_TAILLES[${indice}]
taille_suivante=$((taille+taille_dossier))
if [ -z "${chemin}" ]; then
# premier element de la combinaison
(RechercheCombinaisons $((indice+1)) ${taille_suivante} ${indice})
else
# nème element de la combinaison
(RechercheCombinaisons $((indice+1)) ${taille_suivante} "${chemin}/${indice}")
fi
fi
# recherche des combinaisons sans ce dossier
(RechercheCombinaisons $((indice+1)) ${taille} ${chemin})
}
# parmis toutes les combinaisons trouvées, recherche de la plus pertinante et écriture de celle-ci dans le fichier résultat
EcrireLaCombinaison()
{
chemin=$(awk -F\: -v max=${TAILLE_MAX} 'BEGIN {MAX=0} max >= $1 { if ($1 > MAX) {CHEMIN=$2; MAX=$1} } END {print CHEMIN} ' ${FICHIER_TMP})
echo "Combinaison $1 :" >> ${FICHIER_RESULTAT}
echo ${chemin}|awk -F\/ '{ for (indice=1;indice<=NF;indice++){print $indice}}'|while read INDICE
do
echo "${T_DOSSIERS[${INDICE}]}" >> ${FICHIER_RESULTAT}
# on "supprime" le dossier des tableaux car il a été utilisé pour une combinaison
unset T_DOSSIERS[${INDICE}]
unset T_TAILLES[${INDICE}]
done
}
[[ -f ${FICHIER_RESULTAT} ]] && rm -f ${FICHIER_RESULTAT}
# tant que l'on a pas atteint la fin, on effectue le traitement de recherche
NUM_COMBINAISON=0
while [ $(FinTraitement) -ne 1 ];
do
[[ -f ${FICHIER_TMP} ]] && rm -f ${FICHIER_TMP}
NUM_COMBINAISON=$((NUM_COMBINAISON+1))
# on recherche toutes les combinaisons possibles avec les dossiers restants
RechercheCombinaisons 0 0 ""
# recherche résultat le plus pertinant
EcrireLaCombinaison ${NUM_COMBINAISON}
doneEDIT :
param1 = dossier parent des dossiers mp3
param2 = taille max en ko
param3 = fichier résultat des combinaisons
Dernière modification par Totor (Le 21/10/2008, à 21:50)
-- Lucid Lynx --
Hors ligne
#14 Le 21/10/2008, à 21:54
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Ton algo implémente une recherche exhaustive ou pas ? Quel est le temps d'exécution pour 30 albums ?
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#15 Le 21/10/2008, à 22:44
- thurston
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Merci pour le scrip totor. Il y a un truc qui ne marche pas chez moi, mais je vais regarder un peu en détail.
(quand je lance le script aucune action, ni fichier résultat créé).
A+
Thurston
Hors ligne
#16 Le 22/10/2008, à 08:43
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Ton algo implémente une recherche exhaustive ou pas ? Quel est le temps d'exécution pour 30 albums ?
Oui, la recherche est exhaustive.
30 albums... je n'en sais rien ! je n'en ai pas autant 
En fait, je n'ai pas fait de tests de métrologie car l'objectif était de fournir un script fonctionnel.
Et puis tout dépend de sa machine, j'ai un AMD Phenom 9950... donc plutôt rapide...
-- Lucid Lynx --
Hors ligne
#17 Le 22/10/2008, à 08:43
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Merci pour le scrip totor. Il y a un truc qui ne marche pas chez moi, mais je vais regarder un peu en détail.
(quand je lance le script aucune action, ni fichier résultat créé).
A+
Thurston
Huuuum, si pas de fichier résultat créé, c'est qu'il ne trouve pas de combinaison et donc qu'il ne trouve pas au moins un dossier dont la taille est <= TAILLE_MAX (soit 650Mo : 650*1024 = 665600 ko)
Dernière modification par Totor (Le 22/10/2008, à 09:01)
-- Lucid Lynx --
Hors ligne
#18 Le 22/10/2008, à 09:14
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Oui, la recherche est exhaustive.
30 albums... je n'en sais rien ! je n'en ai pas autant wink En fait, je n'ai pas fait de tests de métrologie car l'objectif était de fournir un script fonctionnel.
Comme je l'ai indiqué dans un post précédent, la recherche exhaustive est à bannir lorsque n augmente. Exemple : n=30 => 2^30=1073741824 ... A partir de ce que j'ai donné, ya moyen de faire un script pr remplir le fichier de données et récupérer la solution automatiquement pour graver le CD direct.
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#19 Le 22/10/2008, à 09:47
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
et bien, je te dirais ce soir combien de temps ça met avec 30 dossiers (j'ai pô d'albums !)
-- Lucid Lynx --
Hors ligne
#20 Le 22/10/2008, à 11:52
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Voire même avec n=50 pour voir
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#21 Le 22/10/2008, à 23:02
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
bon bah big pb...:/
j'ai une erreur de segmentation dès la 34867ème combinaison....:rolleyes:
-- Lucid Lynx --
Hors ligne
#22 Le 22/10/2008, à 23:10
- thurston
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Bizarre ca marche pas du tout pour moi.
J'ai collé une dizaine d'albums mp3 dans le repertoire /home/thurston/script, où j'ai également installé ton script
que j'ai nommé rangedir, avec les permissions d'execution, puis je me mets dans le repertoire avec un terminal, et je lance
./rangedir ./ 665600000 ./resultet que dalle...
??
A+
Thurston
Dernière modification par thurston (Le 22/10/2008, à 23:12)
Hors ligne
#23 Le 23/10/2008, à 01:13
- nicolas66
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
j'ai une erreur de segmentation dès la 34867ème combinaison....
Bah tu m'étonnes, surtout que je viens de voir que tu recherchais les combinaisons récursivement
Clairement, mieux vaut s'orienter vers des heuristiques simples dans un premier temps. Un algorithme glouton donnera peut-être de bons résultats :
* Trier les albums par taille de manière décroissante
* Pour chaque album
* Si la taille totale + taille de l'album <= 650Mo
* Augmenter la taille totale
* Ajouter l'album à la liste résultat
* FinSi
* FinPour
"The computer was born to solve problems that did not exist before." (B. Gates)
Hors ligne
#24 Le 23/10/2008, à 08:39
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Certe, mais cela ne répond pas à la demande qui est :
Avez vous déjà écrit un script qui permette de déterminer quelle est la combinaison gagnante pour arriver à remplir au mieux un CD?
par ailleurs, j'ai été confronté à un problème de limite numérique du shell ....
-- Lucid Lynx --
Hors ligne
#25 Le 23/10/2008, à 08:39
- Totor
Re : [RESOLU] Combiner x repertoires parmi y pour remplir un CD
Bizarre ca marche pas du tout pour moi.
J'ai collé une dizaine d'albums mp3 dans le repertoire /home/thurston/script, où j'ai également installé ton script
que j'ai nommé rangedir, avec les permissions d'execution, puis je me mets dans le repertoire avec un terminal, et je lance./rangedir ./ 665600000 ./resultet que dalle...
??
A+
Thurston
as-tu regardé le contenu du fichier ./result ?
-- Lucid Lynx --
Hors ligne