Analyse numérique

1. Introduction
2. Définition

Une heuristique est a l’opposé des méthodes exactes une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, pour un problème d'optimisation difficile. C'est un concept utilisé entre autres en optimisation combinatoire, en théorie des graphes, en théorie de la complexité des algorithmes et en intelligence artificielle.

**étymologiquement du grec ancien eurisko (trouver) ; l heuristique est une méthode approchée conçue pour un problème d'optimisation particulier permettant de trouver des solutions avec un temps de calcul raisonnable traduisant une stratégie, une manière de penser, s'appuyant sur notre connaissance du problème. Ils sont indispensables pour les problèmes NP −  difficiles car généralement en temps polynomial.

1.  Classification des heuristiques

les heuristiques peuvent se classer en trois catégories :

– Les heuristiques constructives gloutonnes : se contentent de construire pas à pas une seule solution. Elles se caractérisent par une grande rapidité mais leur performance est souvent décevante.

– Les heuristiques de recherche locale (ou de recherche d’un optimum local): travaillent quant à elles sur une solution qu’elles tentent d’améliorer itérativement. Lors d’une itération, la solution courante est légèrement modifiée afin d’obtenir une solution voisine. Ces algorithmes obtiennent en général des résultats meilleurs que les procédures constructives, mais n’ont pas toujours une grande capacité à explorer des régions très différentes de l’espace des solutions.

– Les heuristiques évolutionnaires : agissent sur une population d’individus (des solutions ou des morceaux de solutions) qui coopèrent et s’adaptent individuellement. Elles ont la plupart du temps un fort potentiel pour trouver des solutions très différentes lors de leur application, mais manquent souvent d’agressivité, car malgré la diversité des solutions rencontrées, celles-ci ne sont pas toujours de grande qualité. De plus, elles nécessitent souvent un ajustement long et fastidieux de nombreux paramètres avant d’obtenir des résultats intéressants.

Dans ce qui suit, nous allons décrire ces heuristiques selon deux classes : les

Heuristiques constructives (ou heuristique gloutonnes), et les méta heuristiques incluant les heuristiques de recherche locale et les heuristiques évolutionnaires. C’est la classification qui est souvent adoptée dans la plupart des travaux de description des méthodes approchées.

[pic 1]

3.  Les Heuristiques gloutonnes

3.1. Définition

En informatique, un algorithme glouton (greedy algorithm en anglais, parfois appelé aussi algorithme gourmand) est un algorithme qui suit le principe de faire, étape par étape, un choix optimum local. Dans certains cas cette approche permet d'arriver à un optimum global, mais dans le cas général c'est une heuristique

Nous l'avons déjà en effet utilisée plusieurs fois mais sans la mettre en avant. Citons quelques heuristiques que nous avons vu:

-FIFO (First In First Out) : où la première tâche arrivée est la première à être ordonnancée,

-SPT (Shortest Processing Time) : où la tâche ayant le temps opératoire le plus court est traitée en premier

-LPT (Longest Processing Time) : où la tâche ayant le temps opératoire le plus important est traitée en premier,

-EDD (Earliest Due Date) où la tâche ayant la date due la plus petite est la plus prioritaire.

L'algorithme de Prim, on rajoute à chaque étape l'arrête de plus petite valuation entre un sommet de l'arbre en construction et un sommet qui n'y figure pas encore. Il s'agit donc bien d'un choix glouton au sens que l'on vient de définir.

L'algorithme de Kruskal, on choisit successivement les arrêtes de plus petites valuations à condition que celles-ci ne créent pas de cycle simple. Là encore l'approche est gloutonne.

L'algorithme de Welsh-Powell où l'on considère les sommets par ordre décroissant de leurs degrés.

Et puis bien sûr le célèbre algorithme de Dijkstra, où à chaque itération l'on sélectionne le sommet non encore traité dont la distance à l'origine est minimale. Et donc le meilleur sur le moment.

Ces algorithmes sont donc gloutons, ils sont bien constitués d'une succession de choix sur lesquels on ne revient jamais par la suite.

NB : A noter que l’algorithme de Bellman-Ford n’est pas glouton, on revient plusieurs fois sur chacun des sommets.

1. Résolution du problème

Problème 1 : Problème du voyageur de commerce

un algorithme  glouton pour le PVC:

 - trier les arêtes (coûts croissants)

 - sélectionner dans l'ordre les arêtes non "parasites" [pic 2]

Problème 2 : Nous voulons placer les objets dans les boites en respectant leurs capacités en utilisant le moins possible de boites.

1. Méthode de résolution par choix successifs d’un objet et d’une boite

Capacite de la boite 11

(Ajoute tes schémas a la suite)

Problème 3 : Problème de coloration

Le problème de coloration consiste à donner des couleurs aux sommets tel que pour chaque arête, les deux sommets reliés soient de couleurs différentes. L'ensemble de couleur est limité. Le problème est NP-complet. L'algorithme glouton suivant, parfois appelé first-fit algorithm est une heuristique pour ce problème.

Entrée :

liste ordonnée V des n sommets d'un graphe G

liste ordonnée C de couleurs    

Pour i variant de 1 à n

 v = V[i]      

 couleur = la première couleur de C non utilisée par les voisins de v  

 colorier (v, couleur)  

Fin pour

Pour un graphe il existe toujours un ordre des sommets qui mène à une bonne solution en utilisant cet algorithme, cependant pour d'autres ordres l'algorithme sera bloqué car toutes les couleurs disponibles auront déjà été utilisées, et l'étape la première couleur de C non utilisée par les voisins de v ne pourra pas être effectuée.

...