Algorithmes Gloutons

Introduction aux Algorithmes Gloutons

Les algorithmes gloutons sont simples et intuitifs. Ils fonctionnent en faisant le choix qui semble le meilleur à chaque étape, sans jamais revenir en arrière pour réévaluer les choix précédents. Cette approche peut ne pas toujours conduire à la solution optimale globale, mais elle est souvent efficace et rapide.

Caractéristiques des Algorithmes Gloutons

1. Choix Glouton : À chaque étape, un choix est fait qui semble être le meilleur à ce moment-là.

2. Optimalité Locale : Le choix fait à chaque étape est localement optimal.

3. Pas de Retour Arrière : Une fois un choix fait, il n'est jamais réévalué ou changé.

4. Efficacité : Les algorithmes gloutons sont généralement plus rapides que d'autres approches, comme la programmation dynamique.

Exemples de Problèmes Résolus par des Algorithmes Gloutons :

1. Problème de la Monnaie : Trouver le nombre minimum de pièces nécessaires pour faire une certaine somme d'argent.

2. Problème du Rendu de Monnaie : Similaire au problème de la monnaie, mais avec des pièces de valeurs spécifiques.

3. Problème du Sac à Dos Fractionnaire : Maximiser la valeur des objets dans un sac à dos avec une capacité limitée, où les objets peuvent être divisés.

4. Problème de l'Ordonnancement d'Intervalles : Sélectionner le nombre maximum de tâches qui ne se chevauchent pas.

Exemple : Problème de la Monnaie

Problème : Trouver le nombre minimum de pièces nécessaires pour faire une certaine somme d'argent, en utilisant des pièces de valeurs données.

Approche Gloutonne :

1. Commencez par la pièce de la plus grande valeur.

2. Utilisez autant de pièces de cette valeur que possible sans dépasser la somme restante.

3. Répétez le processus avec la pièce de la valeur suivante jusqu'à ce que vous atteigniez la somme exacte.

Exemple : Supposons que vous avez des pièces de valeurs [25, 10, 5, 1] et que vous voulez faire une somme de 36 cents.

• Utilisez une pièce de 25 cents. Somme restante : 11 cents.

• Utilisez une pièce de 10 cents. Somme restante : 1 cent.

• Utilisez une pièce de 1 cent. Somme restante : 0 cents.

Le nombre minimum de pièces nécessaires est 3.

Exemple : Problème du Sac à Dos Fractionnaire

Problème : Maximiser la valeur des objets dans un sac à dos avec une capacité limitée, où les objets peuvent être divisés.

Approche Gloutonne :

1. Calculez le rapport valeur/poids pour chaque objet.

2. Triez les objets par rapport valeur/poids en ordre décroissant.

3. Ajoutez les objets au sac à dos dans cet ordre jusqu'à ce que le sac soit plein.

Exemple : Supposons que vous avez les objets suivants avec leurs valeurs et poids respectifs :

La capacité du sac à dos est de 50 kg.

• Calculez les rapports valeur/poids : A (6), B (5), C (4).

• Triez les objets par rapport valeur/poids : A, B, C.

• Ajoutez l'objet A (10 kg) au sac. Capacité restante : 40 kg.

• Ajoutez l'objet B (20 kg) au sac. Capacité restante : 20 kg.

• Ajoutez une fraction de l'objet C (20/30) au sac. Capacité restante : 0 kg.

La valeur totale dans le sac à dos est de 60 + 100 + 80 = 240.

Avantages et Inconvénients des Algorithmes Gloutons

Avantages :

• Simplicité et facilité de mise en œuvre.

• Efficacité en termes de temps et d'espace.

• Souvent fournissent une solution optimale pour certains problèmes.

Inconvénients :

• Ne garantissent pas toujours une solution optimale globale.

• Peuvent échouer pour certains problèmes où une approche plus globale est nécessaire.