Bin packing : algorithme pour énumerer toutes les solutions

Version imprimable

30/01/2010, 19h20
cochemar_bin_packing

Bin packing : algorithme pour énumerer toutes les solutions

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
01/02/2010, 15h40
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. :?
01/02/2010, 16h25
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:)

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:

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.

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:

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

01/02/2010, 19h25
pseudocode

Citation:

Envoyé par 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 :(...

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

Ben j'ai essayé d'ecrire une fonction recursive mais elle marche pas, pourtant j'ai fait que traduire l'algo que tu m'as donné ben afin je crois:?:?:?

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
 
bool egalite_objet(objet o1, objet o2)
{
  int cmp_nom = strcmp(o1->nom,o2->nom);
  return o1->poids == o2->poids && cmp_nom == 0; 
}
 
 
 
static int chercher_indice(sac s, objet o)
{
  for(int i = 0; i<s->nb_objet; i++)
    if(egalite_objet(s->listeObjet[i],o))
      return i;
  return -1;
}
 
void enlever_objet(sac s, objet o)
{
  s->poids_courant -= o->poids;
  s->nb_objet -= 1;
  int i = chercher_indice(s,o);
  (s->listeObjet[i]) = NULL;
}
 
void enlever_sac(containeurSac c, sac s)
{
  c->nombre_sac -= 1;
  (c->listeDeSac[c->nombre_sac-1]) = NULL;
}
 
 
 
void recursif(objet tab_objet[], containeurSac c, int i, int nb_sac_max, float POIDS_LIMITE)
{
  for(int j =0; j < c->nombre_sac; j++)
    {   
      if(ajout_possible_dans_sac(c->listeDeSac[j],tab_objet[i],POIDS_LIMITE))
	{
	  ajouter_objet_dans_sac(c->listeDeSac[j], tab_objet[i]);
	  recursif(tab_objet, c, i+1, nb_sac_max, POIDS_LIMITE);
	  enlever_objet(c->listeDeSac[j], tab_objet[i]);
	}
    }
  if(c->nombre_sac < nb_sac_max)
    {
      ajouter_sac_containeurSac(c);
      recursif(tab_objet, c, i+1, nb_sac_max, POIDS_LIMITE);
      enlever_objet(c->listeDeSac[i], tab_objet[i]);
      enlever_sac(c, c->listeDeSac[c->nombre_sac-1]);
    }
}

1ere remarque : il faut penser a "sortir" de l'appel recursif. A force d'explorer l'élément suivant, tu vas finir par arriver au bout de la liste des éléments. :aie:

2nde remarque : ca me parait bien compliqué de travailler avec des listes chainées. Ton document PDF suggère de passer par un tableau qui contient les affectations #element/#sac. Ca me parait plus simple. ;)

Exemple d'implémentation:

Code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
 
int N=7; // Nb d'elements
int[] P={3, 4, 4, 3, 3, 2, 1}; // poids des éléments
int Pmax=10; // le poids max d'un Sac
 
int SacLimit = N; // limite du nombre de sacs (au pire : un par element)
int SacMax = 0; // Nb de sacs utilisés
int[] S = new int[SacLimit]; // poids de chaque sac
 
int[] X = new int[N]; // les affectations element/sac
 
void resoudre() {
	// force l'affectation du 1er element au 1er sac
	creerNouveauSac();
	affecter(0,0);
 
	// exploration recursive
	explore(1);
}
 
void explore(int i) {
	if (i>=N) { // sortie de la recursion
		if (SacMax<SacLimit) { // nouvelle solution, meilleure que la precedente
			SacLimit=SacMax;
			System.out.println(Arrays.toString(X));
		}
		return;
	}
 
	// met l'element dans chaque sac, et explore l'element suivant 
	for(int s=0;s<SacMax;s++) {
		affecter(i,s);
		if (S[s]<=Pmax) explore(i+1);
		retirer(i,s);
	}
 
	// met l'element dans un nouveau sac
	creerNouveauSac();
	if (SacMax<SacLimit) {
		affecter(i,SacMax-1);
		explore(i+1);
		retirer(i,SacMax-1);
	}
	SupprimerNouveauSac();
}
 
// fonctions utilitaires
void creerNouveauSac() { SacMax++; S[SacMax-1]=0; }
void SupprimerNouveauSac() { SacMax--; }
void affecter(int i, int s) { X[i]=s;  S[s]+=P[i]; }
void retirer(int i, int s)  { X[i]=-1; S[s]-=P[i]; }

02/02/2010, 20h50
cochemar_bin_packing
Salut j'ai adapté ton code à ma structure mais j'ai pas eu le temps de le tester.

Au fait je n'ai pas compris cette partie du code:
Code:

1 2 if (SacMax<SacLimit) { // nouvelle solution, meilleure que la precedente SacLimit=SacMax;
c'est quoi le SacLimit et le sacMax ???je m'y perd un peu au fait.
Parce que si SacMax est initialisé a 0. le "if" sera toujours vrai et je vois mal comment on pourrait mettre SacLimit à 0 (SacLimit=SacMax;).
Je crois qu'il y a quelque chose qui va pas...:?
03/02/2010, 09h32
pseudocode

Citation:

Envoyé par cochemar_bin_packing

c'est quoi le SacLimit et le sacMax ???je m'y perd un peu au fait.
Parce que si SacMax est initialisé a 0. le "if" sera toujours vrai et je vois mal comment on pourrait mettre SacLimit à 0 (SacLimit=SacMax;).
Je crois qu'il y a quelque chose qui va pas...:?

SacMax c'est le nombre de sac utilisé actuellement (= lors de l'exploration de "cette" solution).

Comme notre algorithme a la possibilité de "creer" des nouveaux sacs, il faut lui fixer une limite, sinon il va explorer des solutions avec 5548721 sacs pour voir si elles sont valides :P. SacLimit représente le nombre "maximum" de sac que l'algorithme est autorisé a créer. Au départ, il faut bien sur que ce nombre soit assez grand pour trouver au moins une solution. J'ai choisi de prendre SacLimit=N, car je suis sur que c'est une solution au problème (1 sac pour chaque element).

Le "if (SacMax<SacLimit)" n'est testé que dans le cas "if (i>=N) " ;). C'est à dire uniquement lorsqu'on a terminé la recursion, et donc trouvé une solution valide. Auquel cas, on regarde si cette "nouvelle" solution utilise moins de sac que la limite actuelle. Si c'est le cas, alors cette "nouvelle" solution est meilleure que la limite... et donc elle devient la nouvelle limite.
03/02/2010, 22h57
Pouet_forever

Comme déjà dit, je pense que la solution la plus simple, et la moins coûteuse en mémoire (pour pas dire la plus rapide), est la programmation dynamique !
Revois le lien que je t'ai donné, la solution est dedans (à quelques modifications près).
30/04/2012, 04h38
lamoye

bonjour a tous,je travaille sur un problème de découpe ( bin packing 2D)
le problème s'énonce comme suit!
on dispose de plaques mères de 48x96 dm
on doit découper à partir des plaques mères: 8 plaques de 36x50 dm
13 plaques de 24x36 dm
5 plaques de 20x60 dm
15 plaques de 18x30 dm

les découpes doivent etre satisfaites tout en minimisant le nombre de plaques mères utilisées ainsi que la chute de matière.
j'aimerai savoir comment faire pour énumérer les différents plans de coupe possibles pour modéliser ce problème sous forme de programme linéaire en nombres entiers.
merci d'avance pour votre aide!