Discussion:Heuristique (mathématiques)

Heuristique et temps polynomial

Est-ce qu'on peut dire qu'une heuristique est toujours en temps polynomial (comme c'est écrit dans l'intro) ? J'ai l'impression que si on a un algorithme qui fonctionne bien dans la pratique, on le nomme "heuristique"; même si sur des instance pathologiques le temps de calcul est très grand. (C'est ce qui est dit par exemple dans "Linear optimization" de Bertsimas et Tsitsiklis chap 11.) Roll-Morton (d) 1 mai 2013 à 21:41 (CEST)

Une heuristique n'est pas un algorithme. On ne peut donc pas lui attribuer une complexité, comme on le fait pour les algorithmes. En particulier une heuristique peut fonctionner très bien sur certaines données et très mal sur d'autres. --Pierre de Lyon (d) 3 mai 2013 à 20:00 (CEST)

Je suis surpris par cette affirmation, une heuristique doit bien s'implémenter, c'est donc un algorithme aussi (intégré dans un algorithme plus général). On peut donc lui associer une complexité (en fonction de ses données d'entrées, mais aussi calculer la taille des données d'entrées par rapport à la taille des données d'entrées de l’algorithme principal). — TomT0m ^[bla] 4 mai 2013 à 18:12 (CEST)

Tout ce qui s'implémente n'est pas forcément un algorithme. Les algorithmes sont des objets mathématiques très précis, qui font l'objet de la théorie de la calculabilité et de la théorie de la complexité algorithmique. La théorie de la complexité algorithmique ne s'applique pas aux heuristiques. Par exemple, les heuristiques qui fonctionnement très bien pour résoudre rapidement le problème SAT ont des comportement si biscornus et si peu reproductibles que l'on ne peut pas les faire entrer dans un classe de complexité, comme on le ferait pour les algorithmes. Certes, on peut faire des statistiques sur les comportements des heuristiques et il ne faut pas s'en priver, mais c'est de l'empirisme et ça n'est pas de la théorie. --Pierre de Lyon (d) 14 mai 2013 à 12:50 (CEST)

Hum, il me semble qu'on pourrait quand même dire certaines choses : par exemple qu'une heuristique est souvent en temps polynomial, sans dire qu'elle est dans la classe P. Dans le cas des algorithmes d'approximation, je pense qu'on peut dire que c'est algorithme mais qui résout une question "relaxée", et pour ceux-là (du moins ceux qui sont à ratio constant), il y a une théorie avec la classe APX, par exemple. (J'écris ceci juste pour faire avancer le sujet, je ne connais que l'emploi courant des termes.)--Roll-Morton (d) 14 mai 2013 à 18:34 (CEST)

Tout ce qui s'implémente a un temps d'exécution en fonction des données d'entrées qu'on lui fournit (qui ultimement dépendent de la taille du problème "maître", donc de la taille du problème qu'on veut ultimement résoudre, c'est donc une notion qui m’a l’air facilement définissable. La vitesse de calcul d'une heuristique est d'ailleurs importante, dans le cas d'une heuristique de choix par exemple, comme dans l’algorithme A*, on ne veut pas que le calcul de la fonction qui fournit l'heuristique prenne plus de temps qu'il faudrait pour résoudre le problème de manière exacte par exemple. Une bonne heuristique doit donc être rapide, elle est calculée en fonction des données du problème et est en général bien définie dans ce qu'elle calcule, je ne vois pas ce qui empêche d'en faire un algorithme. — TomT0m ^[bla] 14 mai 2013 à 20:41 (CEST)

Depuis Turing, Kleene et Church le concept d'algorithme est quelque chose de très précis, tandis que la notion d'heuristique est assez vague et doit le rester pour englober des méthodes de calcul qui sortent du cadre des algorithmes. On peut calculer la complexité d'un algorithme, on ne peut qu'estimer l'efficacité d'une heuristique. C'est pour comparer des heuristiques différentes de résolution du problème SAT que les chercheurs ont organisé une compétition. Quant à la phrase « Tout ce qui s'implémente a un temps d'exécution en fonction des données d'entrées qu'on lui fournit », elle n'est pas vraie, car dès lors que l'exécution comporte une part aléatoire, on ne peut pas attribuer un temps de calcul à une entrée donnée. --Pierre de Lyon (d) 16 mai 2013 à 11:00 (CEST)

Je ne suis pas du tout d'accord. Vous semblez impliquer qu'un algorithme doit forcément être complet ou exact, je n’ai jamais vu aucune définition qui l’impliquait. La complétude est simplement une propriété. Quant à la complexité d'un algorithme stochastique, je ne vois pas pourquoi on ne pourrait pas la calculer, en moyenne ou au pire, même si ça n'implique pas les mêmes techniques. Par ailleurs à ma connaissance les algo qui sont actuellement présentés pour satcompetition sont pour certains d'entre eux complets. Vous vous référez à quelle définition d'algorithme ? — TomT0m ^[bla] 16 mai 2013 à 12:18 (CEST)

Je n'ai pas dit qu'un algorithme doit être complet (terminer toujours, on sait que cette propriété est indécidable). En revanche il doit être parfaitement défini (si c'est cela que vous appelez exact) et il y a des définitions pour cela qui font partie de la théorie de la calculabilité. Ceci dit, dès qu'on parle de complexité d'un algorithme on suppose que l'on sait qu'il se termine. --Pierre de Lyon (d) 16 mai 2013 à 15:50 (CEST)

Pour moi un algorithme complet est un algorithme qui garantit de trouver une solution si il en existe une, mais c'est peut être plus un algorithme exact qu'on devrait appeler. (entre parenthèse sans pouvoir en citer je suis à peu prêt sur qu'il existe des algorithmes statistiques ou stochastiques sur lesquels on peut prouver qu'ils convergent vers l'optimum, certains algorithmes de colonies de fourmis il me semble). Sinon l’usage vous donne un peut tort j’ai l'impression, on met de nos jours toutes sortes de qualificatifs derrière le mot algorithme de nos jours. Dois-je comprendre que pour vous, algorithme incomplet = heuristique ? (j'ai vu cette équivalence en interrogeant Google). — TomT0m ^[bla] 16 mai 2013 à 17:37 (CEST)

Ajout : définition d'algorithme complet qu'on peut trouver par exemple dans ce document, premier résultat de la requête Voir « "complete algorithm » (sur Google)

J'arrête ici la discussion car j'ai l'impression de me faire troller. --Pierre de Lyon (d) 17 mai 2013 à 07:30 (CEST)

Heuristiques dans les algos de recherche arborescente

Cet article parle des heuristiques en optimisation combinatoire, ce n'est pas le seul type d'heuristique en algorithmique qui existe. La définition que j’en avais eu (pas encore cherché d'ou elle vient) en cours d'algo était toute méthode permettant d'accélérer la résolution d'un problème, de mémoire approximative. En pratique, mon prof parlait surtout des heuristique dans les algos de recherches dans lesquels il y a un choix à faire, comme par exemple le choix du prochain noeud à explorer dans une liste de noeud ouvertes comme pour l’algorithme A*, une variable à choisir pour une heuristique de branchement pour un problème de satisfaction de contrainte.

À ma connaissance, on utilise des heuristiques en optimisation combinatoire dans un autre algorithme quand on a besoin d'une solution réalisable pas trop mauvaise, comme par exemple pour choisir de point de départ dans un algorithme itératif, ce qui peut beaucoup influer sur la vitesse de convergence, donc ça rentre dans la définition de mon prof. Vous en pensez quoi ? — TomT0m ^[bla] 16 mai 2013 à 13:03 (CEST)

PS: Ça correspond pas mal à ce que cette version antérieure de l'article heuristique semblait contenir : archivée sur un autre site

Non, cet article ne parle pas des heuristiques en optimisation combinatoire, mais des heuristiques en mathématiques. D'autre part, nous ne sommes pas en train de compiler le cours d'un professeur qui peut donner une définition restrictive de la notion d'heuristique et une version large de la notion d'algorithme -- C'est la liberté du monde académique --. Nous sommes au contraire en train d'écrire une encyclopédie où les définitions doivent être celles qui sont communément admises. --Pierre de Lyon (d) 16 mai 2013 à 15:44 (CEST)

La seule source donnée parle d'optimisation combinatoire. D'ailleurs en l’état cet article couvre t’il l’heuristique de l’algorithme A* ou dans le sens donné dans ce document par exemple ? c'est assez commun comme vocabulaire employé dans ces contextes. — TomT0m ^[bla] 16 mai 2013 à 17:21 (CEST)

cette source va plutôt dans votre sens par contre, le problème à résoudre dans un algo de backtracking relatif au choix de variable est le problème de choix optimal de variable, pour lequel on utilise en général des heuristiques de choix pour lesquels il n’existe pas en général de garanties et qui donnent plutôt de bons résultats en pratique. Cela dit ce que calculent ces heuristiques est parfaitement défini. Est-ce que ça rend un algorithme de backtracking heuristique parce qu'il utilise une heuristique, alors qu'il est garanti de terminer et de donner une solution en un temps fini ? — TomT0m ^[bla] 16 mai 2013 à 18:12 (CEST)

Comme je comprends la question, je répondrais oui. --Pierre de Lyon (d) 24 mai 2013 à 22:56 (CEST)

Heuristiques et résolution exacte

Je constate que la version française, qui vient d'être corrigée, différe sur ce point de la version anglaise:

- Une heuristique diffère d'un algorithme de résolution exact, en ce sens que l'algorithme exact apporte la garantie de trouver la solution ou une solution optimale pour le problème.

contre

- a heuristic is a technique designed for solving a problem more quickly when classic methods are too slow,

Il faudrait veiller à avoir une certaine cohérence interwiki. Bien clairement, je pense que c'est la version anglo-saxonne qui a raison et j'étais auteur de la version antérieure. --Pierre de Lyon (d) 28 mai 2013 à 10:51 (CEST)

En même temps, on peut lire un peu plus loin dans l'article quelque chose comme « The greedy algorithm heuristic » qui montre bien que la distinction est pour le moins floue et artificielle. — TomT0m ^[bla] 28 mai 2013 à 11:32 (CEST)

Si nous pouvons être moins flous que les anglo-saxons, essayons . Ne sommes-nous pas la patrie de Descartes? D'autre part, j'ai enlevé le pléonasme "algorithme exact". --Pierre de Lyon (d) 2 juin 2013 à 18:30 (CEST)

J'aimerai quand même des références pour ça, c'est le noeud du problème. Quand on parle de résoudre un (sous) problème, on a parfois pas besoin de trouver une solution mathématiquement optimale. D'ailleurs un ensemble d'instuction (qui termine) résoud de toute façon un problème : le problème de savoir le résultat de cette suite d'instruction. — TomT0m ^[bla] 2 juin 2013 à 18:57 (CEST)

Dans l'avant dernier numéro de ACM SIGACT news de décembre 2012 (un bulletin de référence en ce qui concerne la théorie des algorithmes et de la complexité), il y a un article de synthèse sur les heuristiques (Lane A. Hemaspaandra, Ryan Williams: SIGACT News Complexity Theory Column 76: an atypical survey of typical-case heuristic algorithms. SIGACT News 43(4): 70-89 (2012)) autour de la résolution des problème NP. Le résumé commence par (je traduis): « Les approches heuristiques se comportent si bien qu'elles semblent presque toujours donner la bonne réponse.» Plus loin dans l'article les auteurs écrivent: « Quand nous parlerons d'heuristiques, nos parlerons d'algorithmes déterministes. (C'est-à-dire que nous ne parlerons pas du cas où l'algorithme heuristique est randomisé et essaie d'atteindre une fréquence d'erreur asymptotique basse). Ainsi pour nous, un algorithme heuristique en temps polynomial sera simplement un programme déterministe en temps polynomial et bien sûr il acceptera un certain ensemble P. ». L'article est certes un peu technique par endroit, mais constitue une excellente référence sur les heuristiques du point de vue mathématique. --Pierre de Lyon (d) 17 juin 2013 à 21:46 (CEST)

Travail inédit ?

le texte n'est relié à aucun des ouvrages de la bibliographie, ni ne présente les différences d'approche, qui semblent considérables. En attendant :

« Méthode heuristique : Méthode de résolution de problèmes qui, contrairement à une méthode algorithmique, tient compte à chaque étape des résultats précédents pour déduire une stratégie à adopter pour la suite (prise de décision « raisonnée »). De plus, les méthodes heuristiques ne garantissent pas qu'une solution sera trouvée en un nombre fini d'étapes. »

— Alain Bouvier, Michel George et François Le Lionnais, Dictionnaire des mathématiques, Presses universitaires de France, 2001 (1^re éd. 1979), p. 407.

Bien entendu, cette définition est une prise de position : mais on attend d'une encyclopédie qu'elle en rende compte. Au lieu de ça, nous avons une suite d'appréciation non reliées à des références.

PolBr (discuter) 21 août 2021 à 10:42 (CEST)

En mathématiques

La méthode cartésienne suggérée vient des deux premiers principes du Discours de la méthode :

« Le premier était de ne recevoir jamais aucune chose pour vraie que je ne la connusse évidemment être telle ; » C'est la "condition d'arrêt".

« Le second, de diviser chacune des difficultés que j'examinerais, en autant de parcelles qu'il se pourrait, et qu'il serait requis pour les mieux résoudre. » C'est la méthode de division des problèmes en problèmes "plus simples". JC.Raoult (discuter) 19 janvier 2023 à 18:23 (CET)