Heuristique

Définition

En informatique et en intelligence artificielle, le concept d’heuristique est associé à une méthode de calcul qui fournit rapidement une solution réalisable, pas nécessairement optimale ou exacte, mais qui est suffisante pour avancer ou pour tirer des leçons dans la résolution d’un problème d’optimisation difficile.

Appliquer une heuristique revient à utiliser une règle empirique ou une règle approximative.

Un exemple d'heuristique en informatique est la solution approximative du problème du voyageur de commerce qui consiste à trouver le trajet le plus court possible qui permette à un voyageur de commerce de visiter chaque ville d'un ensemble de villes. Un algorithme glouton permet de trouver une solution approximative mais pas optimale dans un temps relativement court. L'heuristique de l'algorithme glouton choisit systématiquement la meilleure étape suivante.

Compléments

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

En psychologie, les heuristiques désignent également des raccourcis mentaux utilisés pour simplifier des problèmes difficiles. Ces raccourcis ne sont pas précis et induisent parfois en erreur.

Un exemple d'heuristique psychologique. Quelle ville a la plus grande population entre Chicago ou Omaha? Ici, on peut utiliser l'heuristique de reconnaissance. Si je connais le nom de l’une des deux villes mais pas celui de l’autre, alors celle que je connais a la plus grande population. La plupart des gens connaissent mieux Chicago qui compte 2,7 millions d'habitants alors qu'Omaha en compte 480 000.

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