Heuristique (mathématiques)

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Page d'aide sur l'homonymie Pour les articles homonymes, voir heuristique.

Au sens le plus large, l'heuristique est la psychologie de la découverte, abordée par différents mathématiciens.

Au sens étroit, plus fréquent, une heuristique est 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.

Heuristique au sens large[modifier | modifier le code]

Aspect psychologique[modifier | modifier le code]

On distingue en général plusieurs temps

  • la prise en compte du problème (question, contexte : données, contraintes, acteurs, tenants et aboutissants)
  • l'incubation, recherche de solution, rumination parfois très longue ; la méthode du problème résolu peut ici dégager les conditions nécessaires à respecter.
  • l'illumination (ou découverte de solution)
  • l'explicitation, qui descend dans les détails
  • la validation (qui doit relancer le processus en cas d'échec)

En mathématiques[modifier | modifier le code]

Polya a abordé ces questions sous l'angle des mathématiques.

Il distingue les niveaux opératoires, tactiques et stratégiques. Le premier regroupe des savoir-faire élémentaires, le dernier est le plus intuitif et le plus difficile. Mais l'expérience rend les niveaux inférieurs de plus en plus riches et efficaces.

Une fois le problème bien cerné (question, contexte : données, contraintes, tenants et aboutissants), selon les cas

  1. c'est un problème connu (ou un cas particulier) ;
  2. c'est un problème qu'on peut ramener à une combinaison de problèmes plus simples ;
  3. c'est un problème ressemblant à un problème qu'on sait traiter.

Le premier cas se produit d'autant plus souvent qu'on a plus d'expérience ; il peut demander une adaptation, afin de ne pas "écraser une noisette avec un marteau-pilon".

Le second cas correspond à une analyse cartésienne, et utilise le premier comme critère d'arrêt.

Le troisième cas est le plus intuitif, fertile mais incertain, car les problèmes analogues ont souvent, mais pas toujours, des solutions analogues ; de plus, si l'analogie est trop lointaine, on peut devoir la fragmenter en plusieurs stades intermédiaires.

Finalement, lorsqu'un plan d'action a été trouvé, on l'explicite pour le mettre en œuvre.

Si le résultat n'est pas bon, on remet en cause la démarche.

Si le résultat est correct, il est bon de voir si on peut faire mieux, plus efficace ou plus général, afin d'enrichir son expérience.

Heuristique au sens étroit[modifier | modifier le code]

Une heuristique est 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.

Une heuristique s'impose quand les algorithmes de résolution exacte sont de complexité exponentielle, et dans beaucoup de problèmes difficiles. L'usage d'une heuristique est aussi pertinent pour calculer une solution approchée d'un problème ou pour accélérer le processus de résolution exacte. Généralement, une heuristique est conçue pour un problème particulier, en s'appuyant sur sa structure propre, mais les approches peuvent contenir des principes plus généraux.

En général, un algorithme-glouton est précisément une heuristique, par exemple

On parle de métaheuristique pour les méthodes approximatives générales, pouvant s'appliquer à différents problèmes (comme le recuit simulé par exemple).

Qualité d'une heuristique[modifier | modifier le code]

Elle peut s'évaluer selon divers critères  :

  1. Qualité du résultat : on implémente l'heuristique et on évalue la qualité de ses solutions par rapport aux solutions optimales (ou aux meilleures solutions connues), soit en termes de distance, soit en termes de probabilité de réussite. Ceci passe par la mise en place d'un jeu d'essai ou benchmark, ensemble d'instances d'un même problème accessible à tous.
  2. Coût de l'heuristique : complexité (temps, espace) de l'heuristique.
  3. Éventuellement, étendue du domaine d'application (domaine d'optimalité et domaine d'admissibilité des solutions.

Ces critères permettent de comparer les heuristiques s'adressant à un même problème, afin de dégager les heuristiques dominantes.

Certaines peuvent être oubliées, d'autres se révélent utiles dans les cas simples, ou au contraire très efficace après un démarrage très lourd.

Enfin, si une méthode absolue est hors d'atteinte, on peut mettre en concurrence diverses heuristiques pour profiter de l'ensemble de leurs domaines d'activités.

Voir aussi[modifier | modifier le code]

Bibliographie[modifier | modifier le code]

  • (en) C. Papadimitriou & K. Steiglitz, Combinatorial optimization: algorithms and complexity, Englewoods Cliffs, Prentice Hall, 1982.
  • (en) G. Polya, How to solve it, Princeton University Press, 1945
  • (fr) G. Polya, Comment poser et résoudre un problème, Dunod 1965, traduction du précédent ; réédition J. Gabay

Articles connexes[modifier | modifier le code]

Sur les autres projets Wikimedia :

Notes et références[modifier | modifier le code]