Appliqué sans discernement, le backtracking peut s’avérer redoutable de complexité, tant la voie qui mène à la solution peut être longue, tortueuse, pleine d’ornières, de pièges et de détours dans lesquels se perdre indéfiniment. Maitriser le problème permet néanmoins de tracer un chemin beaucoup plus direct vers la solution, nettoyé de tous ses obstacles et voies de traverses, et permettant finalement un gain de temps qu’aucune autre optimisation ou puissance de calcul herculéenne ne pourra jamais compenser. Grâce à la méthode exposée dans l’article précédent, nous avons à disposition une autoroute filant pratiquement en ligne droite vers la solution. Mais cela veut-il dire pour autant que nous désirons nous trainer le long de ce chemin à bord d’un vieux tacot fumant et tout cabossé ?

Même s’il est vrai que les optimisations dont nous allons parler ici ne permettent de gagner qu’entre deux et trois ordres de grandeur en temps de calcul, cela signifie tout de même pouvoir filer jusqu’à mille fois plus vite vers la ligne d’arrivée. Embarquer dans un tel bolide permet de passer de la génération d’une grille en 20 minutes à seulement 1 seconde, ce qui, vous en conviendrez, est loin d’être négligeable.

À suivre