Devops for Growth

Applications algorithmiques

• Le problème du plus court chemin (algorithme de Bellman-Ford et algorithme de Floyd-Warshall) ;
• Problème d'affectation des ressources. Il s'agit (par exemple) de distribuer m skis à n skieurs (m>n) en minimisant les écarts de taille entre les skis et les skieurs. La propriété d'optimalité des sous-structures (si une distribution est optimale, alors toute sous-partie des skis et des skieurs est optimale) le rend traitable par programmation dynamique ;
• Le problème du sac à dos (knapsack en anglais) est un problème classique de recherche opérationnelle qui est NP-difficile, mais qui est résolu de manière pseudo-polynomiale à l'aide d'un algorithme de programmation dynamique ;
• Le problème du rendu de monnaie dans le cas général ;
• La recherche de la plus longue sous-suite strictement croissante dans une suite de nombres ;
• Des problèmes d'algorithmique du texte comme le calcul de la plus longue sous-suite commune entre deux chaînes, le calcul de la distance de Levenshtein ou encore l'alignement de séquences (avec l'algorithme de Smith-Waterman par exemple) ;
• L'algorithme CYK est un algorithme d'analyse syntaxique ;
• La méthode la plus utilisée pour résoudre le problème de détection de ruptures est la programmation dynamique.

Utilisations

Les algorithmes de recherche locale sont largement utilisés dans les problèmes d'optimisation difficiles, tels que les problèmes informatiques (en particulier l'intelligence artificielle), mathématiques, de recherche opérationnelle, d'ingénierie et de bio-informatique.

Exemples

Les problèmes suivants se prêtent bien à l'utilisation de la recherche locale[réf. souhaitée] :

1. le problème de couverture de sommets dans lequel une solution est un arbre recouvrant un graphe simple et l'objectif est de trouver la solution avec le nombre de nœuds minimum ;
2. le problème du voyageur de commerce où une solution est un cycle contenant tous les nœuds du graphe et l'objectif est de minimiser la longueur totale du cycle ;
3. le problème SAT où une solution est une association et l'objectif est de maximiser le nombre de clauses vérifiées par l'association ; dans ce cas, la solution finale est celle qui satisfait toutes les clauses.

Beaucoup de problèmes peuvent être formulés de plusieurs manières en termes d'espace de recherche et d'objectif. Par exemple, pour le problème du voyageur de commerce une solution peut être un cycle et le critère à maximiser la combinaison du nombre de nœuds et de la longueur du cycle. Mais une solution peut aussi être un chemin, et le transformer en cycle peut faire partie de l'objectif.

« En informatique, de toutes les approches en programmation, la programmation par contraintes se rapproche le plus de l'idéal : l'utilisateur décrit le problème, l'ordinateur le résout. »

— E. Freuder4

Elle fait partie des « aides à la décision » dans la mesure où elle propose des modèles conceptuels en vue d'analyser et de maitriser des situations complexes pour permettre aux décideurs de comprendre, d'évaluer les enjeux et d'arbitrer ou de faire les choix les plus efficaces2.

Ce domaine fait largement appel au raisonnement mathématique (logique, probabilités, analyse des données) et à la modélisation des processus. Il est fortement lié à l'ingénierie des systèmes, ainsi qu'au management du système d'information.

L'heuristique (du grec ancien εὑρίσκω, eurisko, « je trouve »1), parfois orthographiée euristique, est un terme de didactique qui signifie « l'art d'inventer, de faire des découvertes »2.

• (...)
• En psychologie, une heuristique de jugement désigne une opération mentale, rapide et intuitive.
• (...)
• En optimisation combinatoire, en théorie des graphes, en théorie de la complexité des algorithmes et en intelligence artificielle, une heuristique est une méthode de calcul qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation NP-difficile.

Exemple

Le problème du VRP où un Voyageur de Commerce doit parcourir les N villes d'un pays en effectuant le trajet le plus court.

La méthode ELECTRE et ses dérivés rejettent les trois postulats de base de l'aide classique à la décision:

• Rejet du postulat de la réalité de premier ordre: ELECTRE porte sur des objets de connaissance qui ne sont pas donnés car l'identité du projet dépend de l'observateur et de son système de valeurs.
• Rejet du postulat du décideur: Dans l'analyse classique, le décideur a un système de préférences rationnelles. En réalité, le décideur est souvent indécis ; ses préférences évoluent car la décision est le résultat d'un processus de micro décisions qui s'inscrit dans le temps.
• Rejet du postulat de l'optimum qui justifie la recherche d'un projet optimal dans l'analyse classique d'aide à la décision. L'optimum ne peut être atteint que si trois conditions sont satisfaites:
  • Les différentes stratégies (projets) proposées au décideur sont bien distinctes les unes des autres.
  • Stabilité dans le temps des stratégies.
  • Complète comparabilité transitive. C'est-à-dire que si A > B et B > C, alors A > C (transitivité), et que A, B et C sont toujours comparables.

La méthode ELECTRE considère que les projets ne sont pas stables et pas toujours comparables. En effet, il n'est pas toujours possible de déterminer une stratégie meilleure que toutes les autres dans l'absolu. Dans le cadre d'analyse des méthodes multicritères, la valeur accordée à une stratégie est relative.

C'est un modèle d'agrégation des préférences. Contrairement aux méthodes d'analyse multicritères anglo-saxonnes, qui consistent à agréger puis comparer les différents critères, la méthode ELECTRE et ses dérivés les comparent puis les agrègent.