dd

Un cambrioleur possède un sac à dos d'une contenance maximum de 30 kg. Au cours d'un de ses cambriolages, il a la possibilité de dérober 4 objets A, B, C et D. Voici un tableau qui résume les caractéristiques de ces objets : Objet A B C D Masse 13kg 12kg 8kg 10kg Valeur 700 400 300 300 Déterminez les objets que le cambrioleur aura intérêt à dérober, sachant que :

• tous les objets dérobés devront tenir dans le sac à dos (30 Kg maxi)
• le cambrioleur cherche à obtenir un gain maximum. Ce genre de problème est un grand classique en informatique, on parle de problème d'optimisation. Il existe toujours plusieurs solutions possibles à un problème d'optimisation (dans le problème du sac à dos, on peut choisir A+B ou A+C ou B+C+D... toutes les combinaisons sont possibles à partir du moment où la masse totale ne dépasse pas 30 Kg), mais on ne cherche pas n'importe quelle solution, on cherche une solution dite optimale : dans notre exemple on cherche le plus grand gain possible. Souvent, dans les problèmes d'optimisation, il n'existe pas une solution optimale, mais plusieurs solutions optimales, résoudre un problème d'optimisation c'est donc trouver une des solutions optimales. Il existe différentes méthodes algorithmiques permettant de trouver une solution optimale à un problème d'optimisation : il peut, en effet, être intéressant "d'automatiser" la résolution des problèmes d'optimisation à l'aide d'algorithme (dans notre cas, trouver un algorithme qui trouve une solution optimale au problème du sac à dos). En apparence, la solution la plus simple dans le cas du sac à dos serait d'écrire un algorithme qui teste toutes les combinaisons d'objets possibles et qui retient les solutions qui offrent un gain maximum. Dans notre cas précis, avec seulement 4 objets, cette solution pourrait être envisagée, mais avec un plus grand nombre d'objets, le temps de calculs, même pour un ordinateur très puissant, deviendrait trop important. En effet l'algorithme qui testerait toutes les combinaisons possibles aurait une complexité en temps en O(a n ) avec a une constante et n le nombre d'objets. On parle d'une complexité exponentielle. Les algorithmes à complexité exponentielle ne sont pas efficaces pour résoudre des problèmes, le temps de calcul devient beaucoup trop important quand n devient très grand. À la place de cette méthode "je teste toutes les possibilités", il est possible d'utiliser une méthode dite gloutonne (greedy en anglais). Qu'est-ce qu'une méthode gloutonne ? La résolution d'un problème d'optimisation se fait généralement par étapes : à chaque étape on doit faire un choix. Par exemple, dans le problème du sac à dos, nous ajoutons les objets un par un, chaque ajout d'un objet constitue une étape : à chaque étape, on doit choisir un objet à mettre dans le sac. Le principe de la méthode gloutonne est de, à chaque étape de la résolution du problème, faire le choix qui semble le plus pertinent sur le moment, avec l'espoir qu'au bout du compte, cela nous conduira vers une solution optimale du problème à résoudre. Autrement dit, on fait des choix localement optimaux dans l'espoir que ces choix mèneront à une solution globalement optimale (le "localement" signifie ici "à chaque étape de la résolution du problème"). Appliquons une méthode gloutonne à la résolution du problème du sac à dos : Sachant que l'on cherche à maximiser le gain, commençons par établir un tableau nous donnant la "valeur massique" de chaque objet (pour chaque objet on divise sa valeur par sa masse) : Objet A B C D Valeur massique 54€/kg 33€/kg 38€/kg 30€/kg On classe ensuite les objets par ordre décroissant de valeur massique : A > C > B > D Enfin, on remplit le sac en prenant les objets dans l'ordre et en s'arrêtant dès que la masse limite est atteinte. C'est ici que ce fait "le choix glouton", à chaque étape, on prend l'objet ayant le rapport "valeur-masse" le plus intéressant au vu des objectifs :
• 1ere étape : A (13 kg)
• 2e étape : C (13 + 8 = 21 kg)
• 3e étape : B (13 + 8 + 12 = 33 kg) => impossible, on dépasse les 30 Kg. Le sac est donc composé de 2 objets : A et C pour un montant total de 1000 € et une masse totale de 21 kg. Cette méthode gloutonne peut être "automatisée", il est donc possible d'écrire un algorithme glouton (un algorithme qui est basé sur une méthode gloutonne) afin de trouver une solution au problème du sac à dos avec n'importe quelles valeurs (nombre d'objets, masse des objets, valeur des objets, masse maximum). La solution trouvée ci-dessus est-elle optimale ? On constate rapidement que la réponse est non, car le couple A+B permet d'atteindre une valeur de 1100 € pour une masse de 25 Kg. Dans notre problème, la méthode gloutonne ne nous donne pas une solution optimale. Plus généralement , il est important de bien comprendre qu'un algorithme glouton ne donne pas forcément une solution optimale.