Bruteforce and backtracking to solve NP-complete problems

Reading time30 min

En bref

Résumé de l’article

Dans cet article, nous vous présentons une approche pour résoudre le TSP, ou plus généralement les problèmes NP-complets. Cette approche est basée sur une recherche exhaustive des solutions possibles, avec une petite stratégie d’accélération appelée “backtracking”.

Points clés

Une approche bruteforce (exhaustive) peut être utilisée pour résoudre un problème NP-Complete.
Pour le TSP, elle construit un arbre tel que chaque branche est une solution possible.
La complexité de la résolution du TSP avec un algorithme bruteforce est $O(n!)$.
Le backtracking est une optimisation qui permet d’arrêter l’exploration des branches tôt dans la recherche.
Le branch-and-bound est une autre optimisation possible.

Contenu de l’article

1 — Vidéo

Veuillez regarder la vidéo ci-dessous. Vous pouvez aussi lire les transcriptions si vous préférez.

Important

Il y a des “codes” qui apparaissent dans cette vidéo. Veuillez garder à l’esprit que ces “codes” sont ce que nous appelons des pseudo-codes, c’est-à-dire qu’ils ne sont pas écrits dans un vrai langage de programmation. Leur but est simplement de décrire les algorithmes, pas d’être interprétables en soi. Vous aurez donc besoin d’un peu de travail pour les rendre pleinement fonctionnels en Python si vous le souhaitez.

Information

Cliquez ici pour afficher la transcription de la vidéo.

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 exhaustif, et le backtracking. À la fin de la vidéo, vous devriez être capable d’implémenter ces deux algorithmes pour résoudre le problème du voyageur de commerce.

Calcul d’une solution

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, ou TSP.

Algorithme de force brute

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 cher. C’est ce qu’on appelle une “force brute”, ou “recherche exhaustive”.

Si la ville de départ est fixée, le nombre de telles 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 dans un facteur polynomial de $O(n!)$.

Pour donner un sens plus concret à cette complexité, imaginez qu'évaluer une permutation, ou un chemin élémentaire, prend 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, donc le porter à 30, prendra environ 3 millions de milliards de siècles.

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

Le point de départ pour le voyageur de commerce est le sommet $v_1$, et imaginons pour simplifier qu’il n’a pas à 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), pendant laquelle on garde en mémoire le chemin le plus court rencontré.

Jusqu'à présent dans ce MOOC, nous avons considéré le DFS pour lequel 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 s'il est dans des chemins différents. Donc, ici nous considérons une variation du DFS où la liste des sommets explorés est modifiée pour la branche explorée actuelle, et pas 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 donc cette nouvelle solution est 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.

Algorithme

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 chemin 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.

Solution par backtracking

Une amélioration rapide de l’algorithme précédent est d’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 solution 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 hasard nous commençons par la branche qui génère la solution optimale. Lors de l'exploration des autres branches, nous arrêterons de les explorer dès que le poids total dépasse celui trouvé pour la première branche, ce qui économisera beaucoup de temps de calcul.

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

Exemple

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.

D'abord, nous essayons de nous déplacer vers son voisin le plus proche, qui est $v_4$. Cela coûte 3 pour aller à $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 allons à $v_2$ le dernier sommet restant. Cela ajoute 8 à notre somme et nous obtenons un total de 12. Nous avons donc 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 pas de mouvement possible depuis cette configuration, donc nous reculons. 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 à reculer. Maintenant, nous avons une option alternative, qui est d'aller à $v_2$. Nous ajoutons le poids correspondant de 2 et obtenons une route partielle d'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 résulterait en un total supérieur à notre chemin précédemment trouvé de longueur 12. Donc, nous reculons à la place.

Nous avons maintenant exploré toutes les options commençant par $v_1$ puis $v_4$, donc nous continuons à reculer. Nous sélectionnons maintenant une autre option en partant de $v_1$, qui est d'aller vers le deuxième voisin le plus proche de $v_1$, qui est $v_3$. 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 la route la plus courte jusqu'à présent.

Nous continuons à explorer l'arbre en reculant, deux fois. Maintenant, nous avons l'option d'aller à $v_2$, mais cela coûterait trop cher comparé à notre meilleure route, donc nous continuons à reculer.

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

Nous pouvons donc conclure que la route la plus courte 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 plus faible que l’approche brute force.

Mots de conclusion

OK, c’est tout pour aujourd’hui ! J’espère que vous avez compris comment obtenir une solution exacte du TSP en utilisant une recherche brute force ou exhaustive, et comment on peut 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.

Pour aller plus loin

2 — L’algorithme branch-and-bound

Un troisième algorithme pour résoudre exactement le TSP est l’algorithme branch-and-bound.

L’algorithme branch-and-bound explore l’arbre des possibilités (dans le cas du voyageur de commerce, l’arbre des chemins possibles). Pour ce faire, il utilise un algorithme de type BFS. À chaque sommet rencontré, il essaie d’estimer un intervalle (aussi étroit que possible) estimant la longueur d’un chemin plus court obtenu à partir de la branche de l’arbre où il se trouve actuellement.

Pour obtenir ces intervalles, plusieurs techniques existent :

Pour obtenir une borne supérieure, il suffit d’utiliser un algorithme glouton, qui estime la longueur du chemin restant en allant toujours vers le sommet le plus proche. Cela donne un chemin qui n’est pas nécessairement optimal, mais dont la longueur ne peut être que plus longue que celle d’un chemin le plus court.
Pour obtenir une borne inférieure, on peut par exemple compter le nombre de sommets encore non visités (appelons ce nombre $k$). Dans le meilleur des cas, ils peuvent être visités en passant par les $k$ arêtes de poids les plus faibles. La somme de ces $k$ poids donne la borne inférieure. Cette réduction est souvent grossière, et il est préférable de chercher la plus fine.

Lorsque l’algorithme a déterminé plusieurs intervalles (un par branche à explorer), il peut les comparer entre eux. Dans le cas de la recherche d’un chemin de longueur minimale, si l’intervalle d’une branche $b_1$ a pour borne supérieure une valeur plus petite que la borne inférieure d’un intervalle d’une autre branche $b_2$, alors le sous-arbre correspondant à $b_2$ est éliminé. En effet, il n’y a aucun intérêt à explorer le sous-arbre $b_2$ sachant que la meilleure solution trouvée sera de toute façon moins intéressante que la pire en continuant sur la branche $b_1$.

2.1 — Complexité

La complexité de l’algorithme est dans le pire des cas la même qu’une recherche exhaustive (si l’estimation des bornes ne coûte pas trop cher). C’est par exemple le cas avec un graphe complet dans lequel toutes les arêtes ont le même poids.

En pratique, avoir une bonne précision dans l’estimation des intervalles peut faire gagner beaucoup de temps. Un cas optimal est celui d’une complexité linéaire.

2.2 — Compromis précision-performance

Comme pour tous les algorithmes approximatifs, l’estimation des intervalles pose le problème du compromis précision-performance. En effet, plus l’intervalle est étroit, plus il permettra d’élaguer des parties de l’arbre. Cependant, si son estimation nécessite un calcul coûteux, cela impacte la complexité totale.

Il est donc nécessaire de trouver des estimations des bornes des intervalles qui offrent un bon compromis entre temps de calcul et précision.

Pour aller au-delà

L’algorithme Held-Karp.

Cet algorithme résout le TSP en $O(n^2 \cdot 2^n)$.
ORTools.

C’est un outil rapide pour résoudre le TSP et d’autres problèmes d’optimisation.
Branch-and-bound.

Une possible implémentation Java/C++ de l’algorithme. ```