Discussion :

[cochemar_bin_packing]

Salut à tous, je doit implémenter en C une "solution optimale" pour le problème du bin packing j'ai fait des méthodes "classic" pour commencer genre le first fit et le best fit. mais pour l'optimisation j'aurai besoin d'énumérer toutes les solutions possible afin de prendre la meilleur.
Esce que quelqu'un pourrais m'aider a trouver un algo (récursif) qui ferai ça???
Merci d'avance

[pseudocode]

Une exploration complète de l'arbre des solutions, ca va être énorme !

Il faut trouver des critères pour arrêter l'exploration au plus tôt. Sinon ca va pas être gérable.

[cochemar_bin_packing]

Oui c'est sur. mais au fait dans un premier temps j'aurai besoin d'enumerer les solutions sans utiliser un arbre... j'ai pensé à un tableau binaire mais je sais pas comment faire...
http://dept-info.labri.fr/ENSEIGNEME...in-packing.pdf voila le lien vers le probleme; c'est surtout la methode exacte qui m'interesse...
Merci pour ton aide

[pseudocode]

Ton document explique qu'il faut faire une exploration de l'arbre.

- Le premier élément est assigné arbitrairement au sac 1 : X[1]=1.

- On explore alors les solutions possibles pour l'élement #2 :
--> dans le sac #1
--> dans un nouveau sac #2
pour chacune de ces 2 possibilités, on explore les solutions possibles pour l'élement #3

Ca peut se faire facilement par recursion:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
 
DEBUT explorer(#i)
 
	Pour chaque sac #s
		si l'element #i rentre dans le sac #s alors
			affecter #i à #s
			explorer(#i+1)
			retirer #i de #s
		fin si
	Fin Pour
 
	Créer un nouveau sac #s
	affecter #i à #s
	explorer(#i+1)
	retirer #i de #s
	Supprimer le nouveau sac #s
 
FIN

Il est recommandé de limiter la création de nouveaux sacs. Par exemple, si on a déjà trouvé une solution avec K sacs, c'est inutile de tester une solution avec K+1 sacs. Elle sera forcément moins bonne.

[cochemar_bin_packing]

Oui je vois maintenant comment ça marche. Au niveau algorithmique je sais maintenant comment on peut faire, mais pour programmer tout ça je me demandez s'il avait un moyen pour que je n'utilise pas un arbre? parce que j'utilise trois structure donc je m'y perd un peu quand je dois manupuler un arbre ...

voila mes structures:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
struct objet
{
  char* nom;
  float poids;
};
 
struct sac
{
  int nb_objet; /* =======> initialisé à 0... puis a chaque qu'on ajoute un objet on fais +1 */
  float poids_courant;
  objet *listeObjet; /* ==>>c'est genre un "tableau" d'objet dans lequel je peux avancer pour avoir les infos sur les objet qui sont dans le sac...*/
};
 
struct containeurSac 
{
  sac * listeDeSac; /*==>il permet d'acceder aux sac du container et de "voir" leur contenu */
 
  int nombre_sac; /* ==> initialisé à 0 et nous donne le nombre de sac utilisé... */
};

Encore merci pour ton aide

[pseudocode]

Oui je vois maintenant comment ça marche. Au niveau algorithmique je sais maintenant comment on peut faire, mais pour programmer tout ça je me demandez s'il avait un moyen pour que je n'utilise pas un arbre? parce que j'utilise trois structure donc je m'y perd un peu quand je dois manupuler un arbre ...

L'arbre ca représente l'espace des solutions a explorer : on doit faire des choix qui nous conduisent à d'autre choix, etc. Bref ca forme un arbre de solutions.

Dans le code, on ne manipule pas un arbre au sens "structure de données" (noeud, feuille). On ne fait qu'explorer l'arbre. On n'a donc besoin que d'une pile qui contient les choix (= les noeuds) qu'on a choisi d'explorer. Cette pile nous permet de revenir en arrière dans nos choix, et d'en faire d'autres.

Le plus simple c'est de faire un algo recursif car, dans ce cas, la pile est gérée automatiquement par le langage (appels de fonctions).