Sommaire

Optimisation et minimums

Les problèmes d’optimisation et de recherche de minimums sont courants, et des résolutions exactes sont compliquées, voire impossibles. L’intelligence artificielle a donc mis au point des algorithmes spécifiquement pour ces problèmes.

1. Exemples

Les ingénieurs ont à résoudre de nombreux problèmes d’optimisation, comme minimiser le coût d’un objet, tout en lui conservant certaines propriétés, ou optimiser la formule d’un métal pour le rendre plus résistant.

Dans la vie courante, il y a aussi des problèmes de ce type. Payer en utilisant le moins de pièces possible (ou au contraire en essayant de passer un maximum de petites pièces) en est un exemple classique. Pour ceux qui ont des tickets restaurant, commander dans un restaurant ou acheter dans un commerce, assez pour couvrir le prix du ticket (car la monnaie n’est pas rendue dessus) mais en dépassant le moins possible en est un autre.

Charger une voiture, ranger un entrepôt, modifier une composition, déterminer un design, créer un circuit imprimé, limiter les coûts d’emballage... sont autant de problèmes d’optimisation.

2. Le problème du sac à dos

Le problème du sac à dos (ou Knapsack Problem en anglais, abrégé en KP) est simple à comprendre mais très difficile à résoudre.

Un sac à dos a une contenance maximale (sinon ...