L’algorithme de backtracking

L’algorithme de backtracking est très utilisé pour répondre à des problèmes de recherche et d’optimisation.

Principe

Le principe de l’algorithme est simple : construire dynamiquement une solution au problème en faisant croître des parties de solution, tant que ces parties sont suffisamment prometteuses.

Cas du voyageur de commerce

Dans notre cas, l’algorithme de backtracking correspond à réaliser un parcours en profondeur dans l’arbre des possibilités de chemins. Lorsque l’algorithme s’enfonce dans l’arbre, il peut connaître le coût partiel de la partie de chemin depuis l’origine jusqu’à la position actuelle. Dans le cas où ce coût est trop grand, l’algorithme n’explore pas davantage le sous-arbre et s’arrête.

En adaptant l’algorithme vu pour résoudre le problème du voyageur de commerce, on obtient le suivant :

Cet algorithme fonctionne si toutes les arêtes sont de poids positif.

Complexité

Considérons un graphe complet dont toutes les arêtes ont la même pondération. L’algorithme de backtracking va alors explorer l’arbre entier des possibilités et donc effectuer autant d’opérations qu’une recherche exhaustive.

En pratique cependant, il se peut que l’algorithme trouve très vite le bon chemin (puisqu’il réalise un parcours en profondeur). Dans ce cas, l’algorithme pourra potentiellement éliminer un très grand nombre de sous-arbres pour accélérer sa recherche. Dans un cas optimal, le nombre d’opérations devient linéaire.

Heuristiques

Les bonnes performances de l’algorithme de backtracking dépendent fortement de la qualité des premières estimations trouvées par l’algorithme. En pratique cela veut dire qu’on a tout intérêt à explorer des parties prometteuses en premier pour aider l’algorithme dans sa recherche.

Par exemple, un algorithme glouton peut être utilisé pour obtenir une première branche dans l’arbre. Si l’estimation du plus court chemin est bonne, de nombreuses branches seront éliminées dans la suite du parcours.

Publié le

Laisser un commentaire