Algorithmes Gloutons
Une heuristique est une méthode de résolution basée sur des règles empiriques, des approximations ou des connaissances spécifiques du problème, visant à produire rapidement une solution acceptable, sans garantie d'optimalité.
Une entreprise développe un correcteur orthographique intelligent pour une suite bureautique. Le système doit détecter les fautes de frappe, suggérer des corrections, analyser la similarité entre documents et construire un index de recherche approximative. Le cœur du système repose sur la distance d'édition (distance de Levenshtein), qui mesure le nombre minimal d'opérations élémentaires (insertion, suppression, substitution) pour transformer un mot en un autre.
La coloration des graphes consiste à attribuer des couleurs à certains éléments d'un graphe (sommets ou arêtes) en respectant des contraintes d'adjacence.
L'algorithme A* ne se contente pas de regarder le chemin parcouru ; il projette également l'effort restant. C'est un algorithme best-first search (recherche du meilleur d'abord).
Ces dernières années, des chercheurs ont découvert des livres manuscrits numérotés sur l’histoire du sultan du Maroc, Moulay Ismail Ibn Sharif (1672-1727), et pensent qu’ils pourraient révéler les secrets de la célèbre prison du Habs Qara, ce qui les a incités à les étudier attentivement.
Ces dernières années, le déficit de pluie a entraîné un faible niveau d’eau dans les barrages du Maroc, ce qui pourrait provoquer des problèmes d’approvisionnement en eau cet été ; ainsi, certaines villes comme Zagora ont décidé d’installer des réservoirs domestiques pour fournir de l’eau potable aux maisons touchées.
Étant donné la longueur du mur L et des étagères de deux longueurs m et n, trouvez le nombre de chaque type d'étagère à utiliser et l'espace disponible restant dans la solution optimale, de sorte que l'espace vide soit minimal.
Sac à dos fractionnaire Étant donné les poids et les valeurs de n articles, nous devons mettre ces articles dans un sac à dos de capacité C pour obtenir la valeur totale maximale dans le sac à dos.
Étant donné un tableau a, nous devons trouver le produit minimum possible avec le sous-ensemble d'éléments présents dans le tableau. Le produit minimum peut être un seul élément aussi.
Étant donné un ensemble de travaux pour lesquels chaque travail a une date limite et les bénéfices associés si le travail est terminé avant la date limite. Il est également indiqué que chaque travail prend une seule unité de temps, de sorte que le délai minimum possible pour tout travail est 1. Comment maximiser le profit total si un seul travail peut être planifié à la fois.
Vous avez n activités avec leurs heures de début et de fin. Sélectionnez le nombre maximal d'activités pouvant être effectuées par une seule personne, en supposant qu'une personne ne peut travailler que sur une seule activité à la fois.
Un algorithme glouton (ou greedy algorithm en anglais) adopte une stratégie simple mais puissante : À chaque étape, il choisit le meilleur choix possible selon un critère local, sans jamais remettre en question les choix précédents. Autrement dit, l'algorithme avance pas à pas, en effectuant des choix immédiats qui semblent les plus avantageux sur le moment - d'où le terme "glouton" (celui qui "mange" tout de suite ce qui paraît le meilleur).