Bruteforce & backtracking pour résoudre des problèmes NP-complets

Bonjour à tous ! Bienvenue dans ce cours sur l’algorithmique et les mathématiques discrètes.

Dans la leçon d’aujourd’hui, nous allons parler de la résolution des problèmes NP-complets avec deux algorithmes : un algorithme exhaustif et un algorithme de backtracking. À la fin de la vidéo, vous devriez être capables d’implémenter ces deux algorithmes pour résoudre le problème du voyageur de commerce.

Classiquement, les problèmes NP-complets sont abordés soit par :

• Des “algorithmes exacts”, qui sont raisonnablement rapides pour les petits problèmes.
• Ou, des algorithmes “sous-optimaux” ou “heuristiques”, qui fournissent des solutions suffisamment bonnes, mais pas nécessairement optimales.

Aujourd’hui, explorons deux algorithmes exacts pour résoudre le problème du voyageur de commerce (TSP).

La solution la plus directe au TSP est d’essayer tous les chemins élémentaires possibles – ou permutations – des $n$ villes, et de voir lequel est le moins coûteux. C’est ce qu’on appelle une recherche exhaustive ou “bruteforce”.

Si la ville de départ est fixée, le nombre de ces permutations est égal à $(n-1)!$. Par conséquent, le temps de calcul, ou le temps nécessaire à l’ordinateur pour résoudre le problème avec cette approche, est proportionnel à un facteur polynomial de $O(n!)$.

Pour donner un sens plus concret à cette complexité, imaginez qu’évaluer une permutation, ou un chemin élémentaire, prenne 1 microseconde. Le tableau suivant résume le temps de calcul lorsque le nombre de villes augmente. Par exemple, pour un problème avec 5 villes, le nombre de chemins élémentaires possibles est de 24, et le temps de calcul sera de 24 microsecondes. Multiplier le nombre de villes par seulement 3 augmente le temps de résolution à environ 24 heures, et multiplier le nombre de villes par 10, pour atteindre 30, prendra environ 3 millions de milliards de siècles.

Il est donc assez évident que cet algorithme devient impraticable même pour seulement 20 villes. Regardons un exemple. Considérons ce graphe.

Le point de départ du voyageur de commerce est le sommet $v_1$, et imaginons pour simplifier qu’il n’ait pas besoin de revenir à $v_1$ à la fin. Le nombre de solutions à explorer est donc $(n-1)!$ si $n$ est le nombre de villes.

Essayer toutes les solutions possibles à partir de $v_1$ peut être fait en utilisant une recherche en profondeur (DFS), au cours de laquelle nous gardons en mémoire le chemin le plus court rencontré.

Jusqu’à présent dans ce MOOC, nous avons considéré des DFS pour lesquelles chaque sommet est exploré une seule fois. Ici, nous nous intéressons au cas où un sommet n’apparaît pas deux fois sur le même chemin, mais peut apparaître deux fois si dans des chemins différents. Nous considérons donc une variation du DFS où la liste des sommets explorés est modifiée pour la branche actuellement explorée, et non pour les autres branches.

L’arbre de tous les chemins possibles est montré ici.

La recherche commence à gauche, en proposant la première solution $( v_1, v_2, v_3, v_4 )$ avec un coût de 16. Cette solution est stockée en mémoire comme la meilleure solution identifiée jusqu’à présent.

La solution suivante explorée est $( v_1, v_2, v_4, v_4 )$, qui a un coût de 10. Cette solution est meilleure que la meilleure connue actuellement, $( v_1, v_2, v_3, v_4 )$, et cette nouvelle solution est donc stockée en mémoire comme la meilleure solution actuelle.

La recherche continue jusqu’à ce que toutes les solutions possibles aient été évaluées. Le résultat de l’algorithme est la solution $( v_1, v_3, v_4, v_2 )$, qui a le coût le plus bas possible de 7. Un total de six solutions ont été évaluées dans cette recherche en profondeur.

L’algorithme qui parcourt l’arbre précédent peut être vu ici.

C’est un algorithme récursif qui s’appelle lui-même jusqu’à ce qu’une condition d’arrêt soit atteinte. L’idée derrière l’algorithme est de garder en mémoire le meilleur chemin possible rencontré jusqu’à présent, et de le mettre à jour lorsqu’un meilleur ou plus court est rencontré.

Les arguments de l’appel sont les suivants : la liste des sommets (moins le point de départ), le sommet initial, une liste vide (qui contiendra le chemin optimal à la fin), le poids initial de cette liste vide (qui est 0) et le graphe.

Une amélioration rapide de l’algorithme précédent consiste à arrêter la recherche en profondeur lorsqu’il est certain que la branche actuellement explorée ne générera pas une meilleure solution que la meilleure actuelle.

C’est le cas lorsque le poids total des arêtes utilisées dans la branche actuelle de l’arbre est déjà supérieur au poids total de la meilleure solution trouvée.

Cela signifie que la branche explorée à chaque étape a une influence sur le temps de calcul global.

Par exemple, imaginez que par chance nous commencions par la branche qui génère la solution optimale. Lors de l’exploration des autres branches, nous arrêterons leur exploration dès que le poids total dépasse celui trouvé pour la première branche, ce qui permettra de gagner beaucoup de temps de calcul.

Diverses stratégies peuvent être utilisées pour optimiser davantage le backtracking, en présélectionnant les branches à examiner en premier. Par exemple, nous pourrions sélectionner la branche dont le sommet de départ est le plus proche du sommet actuel.

Illustrons cette approche particulière de backtracking sur le même graphe, montré ici. L’arbre de tous les chemins possibles à partir du sommet $v_1$ est montré ici.

Tout d’abord, nous essayons de nous déplacer vers son voisin le plus proche, qui est $v_4$. Cela coûte 3 pour se déplacer vers $v_4$, donc notre route a déjà un coût de 3 jusqu’à présent. Ensuite, nous continuons vers $v_3$, qui est le voisin inexploré le plus proche de $v_4$. Cela coûte 1 de plus, donc la longueur totale est de 4. Enfin, nous nous déplaçons vers $v_2$, le dernier sommet restant. Cela ajoute 8 à notre somme, et nous obtenons donc un total de 12. Nous avons ainsi une première estimation du chemin le plus court, qui est $(v_1,v_4,v_3,v_2)$, même si ce chemin n’est pas optimal.

Il n’y a aucun mouvement possible à partir de cette configuration, donc nous revenons en arrière. Encore une fois, il n’y a pas d’autres alternatives ici, car nous avons déjà exploré $v_2$ après $v_3$, donc nous continuons en arrière. Maintenant, nous avons une autre option, qui est d’aller à $v_2$. Nous ajoutons le poids correspondant de 2 et obtenons une route partielle avec une longueur de 5. Il ne reste qu’une seule option, qui est de visiter $v_3$. Cependant, ce mouvement nous coûterait 8 de plus, ce qui donnerait un total supérieur à notre chemin précédemment trouvé avec une longueur de 12. Donc, nous revenons en arrière à la place.

Nous avons maintenant exploré toutes les options en commençant par $v_1$ puis $v_4$, donc nous continuons en arrière. Nous sélectionnons maintenant une autre option en commençant par $v_1$, qui est d’aller au deuxième voisin le plus proche de $v_1$, qui est $v_3$. À partir de là, nous allons d’abord à $v_4$. Et enfin, nous allons à $v_2$. Nous obtenons une longueur totale de 7, et mettons donc à jour le chemin le plus court jusqu’à présent.

Nous continuons à explorer l’arbre en revenant en arrière, deux fois. Maintenant, nous avons l’option d’aller à $v_2$, mais cela coûterait trop cher par rapport à notre meilleur chemin, donc nous continuons en arrière.

À partir de $v_1$, il ne reste qu’une seule option : aller à $v_2$. Cela coûterait déjà 7, ce qui est autant que notre meilleur chemin, donc nous ne pouvons pas espérer trouver un chemin plus court dans cette direction.

Nous pouvons donc conclure que le chemin le plus court a une longueur de 7, et pourtant nous n’avons exploré qu’une fraction des arbres de tous les chemins possibles.

Ainsi, la solution par backtracking a une complexité bien inférieure à l’approche par bruteforce.

Voilà, c’est tout pour aujourd’hui ! J’espère que vous avez compris comment obtenir une solution exacte du TSP en utilisant une recherche exhaustive ou par bruteforce, et comment nous pouvons résoudre le TSP plus rapidement en utilisant le backtracking.

Dans la prochaine leçon, Patrick vous expliquera comment identifier la complexité d’un problème.