Le correctif qui a changé le taux de succès bien plus que le coût

Huit reines, une par colonne, et un état est la liste des huit lignes qu’elles occupent. Le coût d’un état est le nombre de paires qui s’attaquent. L’escalade par plus forte pente examine les $8 \times 7 = 56$ déplacements d’une seule reine, prend le meilleur (l’un des meilleurs au hasard en cas d’égalité), et s’arrête quand rien ne fait mieux.

Sur 2 000 départs aléatoires, elle en résout 14,75 %, soit 295, en 4,1 pas quand elle gagne et 3,1 pas avant de se bloquer.

A. Le correctif habituel

Elle se bloque parce que le paysage comporte des plateaux : des régions entières où tout déplacement disponible laisse le coût exactement où il est. Le remède habituel consiste à autoriser des déplacements latéraux, jusqu’à une certaine limite, en pariant qu’un plateau est peut-être un épaulement avec de la descente de l’autre côté.

Autorisez cent déplacements latéraux consécutifs et les mêmes 2 000 départs donnent

$$94{,}55\% \text{ résolus}, \qquad 19{,}5 \text{ pas en cas de succès}, \qquad 63{,}6 \text{ en cas d'échec}.$$

Un taux de succès qui passe de 14,75 % à 94,55 % est le genre de chiffre qui fait adopter un changement.

B. Ce que coûte l’obtention effective d’une réponse

L’escalade est bon marché et redémarrable : personne ne l’exécute une seule fois. La quantité qui compte est le travail attendu jusqu’à l’apparition d’une solution :

$$\mathbb{E}[\text{pas}] = \frac{1 - p}{p}\,\mathbb{E}[\text{pas} \mid \text{échec}] + \mathbb{E}[\text{pas} \mid \text{succès}].$$

Les entrées sont données à deux décimales parce que la formule en a besoin : à partir de ces colonnes, elle redonne chaque total au chiffre près, alors qu’avec les mêmes entrées arrondies à une décimale la deuxième ligne donnerait 23,2.

La version simple échoue environ six fois sur sept, mais elle échoue en 3,1 pas et coûte 21,9 pas au total. La version améliorée réussit presque toujours, met 19,5 pas pour le faire, et coûte 23,1 au total. Comptée en pas, la multiplication par six du taux de succès vaut, sur ce problème, un peu moins que rien.

Ce n’est pas que les déplacements latéraux ne marchent pas. Ils font exactement ce qu’ils annoncent : ils font traverser les plateaux. C’est que les échecs qu’ils suppriment étaient bon marché, que les succès qu’ils créent sont chers, et que ces deux faits s’annulent presque. À quel point dépend de ce qu’est un pas, et c’est l’objet de la section suivante.

C. Comparer des pas de natures différentes

Le recuit simulé paraît bien pire dans ce tableau, et la comparaison n’est pas équitable telle quelle. Un pas d’escalade évalue les 56 successeurs avant de bouger ; un pas de recuit en évalue au plus un. Comptons donc le travail, les coûts de successeurs réellement calculés, plutôt que les itérations. Deux choses que le décompte des pas omet comptent ici. Chaque exécution d’escalade qui échoue examine une dernière fois les 56 déplacements, pour constater qu’aucun ne convient, sans faire de pas. Et un tirage de recuit sur huit tombe sur la ligne de la reine elle-même et n’évalue rien. En comptant les deux, le travail attendu par solution est :

• escalade sans latéraux : $1\,547$ évaluations
• escalade avec latéraux : $1\,298$
• recuit : $1\,622$

Multiplier les totaux en pas par 56 donnerait $1\,224$ et $1\,295$ et oublierait ces derniers examens. Ils coûtent à la version simple $5{,}78 \times 56 \approx 324$ évaluations par solution, puisqu’elle échoue 5,78 fois par succès, et environ 3 à la version avec latéraux. Cet examen non compté renverse l’ordre : mesurés en évaluations, les déplacements latéraux rendent une solution 16 % moins chère, là où le décompte des pas la disait 6 % plus chère.

Les trois se tiennent désormais à moins d’un facteur 1,25 les uns des autres. Le recuit achète le meilleur taux de succès par exécution, 98,8 %, au coût le plus élevé des trois, mais de peu dès lors qu’on compte la même chose des deux côtés.

C’est la seconde moitié de la leçon. Le tableau de la section B compte des pas, qui ne sont pas la même unité d’une ligne à l’autre ; cette liste compte des évaluations, qui le sont. Ils soutiennent des conclusions différentes : un correctif qui vaut un peu moins que rien, ou un correctif qui vaut 16 %. Aucun des deux n’est l’amélioration d’un facteur six que suggère le taux de succès.

D. Ce qu’il faut en retenir

• Un taux de succès par exécution n’est pas un coût. Pour toute procédure redémarrable, le critère est le travail attendu jusqu’à une solution, et une méthode qui échoue six fois sur sept peut ne coûter que 19 % de plus qu’une méthode qui échoue une fois sur dix-huit.
• Mesurez les échecs, pas seulement les succès, et chaque échec en entier. La différence est ici dans ce que coûte de découvrir que cette exécution ne va pas aboutir : 3,1 pas contre 63,6, plus l’examen final qui ne trouve rien, soit un quart du coût d’un échec de la version simple.
• Comptez des opérations, pas des itérations, quand les itérations diffèrent. Un pas est ce que l’implémentation décide qu’il est, et comparer des pas entre deux algorithmes aux pas de tailles différentes ne compare rien. Compter les opérations attrape aussi le travail qui n’est pas un pas du tout.
• Rapportez la référence que vous améliorez, avec la même comptabilité. Un changement qui multiplie par six le chiffre affiché et améliore le total de 16 % mérite d’être connu avant son adoption, non après.