TD d’algorithmique avancée
Heuristique de rangement Cette page traite de l'heuristique de rangement, une méthode utilisée pour minimiser le nombre de boîtes nécessaires pour ranger des objets de tailles variées. Vous découvrirez son fonctionnement, des démonstrations mathématiques, des exemples d'application, ainsi qu'une implémentation de l'algorithme Fischer-Price.
D'après le document TD d’algorithmique avancée
Cet article a été rédigé automatiquement à partir du document source, puis vérifié avant publication.
Document source
Algorithmique, NP-complet, Heuristique · PDF · 2 pages
Afficher l'aperçu du document
Heuristique de rangement
Cette page traite de l'heuristique de rangement, une méthode utilisée pour minimiser le nombre de boîtes nécessaires pour ranger des objets de tailles variées. Vous découvrirez son fonctionnement, des démonstrations mathématiques, des exemples d'application, ainsi qu'une implémentation de l'algorithme Fischer-Price.
Présentation du problème de rangement
Nous avons n objets, où le ième objet a une taille si avec 0 < si < 1. L'objectif est de ranger ces objets dans des boîtes de taille unitaire, de manière à utiliser le minimum de boîtes possible. Chaque boîte peut contenir un sous-ensemble des objets tant que la somme de leurs tailles n'excède pas 1. Ce problème est classé comme NP-complet.
Heuristique Fischer-Price
Pour résoudre ce problème, on utilise l'heuristique Fischer-Price. Cette méthode consiste à prendre les objets un par un et à placer chaque objet dans la première boîte qui peut l'accueillir. On note S la somme des tailles des objets :
S = ∑i=1n si.
Démonstration du nombre de boîtes nécessaires
Nous allons démontrer que le nombre optimal de boîtes nécessaires est au moins égal à ⌈S⌉. En effet, les boîtes doivent contenir une taille totale S d'objets. Étant donné que chaque boîte a une capacité de 1, il faut au moins ⌈S⌉ boîtes pour contenir les objets.
Propriétés de l'heuristique Fischer-Price
Nous allons montrer que l'heuristique Fischer-Price laisse au plus une boîte remplie à moins de la moitié. Supposons qu'il existe au moins deux boîtes, notées A et B, qui sont remplies à moins de la moitié. En supposant que la boîte A a été remplie avant la boîte B, le premier objet ajouté à la boîte B, noté x, doit avoir une taille inférieure à 1/2. Cela implique que la boîte A était remplie à moins de la moitié lorsque x a été ajouté à B, ce qui contredit la définition de l'heuristique.
Analyse de la complexité de l'heuristique
Nous allons examiner la complexité de l'heuristique Fischer-Price. La première boucle de l'algorithme comporte n itérations, et la boucle "tant que" peut s'exécuter au plus ⌈2S⌉ fois. Ainsi, la complexité de l'algorithme est en O(nS). On peut également noter que S ≤ n, ce qui donne une complexité en O(n²) dans le pire des cas.
Implémentation de l'heuristique Fischer-Price
Fischer-Price(s)
b ← 0
Pour i ← 1 à n faire
j ← 1
tant que j ≤ b et si + taille[j] > 1 faire j ← j + 1
si j ≤ b alors
taille[j] ← taille[j] + si
sinon
b ← b + 1
taille[b] ← si
Points clés à retenir
Voici les principaux points à retenir concernant l'heuristique de rangement :
- Le problème de rangement est NP-complet.
- L'heuristique Fischer-Price permet de minimiser le nombre de boîtes nécessaires.
- Le nombre de boîtes utilisées par l'heuristique est au plus égal à ⌈2S⌉.
- La complexité de l'heuristique est en O(nS) et peut être en O(n²) dans le pire des cas.
Questions fréquentes
Qu'est-ce que l'heuristique de rangement ?
L'heuristique de rangement est une méthode permettant de minimiser le nombre de boîtes nécessaires pour ranger des objets de tailles variées. Elle s'applique à des problèmes où les objets doivent être placés dans des conteneurs de taille fixe.
Comment fonctionne l'heuristique Fischer-Price ?
L'heuristique Fischer-Price fonctionne en prenant chaque objet un par un et en le plaçant dans la première boîte disponible qui peut l'accueillir, jusqu'à ce que tous les objets soient rangés.
Quelle est la complexité de l'heuristique Fischer-Price ?
La complexité de l'heuristique Fischer-Price est en O(nS), où n est le nombre d'objets et S la somme des tailles des objets. Dans le pire des cas, cette complexité peut être réduite à O(n²).
Combien de boîtes sont nécessaires au minimum ?
Le nombre minimum de boîtes nécessaires est au moins égal à ⌈S⌉, où S est la somme des tailles des objets. Cela signifie qu'il faut au moins autant de boîtes que la taille totale des objets divisée par la capacité d'une boîte.
Peut-on donner un exemple d'application de l'heuristique ?
Un exemple d'application de l'heuristique Fischer-Price serait de ranger des objets de tailles 0.3, 0.5 et 0.2. En utilisant l'heuristique, on placerait 0.3 et 0.5 dans une boîte, et 0.2 dans une autre, nécessitant ainsi deux boîtes au total.
Commentaires
Aucun commentaire pour le moment. Posez la première question.