Heuristiques

Heuristiques

Heuristique

Page d'aide sur l'homonymie Ne doit pas être confondu avec éristique.

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 (Littré). En sociologie, il s'agit d'une discipline qui se propose de dégager les règles de la recherche scientifique (Larousse).

En optimisation combinatoire, Théorie des graphes et Théorie de la complexité, une heuristique est un algorithme qui fournit rapidement (en temps polynomial) une solution réalisable, pas nécessairement optimale, pour un problème d'optimisation NP-difficile. Une heuristique, ou méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné. Les algorithmes de résolution exacts étant de complexité exponentielle, il est généralement plus judicieux de faire appel à des méthodes heuristiques pour des problèmes difficiles. On retiendra cependant que des méthodes de résolution exactes (comme le simplexe) sont de complexité exponentielle mais parfois plus efficaces en pratique qu'une méthode heuristique. L'usage d'une heuristique est pertinente pour calculer une solution approchée d'un problème et ainsi 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. 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).

La qualité d'une heuristique peut s'évaluer selon deux critères scientifiques :

  1. Critère pratique, ou empirique : on implémente l'algorithme approximatif et on évalue la qualité de ses solutions par rapport aux solutions optimales (ou aux meilleures solutions connues). Ceci passe par la mise en place d'un banc d'essai (en anglais benchmark, ensemble d'instances d'un même problème accessible à tous).
  2. Critère mathématique : il faut démontrer que l'heuristique garantit des performances. La garantie la plus solide est celle des algorithmes approchés, sinon il est intéressant de démontrer une garantie probabiliste, lorsque l'heuristique fournit souvent, mais pas toujours, de bonnes solutions.

C'est un fait que ces deux critères peuvent être contradictoires. Un exemple frappant est celui du transversal minimum. L'algorithme 2-approché pour ce problème est dans une imposante majorité des cas nettement moins efficace que l'heuristique des plus hauts degrés. Celle-ci consiste à former une solution réalisable en sélectionnant à chaque itération le sommet couvrant un maximum de sommets. Cette heuristique peut pourtant fournir des solutions aussi mauvaises que l'on veut, dans le sens que pour tout ρ > 1 on peut construire une instance pour laquelle l'heuristique donne une solution dont la valeur est supérieure à ρ fois celle de l'optimum.

Ironiquement, la principale difficulté de la résolution exacte d'un problème d'optimisation combinatoire est non pas de trouver une solution optimale, ce qui souvent arrive assez rapidement lors du processus de résolution, mais de démontrer qu'une solution est bien la meilleure possible, c'est-à-dire de réaliser que l'on a la solution optimale. Le critère mathématique est surtout important car l'information qu'il donne est exploitable dans un processus de résolution exacte. Par exemple, si l'heuristique 2-approchée pour le transversal minimum donne une solution réalisable de valeur 100, on sait que la valeur de la solution optimale est au minimum 50, on peut donc stopper un processus d'énumération (par-exemple séparation et évaluation) dès que l'on possède une solution réalisable atteignant cette borne. Dans ce contexte il devient motivant d'élaborer l'algorithme 2-approché le plus mauvais qui soit, donnant la solution la plus éloignée de l'optimum, pour prouver une meilleure borne. On utilise donc un couplage maximum, alors qu'un couplage maximal suffit, pour cet algorithme 2-approché. Pour résumer, l'heuristique est la logique d'esprit d'un algorithme.

Références

  • C. H. Papadimitriou & K. Steiglitz, Combinatorial optimization: algorithms and complexity, Englewoods Cliffs, Prentice Hall, 1982
  1. (fr) Définitions lexicographiques et étymologiques de heuristique du CNRTL.

Articles connexes

Wiktprintable without text.svg

Voir « heuristique » sur le Wiktionnaire.

  • Portail de l’informatique Portail de l’informatique
Ce document provient de « Heuristique ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Heuristiques de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Arbres heuristiques — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • HEURISTIQUE — Ce terme de méthodologie scientifique qualifie tous les outils intellectuels, tous les procédés et plus généralement toutes les démarches favorisant la découverte – c’est la racine grecque du mot – ou l’invention dans les sciences. On a pu… …   Encyclopédie Universelle

  • Arbre heuristique — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • Carte Heuristique — Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre différentes idées,… …   Wikipédia en Français

  • Carte des idées — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • Carte mental — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • Carte mentale — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • Carte heuristique — Pour les articles homonymes, voir Carte. Une carte heuristique (du grec ancien εὑρίσκω, eurisko, « je trouve » ), ou mind map en anglais, carte des idées, schéma de pensée, carte mentale, arbre à idées ou encore topogramme, est un… …   Wikipédia en Français

  • Mind map — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

  • Mind mapping — Carte heuristique Une carte heuristique (mind map en anglais), également appelée carte des idées, carte conceptuelle, schema de pensée, carte mentale, arbre à idées ou topogramme, est un diagramme qui représente les connexions sémantiques entre… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”