Voir la source de Heuristique (mathématiques)

{{Voir homonymes|Heuristique (homonymie)}}
{{à recycler|date=août 2020}}
{{Travail inédit|date=août 2021}}
Au sens le plus large, ''l'heuristique'' est la [[Logique et raisonnement mathématique#La construction des raisonnements mathématiques| psychologie de la découverte]], abordée par différents mathématiciens.

En [[algorithmique]], 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 (mathématiques)|optimisation]] difficile.

== Heuristique au sens large ==
=== Aspect psychologique {{inédit| date =décembre 2021}} ===

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 ===
[[George Pólya|Pólya]] 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
# c'est un problème connu (ou un cas particulier) ;
# c'est un problème qu'on peut ramener à une combinaison de problèmes plus simples ;
# 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 ; {{pourquoi | il peut demander une adaptation, afin de ne pas "écraser une noisette avec un marteau-pilon".}}

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

Le troisième cas est {{pourquoi | 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.

=== Arguments heuristiques {{inédit | date = décembre 2021}}===
{{Section vide ou incomplète}}

En [[théorie des nombres]], on parle de ''raisonnement heuristique'' pour une approche non rigoureuse (et ne démontrant par conséquent rien) remplaçant par exemple les nombres premiers par une distribution aléatoire, et montrant que le résultat cherché a une probabilité égale à 1.

En [[théorie des nombres]], de nombreuses [[Conjecture|conjectures]] reposent sur des arguments, dits ''heuristiques,'' consistants à estimer la probabilité de la conjecture {{pas clair | en supposant par exemple les nombres premiers comme répartis au hasard}} ; on obtient ainsi parfois des estimations extrêmement précises, comme celles de la [[conjecture de Bateman-Horn]], qui sont bien confirmées expérimentalement. Cette technique ne doit pas être confondue avec la [[méthode probabiliste]], qui, malgré son nom, fournit des démonstrations rigoureuses et des résultats certains.

== Heuristique au sens de l'algorithmique ==
Une '''[[algorithmique#Les heuristiques|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 (mathématiques)|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]], en [[intelligence artificielle]], dans la programmation des jeux (comme les [[échecs]] ou [[Go (jeu)|go]]), dans la [[Test_de_primalité#Tests_probabilistes|primalité des nombres entiers]] et dans la démonstration de théorème.

Une heuristique s'impose quand les algorithmes de résolution exacte sont [[Théorie de la complexité (informatique théorique)|impraticables]], à savoir de complexité polynomiale de haut degré,  exponentielle ou [[Arithmétique_de_Presburger#Algorithmes|plus]]<ref group="note">La [[Problème de la décision|décision]] de l'[[arithmétique de Presburger]] est doublement exponentielle, mais des solveurs comme [[Satisfiability modulo theories|SMT]] Z3 ou oméga de [[Rocq (logiciel)|Rocq]] exhibent des démonstrations dans tous les cas pratiques.</ref>.  Généralement, une heuristique est conçue pour un problème particulier, en s'appuyant sur sa structure propre, mais il existe des approches fondées sur des principes 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).

[[Herbert Simon]], prix Nobel d'économie 1978 et pionnier de l'intelligence artificielle, est considéré comme le père des heuristiques en algorithmique. Pour lui, il s’agissait de méthodes pour arriver à des solutions satisfaisantes avec des quantités modestes de calcul.

=== Qualité d'une heuristique ===
{{article détaillé|Algorithme de Las Vegas|Algorithme de Monte-Carlo}}
Une heuristique peut s'évaluer selon divers critères  :
# ''Qualité du résultat'' : 
## on se place dans une théorie fondée sur les probabilités et on démontre mathématiquement quelques propriétés pertinentes,
## si l'on ne peut pas établir une théorie, 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 [[Test de performance|d'essai]]  ou ''benchmark'', ensemble d'instances d'un même problème, choisies pour couvrir le plus largement le spectre des instances<ref group="note">Là encore la théorie de probabilités va jouer un rôle, pour distribuer aléatoirement le jeu de données.</ref>.
# ''Coût de l'heuristique'' :  complexité ([[complexité en temps|temps]], [[complexité en espace|espace]]) de l'heuristique. 
# ''Étendue du domaine d'application'' (domaine d'optimalité et domaine d'admissibilité des solutions).

On peut mettre en concurrence diverses heuristiques pour profiter de l'ensemble de leurs domaines d'activités, ce qui est, en soi, une nouvelle heuristique.

== Notes ==
{{Notes}}

== Voir aussi ==
=== Bibliographie ===
* Nicolas Pinel, ''La méthode heuristique de mathématiques : enseigner les mathématiques autrement à l'école'', 2e éd., Éditions du Net, 2020.
* [[George Pólya]], ''Comment poser et résoudre un problème'', [[Éditions Dunod|Dunod]] 1965, traduction de  {{langue|en|''How to solve it'', Princeton University Press}}, 1945; réédition J. Gabay.
* {{article |langue=en | auteur1 = Lane A. Hemaspaandra|auteur2= Ryan Williams|périodique= SIGACT News |titre=An atypical survey of typical-case heuristic algorithms | volume =43(4) |passage=70-89 | année=2012}}
* {{article|langue=en |titre=Heuristics and their design: a survey |prénom1=Heiner |nom1=Müller-Merbach |périodique= uropean Journal of Operational Research |volume=8(1) |mois=septembre |année=1981|passage=1-23}}
* {{en}} [[Christos Papadimitriou|C. Papadimitriou]] & K. Steiglitz, ''{{lang|en|Combinatorial optimization: algorithms and complexity}}'', Englewoods Cliffs, [[Prentice Hall]], 1982.
* {{en}} [[Terence Tao]], ''[https://books.google.fr/books?id=SR4m7FxqsRsC&printsec=frontcover Solving Mathematical Problems: A Personal Perspective]'', [[Oxford University Press]], 2006 {{ISBN|9780199205608}}
* [[Imre Lakatos]], ''{{Lien|trad=Proofs and Refutations|Preuves et Réfutations}} : essai sur la logique de la découverte mathématique''. Notamment concernant les heuristiques permettant d'obtenir le [[théorème de Descartes-Euler]], <math>s - a + f = 2</math>, pour certains polyèdres et de le réfuter pour d'autres.

=== Articles connexes ===
{{Autres projets
|wiktionary=heuristique}}
* [[Algorithme approché]]
* [[Algorithme de Monte-Carlo]]
* [[Algorithme de Las Vegas]]
* [[Arbre heuristique]]
* [[Carte heuristique]]
* [[Logique et raisonnement mathématique#La construction des raisonnements mathématiques|Construction des raisonnements mathématiques]]
* [[Didactique]]
* [[Effet Tetris]]
* [[Loi empirique]]
* [[Métaheuristique]]
* [[Problème de satisfaction de contraintes]]

{{Crédit d'auteurs|interne|Heuristique|92650404}}

{{Palette|Informatique théorique}}

{{Portail|informatique théorique|mathématiques}}

[[Catégorie:Recherche opérationnelle]]
[[Catégorie:Méthode algorithmique]]
[[Catégorie:Optimisation combinatoire]]
[[Catégorie:Heuristique]]
[[Catégorie:Enseignement des mathématiques]]