Algorithmes gloutons

Exemple 1: arbre recouvrant de poids minimum

Dans un graphe où les arêtes ont un poids, trouver l'arbre qui relie tous les sommets avec somme des poids minimisée

Algorithme glouton non optimal:
commencer avec un arbre d'un seul sommet et choisir toujours l'arête du poids minimum pour rajouter le prochain sommet

Et un autre (optimal ou non?); Prim:
choisir toujours l'arête du poids minimum pour rajouter un nouveau sommet

Algorithme glouton et optimal; Kruskal:
commencer avec n arbres chacun d'un seul sommet
choisir toujours l'arête du poids minimum qui relie deux arbres;
raison d'optimalité;
détails de la recherche de cette arête omis ici.

Exemple 2: sac-a-dos continu

Des cas où la méthode gloutonne n'est pas optimale

commentaires sur non existence d'algorithmes efficaces (connus) pour ces 3 derniers

Ces 3 problèmes sont des variantes des problèmes NP-complets; Personne ne connait des algorithmes garantis de trouver une solution optimale en temps raisonnable (borné par un polynôme);
mais on ne sait pas si c'est impossible ou non.

Donc, il est utile de considérer des algorithmes qui ont une garantie (ou même une bonne chance) de trouver une solution près de l'optimale.

Un premier essai à un tel algorithme pourrait être un algorithme glouton simple.

Un deuxième essai serait d'essayer d'améliorer le résultat du premier par des modifications locales gloutonnes.

Arbres binaires
(de recherche)

Insertion, recherche, annulation dans un arbre binaire de recherche

Les ordres de parcours

Arbres équilibrés

1: Arbres AVL

2: Arbres 2-3




File translated from TEX by TTH, version 3.05.
On 3 Nov 2005, 13:49.