Approfondir : A*, l'heuristique qui vise le but

Une addition dans la clé de tri a divisé le travail par trois et quart. C'est trop beau pour être gratuit, et ça ne l'est pas : cette addition repose sur une promesse. Tant que ton estimation du chemin restant reste optimiste — jamais plus grande que la vérité — le plus court chemin est garanti. Le jour où elle devient trop sûre d'elle, la garantie tombe sans un message d'erreur, et le robot roule vingt centimètres de trop en croyant faire au mieux. Cette leçon te donne la règle, le contre-exemple chiffré, et le droit de tricher en connaissance de cause.