Vous êtes en vacances dans une métropole, et vous vous trouvez devant un plan de métro. Votre problème est le suivant : quel est l’itinéraire le plus court pour aller de la station de métro où vous vous trouvez, à celle où vous souhaitez aller ? Sans le savoir, vous vous trouvez face à un problème qui peut être facilement résolu par un algorithme : étant donné un plan de métro et deux stations A et B, trouver le chemin le plus court (en nombre de stations) qui va de A vers B. Supposons que l’on charge un ordinateur de résoudre ce problème. Supposons également que nous ayons accès à l’ordinateur de notre choix. Tant qu’à faire, choisissons TaihuLight, l’ordinateur le plus puissant au monde (ce supercalculateur chinois peut faire 94 000 000 000 000 000 opérations par seconde !). Étant donné la puissance de la machine, un premier réflexe serait de faire au plus simple : on demande à l’ordinateur de tester toutes les combinaisons possibles des stations (toutes les permutations). L’ordinateur connaît le plan de métro : étant donné une permutation, il regarde si elle correspond à une liste de stations voisines. Si c’est le cas, alors c’est que la liste des stations est un chemin possible. L’ordinateur calcule la longueur de ce chemin (le nombre de stations qu’il parcourt), et garde en mémoire le chemin le plus court trouvé.