En général, l'heuristique est une façon de privilégier certains chemins de calcul par rapport à d'autres lors de la recherche d'une solution à un problème.
Votre calcul peut être vu comme la recherche d'un chemin entre l'état initial de votre algorithme et l'état final (où la solution du problème est calculée). Sur ce chemin, il y a de nombreux états internes et vous passez de l'un à l'autre.
Maintenant, comment savoir quel chemin choisir s'il y a plusieurs choix possibles d'un état à d'autres états ? Idéalement, vous aimeriez savoir exactement quel état vous devez choisir pour que l'ensemble du chemin soit optimal (et si votre algorithme possède la propriété d'optimalité locale, alors vous avez terminé). Mais bien souvent, vous ne le savez tout simplement pas ; vous gaffez à l'aveugle dans l'espace d'état dans l'espoir de trouver l'état final, pour ainsi dire.
Dans de telles situations, vous pourriez choisir d'employer une heuristique. C'est-à-dire que vous choisissez l'état suivant en vous basant sur une certaine "supposition éclairée", une sorte d'argument rationnellement étayé, qui n'est en fait pas toujours correct, mais qui augmente généralement la probabilité que vous vous dirigiez vers l'état final.
Il est difficile d'expliquer l'heuristique de manière générale, car les approches diffèrent assez fortement en fonction du problème. Laissez-moi vous donner un exemple :
Problème du chevalier aux échecs : étant donné un échiquier de taille n fois n et une position initiale [p, q] sur l'échiquier, trouvez un chemin de la pièce chevalier à travers l'échiquier de sorte qu'elle visite chaque champ exactement une fois.
Maintenant, de tels problèmes sont souvent résolus en utilisant le backtracking. Il suffirait de déplacer le chevalier, en suivant un modèle fixe, en marquant chaque champ qu'il passe et en se souvenant du chemin qu'il a emprunté. S'il ne peut pas passer plus loin, vous "écartez" le mouvement précédent et vous effectuez le suivant dans le schéma à la place. De cette façon, vous finirez par tester tous les chemins possibles. Certains d'entre eux peuvent être des solutions valables au problème.
Maintenant, j'ai implémenté cet algorithme lors de ma 1ère année à l'Université, il y a une vingtaine d'années. Je l'ai fait tourner sur mon PC 486 ; une machine assez lente, mais comme la quantité de chemins possibles augmente très vite avec l'augmentation des dimensions de l'échiquier, les résultats seront à peu près applicables même de nos jours. Ainsi, pour un échiquier de taille 5x5, la solution a été trouvée presque instantanément. 6x6, quelques dizaines de secondes, si je me souviens bien. 7x7, quelques heures, mais oui... 8x8-une nuit et toujours pas de solution.
Alors, essayons quelques heuristiques. La 1ère tentative que j'ai testée consistait à toujours essayer le coup à partir duquel il y avait le plus grand nombre de coups possibles. C'est logique, non ? J'irai là où j'ai le plus de possibilités de continuer... Cela a fonctionné pour l'échiquier 8x8, la solution a été trouvée en une demi-heure ou quelque chose comme ça, mais même pour 9x9, là encore, pas de chance du jour au lendemain.
Alors, essayons quelque chose de fou. Essayons de choisir le coup à partir duquel il y a le moins de coups possibles. Ça n'a pas de sens, n'est-ce pas ? Pourquoi devrais-je préférer le chemin qui est probablement mauvais ? Eh bien, il s'avère que cette heuristique fonctionne brillamment. Sur le 486, l'échiquier 25x25 n'a posé aucun problème, 1ère solution trouvée en une fraction de seconde, les autres ont suivi très rapidement, le compteur ne faisait que tourner et tourner...
Pourquoi ? Eh bien, en dirigeant le cavalier vers les champs à partir desquels il avait le moins de coups possibles, nous avons réduit la largeur du sous-arbre des coups qu'il pouvait faire à partir de cet état. Comme la profondeur de cet arbre est limitée (par n fois n, le nombre de cases de l'échiquier), le nombre d'états dans ce sous-arbre diminue rapidement. Vous testerez donc un sous-arbre étroit beaucoup plus rapidement qu'un sous-arbre large. S'il y a au moins une solution dans ce sous-arbre étroit, vous la trouverez rapidement.
Donc, ce que nous avons fait ici, c'est : nous avons délibérément choisi de préférer certains calculs (ceux qui ont le moins d'états) aux autres et nous les avons essayés en premier. Nous arriverions quand même aux autres si la solution n'était pas trouvée ; au final, tous les chemins possibles auraient été testés. Mais en sélectionnant judicieusement vos déplacements locaux, vous pouvez éviter beaucoup d'impasses.
Et c'est ainsi que fonctionne l'heuristique.