Heuristique

Heuristique
Page d'aide sur l'homonymie Ne doit pas être confondu avec Éristique ni Herméneutique.

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].

Sommaire

En sociologie

En sociologie, l'heuristique est la « discipline qui se propose de dégager les règles de la recherche scientifique »[3].

En optimisation combinatoire, en théorie des graphes, et en théorie de la complexité des algorithmes

Dans ces domaines, 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 pertinent 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

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

  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.

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. nécessaire].

Voir aussi

Bibliographie

  • (en) C. H. Papadimitriou & K. Steiglitz, Combinatorial optimization: algorithms and complexity, Englewoods Cliffs, Prentice Hall, 1982

Articles connexes

Sur les autres projets Wikimedia :

Notes et références

  1. Définitions lexicographiques et étymologiques de « heuristique » du CNRTL.
  2. Définition du Littré
  3. Définition du Larousse

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • 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

  • heuristique — ou hévristique (eu ri sti k ou é vri sti k ) s. f. 1°   Terme didactique. L art d inventer, de faire des découvertes. 2°   Adj. La méthode heuristique. ÉTYMOLOGIE    En grec, le terme signifie l art de trouver et vient du verbe traduit par… …   Dictionnaire de la Langue Française d'Émile Littré

  • heuristique — ● adj. ►INTART Technique consistant à apprendre petit à petit, en tenant compte de ce que l on a fait précédemment pour tendre vers la solution d un problème. L heuristique ne garantit pas du tout qu on arrive à une solution quelconque en un… …   Dictionnaire d'informatique francophone

  • heuristique —  Une heuristique est une methode d’aide a la decouverte …   Glossaire de linguistique computationnelle

  • Heuristique De Disponibilité — En psychologie, l heuristique de disponibilité désigne un mode de raisonnement qui se base uniquement ou principalement sur les informations immédiatement disponibles, sans chercher à en acquérir de nouvelle concernant la situation. Par exemple,… …   Wikipédia en Français

  • Heuristique a mouvement nul — Heuristique à mouvement nul Pour les programmes d échecs, l heuristique à mouvement nul est une technique heuristique utilisée pour améliorer la vitesse de l algorithme d élagage alpha beta. Développée par Beal en 1989, puis Goetsch et Campbell… …   Wikipédia en Français

  • Heuristique de disponibilite — Heuristique de disponibilité En psychologie, l heuristique de disponibilité désigne un mode de raisonnement qui se base uniquement ou principalement sur les informations immédiatement disponibles, sans chercher à en acquérir de nouvelle… …   Wikipédia en Français

  • Heuristique À Mouvement Nul — Pour les programmes d échecs, l heuristique à mouvement nul est une technique heuristique utilisée pour améliorer la vitesse de l algorithme d élagage alpha beta. Développée par Beal en 1989, puis Goetsch et Campbell en 1990, c est Christian… …   Wikipédia en Français

  • Heuristique (en sport) — Heuristique (sport) L heuristique est une règle pragmatique ayant un degré de généralisation. En sport, elle esquive une activité de réflexion trop coûteuse notamment dans la gestion de la motricité sportive et de l organisation du jeu. Par… …   Wikipédia en Français

  • Heuristique de disponibilité — En psychologie, l heuristique de disponibilité désigne un mode de raisonnement qui se base uniquement ou principalement sur les informations immédiatement disponibles, sans chercher à en acquérir de nouvelle concernant la situation. Par exemple,… …   Wikipédia en Français

Share the article and excerpts

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