BinPack

Fermé
krizi Messages postés 21 Date d'inscription samedi 15 novembre 2008 Statut Membre Dernière intervention 11 février 2010 - 24 nov. 2009 à 17:04
Bonjour,
salut


est ce que vous pouvez m'aider pour résoudre le pb ?

donc voilà:


Objectif: Le but du TP est de "concrétiser" la notion de propriété N P vue en cours, en particulier la notion
de certificat et d’algorithme de vérification.
Pour cela, on va travailler sur le problème de la mise en sachets, BIN P ACK , problème très classique.
Le problème est de placer un certain nombre d’objets dans un certain nombre de sacs. Les objets sont de
poids divers, chaque sac acceptant une charge maximale. La propriété -ou problème de décision - BIN P ACK
associée est définie formellement comme suit:
BIN P ACK
Donnée:
n –un nb d’objets
k –le nombre de sacs
p1 , · · · , pn – n entiers, les poids des objets
cap1 , · · · , capk – les capacités des sacs (entières)
Sortie:
Oui, si il existe une mise en sachets, i.e.:
af f : [1..n] → [1..k] – à chaque objet, on attribue un numéro de sac
qui vérifie les contraintes, i.e. telle que:
i/af f (i)=j pi ≤ capj , pour tout numéro de sac j, 1 ≤ j ≤ k. – aucun sac n’est trop chargé
Non, sinon
Exemple: Soit n = 5, x1 = 3, x2 = 2, x3 = 4, x4 = 3, x5 = 3;
si k = 3, cap1 = 5, cap2 = 6, cap3 = 4„ il y a une solution;
si k = 4, il y a une solution pour cap1 = 2, cap2 = 3, cap3 = 6, cap4 = 4 mais il n’y en a pas pour
cap1 = 2, cap2 = 2, cap3 = 6, cap4 = 6.
Note de l’auteur(e): Ce qui suit est une proposition d’architecture de classes qui essaie de correspondre le
plus possible aux notions abstraites vues en cours mais vous pouvez vous en écarter, après réflexion et discussion.
Les sources à compléter sont disponibles ici.
On définira trois classes abstraites correspondant à trois classes de problèmes de décision:
//La classe des pbs de decision
abstract class PblDec{
public abstract boolean aUneSolution();
}
//La classe ExpTime
abstract class ExpTime extends PblDec{
//algo de décision doit être exponentiel
public abstract boolean aUneSolution();
}
//La classe NP
public abstract class NP extends ExpTime{
abstract public Certificat cert(); // certificat pour le pb (notion plutot qu’objet...)
//algo exponentiel de décision de la propriété basée sur l’énumération
public boolean aUneSolution() {
Certificat cert=this.cert();
Iterator<Certificat> iterator=cert.iterator();
while (iterator.hasNext()){ //on balaye l’espace des certifcats
cert=iterator.next();
if (cert.estCorrect(this)) { cert.display(); return true;} //un certificat ua moins est c
}
return false;
}
//algo non déterministe : si il existe une solution AU MOINS UNE exécution retourne Vrai
//si il n’en existe pas TOUTES les Exécutions retournent faux!
public boolean aUneSolutionNonDeterministe() {
Certificat cert=this.cert();
cert.alea();
if (cert.estCorrect(this)) {cert.display(); return true;} else return false;
}
}
avec pour l’interface certificat:
//ce que doit au moins fournir l’objet certificat d’u pb
//iterable pour pouvoir itérer sur tous les certificats possibles pour l’instance du pb
//remove() de l’iterator ss effet;
interface Certificat<NP> extends Iterable{
public boolean estCorrect(NP pb); //retourne vrai si le certificat est juste pour le pb associé
public void alea(); //donne aléatoirement au certificat une valeur parmi celles possibles pour
public void display(); //affiche le certificat, vous pouvez aussi redéfinir toString
}
et une classe correspondant à BinP ack qui implémentera N P :
public class PblBinPack extends NP ......
Q 1.La propriété est N P .
Q 1.1.La notion formelle de certificat
Définir une notion de certificat et d’algorithme de vérification pour ce problème de décision. En déduire que
le problème de décision est bien N P .
Pour k et n fixés, combien de valeurs peut-prendre un certificat?
Q 1.2.L’implémentation
Ecrire la classe Certificat<PblBinPack>. Dans un premier temps, dans CertificatBinPack, ne pas vous
préoccuper d’Iterable et d’ alea(), mais choisir dès le départ une structure de donnée simple et adaptée qui
permettra d’écrire facilement l’itérateur!!!. Tester estCorrect() avec l’option ver du programme de test.
Q 2.N P = Non-déterministe Polynômial
Ecrire et implémenter les méthodes alea() de CertificatBinPack. Vous pouvez tester aUneSolutionNonDetermini
avec l’option nd du programme de test.
Q 3. N P ⊆ EXP T IM E
Ecrire et implémenter les méthodes iterator() de CertificatBinPacket de PblBinPack puis tester
aUneSolution() avec l’option exh du programme de test Quelle est la complexité de aUneSolution()? Si
tous les sacs avaient la même capacité, pourrait-on réduire l’espace de recherche? Cela change-t-il l’ordre de
grandeur de la complexité de l’algorithme?
Q 4.De la décision à l’optimisation On s’intéresse au problème d’optimisation avec un seul type de sac, tous de
capacité cap:
Donnée:
n –un nb d’objets
p1 , · · · , pn – n entiers, les poids des objets
cap –les capacités des sacs (entières)
Sortie: Le nombre minimum de sacs tel qu’il existe une mise en sachets possible.
Montrer que si ce problème était polynômial, le problème de décision de départ -avec des sacs ayant tous
même capacité- le serait aussi. Que dire du problème de décision avec des capacités différentes?
Comment utiliser l’algorithme de décision de la première partie - avec des sacs de capacité différente- pour
résoudre le problème? Quelle complexité aurait cette solution? Comment faire pour obtenir également la mise
en sachets?
2