Fiou, voilà, ça y’est, je viens de rendre mon rapport sur l’études des algorithmes et heuristiques permettant de résoudre le problème du Sac à Dos, connu sous le nom anglophone de Knapsack et abrégé en Max-KS. Mais qu’est ce que ?

Projet de Complexite sur Open Office

Open Office a révolutionné les solutions concurrentes à Microsoft Office en étant le premier à souligner en rouge les mots correctement orthographiés !

En Informatique, l’une des matières que nous étudions se nomme la Complexité. Cela consiste, grosso modo, à étudier la difficulté, ou plutôt la complexité, de problèmes que nous souhaiterions résoudre en Informatique. Je ne m’étendrais pas plus là dessus et je vous invite à lire les articles que peuvent fournir Wikipedia si vous souhaitez de plus amples explications. Mais rien n’est moins sûr que la comprehension d’un néophite à la lecture de ces pages.

Toujours est il donc que le Sac à Dos fait parti des problèmes qui sont les plus difficiles (on parle de NP-complet) à résoudre. Cette difficulté est plus ou moins estimée en fonction du temps nécessaire à résoudre le problème, NP pour Non-Deterministe Polynomial. Je ne vous expliquerai pas pourquoi, puisqu’avant ça il vous faudrait connaître la Machine de Turing, ainsi que la théorie des automates non déterministes. Bref le problème du Knapsack est donc exprimé de telle façon:

Soit un ensemble d’objets, chaque objet a un poids et une valeur déterminée. On souhaite remplir un sac d’objets, le poids total ne doit pas dépasser B et la valeur totale des objets doit être maximisée.

Donc si j’ai un sac de poids maximum 2, et que j’ai 3 montres qui ont chacune un poids de 1, mais pas les mêmes valeurs, je vais prendre les deux qui ont le plus de valeur. Pour deux objets, c’est plutôt facile, le cerveau humain faisant implicitement la comparaison de toutes les combinaisons possibles. Mais lorsque l’on se retrouve face à 30 objets de poids et valeurs différentes ? 300 ? 30000 ? voir un million ?

Execution du Recuit Simulé pour le Knapsack

Un article par algorithme avec des superbes graphes ! Ca fait envie !

Bref, c’est donc le thème que je me farcie depuis maintenant quelques jours, et pour lequel j’ai implémenté quatre algorithmes différents que j’ai ensuite fait tourner sur plusieurs échantillons différents. Un algo exact, nommé Branch and Bounds, deux algorithmes approximatifs, celui du Glouton (Greedy Algorithme) et celui du PTAS pour Polynomial-time approximation scheme, puis l’Heuristique du Recuit Simulé.

Waw, ça vous fait envie hein ? Pas de problème, je m’étendrais en long, large et travers sur chacune de ces implémentations. Pourquoi ? Parce que je n’ai pu trouver aucune source qui soit compréhensible et ça m’a bien ennuyé ! Et comme mon travail ne servira à rien sinon, autant que d’autres étudiants trouvent mes articles pour les aiguiller.

Et pour vous récompenser d’avoir tout suivi, la publication de mon superbe projet, histoire de pouvoir lire une vingtaine de fois les phrases « on constate sur ce graphe » et « on peut voir sur ce graphe ». Wahou, sur if is Dead on sait comment gagner son lectorat !

Avant de vous donner les solutions, vous, vous feriez comment pour résoudre le problème du Sac à Dos ? (expliquez vous en français, c’est tout à fait compréhensible, pas besoin d’être informaticien pour faire une méthode algorithmique !)


Ces articles pourraient aussi vous intéresser:
3 Comments, donnez votre avis !
  • illman a écrit le 25 novembre 2009 à 9 h 22 min:

    Chacal de troller d’Open Office

    RépondreRépondre
  • greg a écrit le 13 mai 2010 à 15 h 09 min:

    Salut, ton projet m’interresse, pourrait tu le publier ?

    RépondreRépondre
  • Yves Remords a écrit le 29 janvier 2012 à 14 h 18 min:

    Merci pour ce petit article simple et de bon goût, qui me fait comprendre l’enjeu du problème du Sac à Dos. Ça m’est utile pour mon étude sur l’histoire de l’informatique et des « maths discrétes ».
    Je crois saisir que le problème du Sac à Dos est un joli problème d’optimisation : vous devriez donc le vendre, très cher, aux communicants de Hollande et de Sarko. Ils croiront que c’est un logiciel pour rendre les Français optimistes.
    Personnellement, je le résous comme Alexandre résolut le problème du nœud gordien :
    – Je n’ai pas de montre,
    – je ne voyage pas avec un sac à dos, mais avec trois malles-cabines. Car les smokings se froissaient dans mon Lafuma.
    Mille bises et tous mes encouragements à ifisDead.
    YR

    RépondreRépondre
  • Donnez votre avis !

    Comment avoir son avatar sur ifisDead ?