#1 Le 11/02/2008, à 23:30
- wlourf
[bash] cette fonction existe-t-elle : valeur cible
Bonsoir !
J'ai parcouru le guide bash mais je ne troure pas cette fonction, j'ai peur qu'elle n'existe pas.
Voici ce que je souhaite :
J'ai une liste de x nombres et je voudrais connaitre la combinaison qui se rapprochera le plus d'une valeur cible y, sans la dépasser.
J'ai peur que si cette fonction n'existe pas, il faille créér des boucles pour calculer ça (cette fonction existe dans Calc mais je souhaite utiliser un script).
Le but avoué de cet exercice est d'optimiser le choix de dossiers (disons 20 Mo à 500 mo) à graver sur un CD pour perdre le moins de place possible.
Merci de vos avis éclairés 
Dernière modification par wlourf (Le 12/02/2008, à 00:17)
Hors ligne
#2 Le 11/02/2008, à 23:42
- Chaussette
Re : [bash] cette fonction existe-t-elle : valeur cible
salut,
si tu veux faire bien les choses je crois qu' il se cache derrière ce petit problème un petit chalenge algorithmique avec un bon gros paquet d' algèbre en vrac.
Je doute aussi qu' il existe une fonction toute faite. Et oui ça me fait aussi beaucoup penser au chiffre et les lettres dans l' exercice du calcul, l' ordinateur chargé de donner la meilleure solution passes par le même genre d' algorithme.
Ca va être intéressant ;°)
Les clowns se marient en grande pompes
Hors ligne
#3 Le 11/02/2008, à 23:48
- BERGUERAND
Re : [bash] cette fonction existe-t-elle : valeur cible
bonsoir,
dans un script tu peux utiliser bc: $man bc; il y a aussi quelques exemples dans /usr/share/doc/bc
Alain
Hors ligne
#4 Le 11/02/2008, à 23:50
- kaer
Re : [bash] cette fonction existe-t-elle : valeur cible
Je te suggére de réfléchir aux questions suivantes:
- est-ce que tu veux faire un seul CD (et tant pis pour les dossiers qui n'y vont pas) ou plusieurs CD et alors c'est le nombre de CD que tu voudras sans doute minimiser (ce qui revient à la place perdue totale)
- si c'est un seul CD, est-ce que tous les répertoires ont le même poids ou certains sont-ils plus importants ?
- cherches-tu l'optimum absolu ou une bonne approximation ? Dans le premier cas, il faudra utiliser des techniques de recherche opérationelle et je doute qu'un script ne puisse le résoudre. A moins bien sûr qu'il n'utilise un appel à des programmes spécialisés. Et là , je passe la mains aux spécialistes ...
Hors ligne
#5 Le 12/02/2008, à 00:13
- Chaussette
Re : [bash] cette fonction existe-t-elle : valeur cible
"il faudra utiliser des techniques de recherche opérationelle" youpii ^^
On est la pour s' amuser non !
Les clowns se marient en grande pompes
Hors ligne
#6 Le 12/02/2008, à 00:25
- wlourf
Re : [bash] cette fonction existe-t-elle : valeur cible
ok, bon c'est pas simple en effet mais ce n'est pas ça qui va m'arrêter puisque dans une autre vie j'arrivai à un résultat avec des macros Excel, ce n'était peut-être pas rapide mais j'arrivais à un résultat... je vais essayer de remettre la main sur ce fichier pour m'inspirer !
sinon :
est-ce que tu veux faire un seul CD (et tant pis pour les dossiers qui n'y vont pas) > oui
les répertoires ont le même poids ou certains sont-ils plus important > les tailles varient de 50 à 500 Mo ou plus lorsque c'est pour des DVD
un rapide coup d'oeil à bc me laisse perplexe étant donné mes faibles connaissances!
Dernière modification par wlourf (Le 12/02/2008, à 00:32)
Hors ligne
#7 Le 12/02/2008, à 00:36
- Chaussette
Re : [bash] cette fonction existe-t-elle : valeur cible
non !!
passes par là : http://fr.wikipedia.org/wiki/Branch_and_bound
C' est loin d' être magistral mais c' est très intéressant, tu va comprendre pourquoi. Je pense que ton problème est un classique, reste à trouver l' application mathématique précise et l' implémenter en bash, mais en C serait plus rapide. (temps de calcul très long)
Je n' ai pour ainsi dire aucune connaissance ne mathématiques, juste des intuitions et des sensibilités dans l' algo. Bref le sujet m' intéresse. :°)
Les clowns se marient en grande pompes
Hors ligne
#8 Le 12/02/2008, à 02:21
- Chaussette
Re : [bash] cette fonction existe-t-elle : valeur cible
Bon en fait ce ne serait pas tellement compliqué vu qu' il ne s' agit que d' explorer un arbre de recherche.
Je propose un algorithme simplifié pour le moment.
On considère que pour arriver plus vite aux feuilles de l' arbre (bien qu' il n' y ai pas nécessité de chemin le plus court, mais seulement pour accéléré la recherche) il faut mettre les fichiers les plus gros en premier (d' intuition).
N1 est le plus gros fichier , N2 le suivant etc...
Le nombre de fichier total est Nmb
E est l' espace disponible.
On considère une variable d' optimisation qui définie un espace inutilisé de taille convenable, pour une solution non absolue mais convenable, et à terme il faudrait pouvoir s' en passer : C
Il y à trois types de solutions : absolu ( le programme s' arrête ) convenable ( demande d' arrêt ) alternative ( toutes les autres solutions )
La première partie du programme se charge aisément de trier tout les fichiers par taille dans une liste.
La fonction F est récursive et prend comme argument E :
F (E) :
s' il existe un fichier tel que Nx = E, noter cette solution comme une solution absolue, arrêt.
s' il existe C > E, noter cette solution comme convenable , proposer l' arrêt.
sinon noter cette solution comme alternative.
si le fichier Nx est supérieur à E
augmenter x ( jusqu' à trouver un fichier de plus petite taille à caser )
si x = Nmb ( on arrive à la fin sans avoir trouvé de plus petit fichier )
reprendre à partir de la solution précédente et mettre à jour x ( on remonte dans l' arbre )
remplacer le dernier fichier Nx de cette solution par Nx+1 ( on diminue la taille du rameau )
réévaluer E
fin
fin
Remplir E avec Nx
Réévaluer E
F (E)
fin de la fonctionS' il n' y à pas d' erreur l' implémentation ne comporte aucune difficulté.
Il y à surement une meilleure méthode que de rajouter des fichiers jusqu' à ce qu ça coince avant de changer de rameau mais je pense que ça devrait faire l' affaire. A noter que cet algorithme n' explore pas du tout toutes les possibilité*. A vos idées !
* : en fait si, elle sont toutes là ! Et après réflexion c' est algo est variment très optimisé , on ne peut pas faire grand chose d' autre que de ruser dans l' implémentation.
Dernière modification par Chaussette (Le 12/02/2008, à 19:26)
Les clowns se marient en grande pompes
Hors ligne