Aller au contenu

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

TD d’algorithmique avancée

Algorithmique, NP-complet, Heuristique · PDF · 2 pages

Afficher l'aperçu du document

Consulter le document original →

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.

Partager

Commentaires

Aucun commentaire pour le moment. Posez la première question.

Les commentaires sont relus avant publication. Votre e-mail n'est jamais affiché.

← Toutes les révisions