Algorithmes heuristiques
L'optimisation par colonies de fourmis (Ant Colony Optimization, ACO) est une métaheuristique inspirée du comportement des fourmis réelles pour trouver le plus court chemin entre leur nid et une source de nourriture. Développée par Marco Dorigo dans sa thèse en 1992, cette méthode est particulièrement efficace pour les problèmes d'optimisation combinatoire.
Le recuit simulé est une métaheuristique d'optimisation inspirée d'un phénomène physique : le recuit des métaux. Ce processus consiste à chauffer un matériau puis à le refroidir lentement pour réduire ses défauts et améliorer sa structure cristalline.
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.