|
La complexité temporelle des algorithmes de backtracking est généralement exponentielle , spécifiquement souvent exprimé par O(b^d) , où:
* b est le facteur de branchement (le nombre de choix possibles à chaque point de décision).
* d est la profondeur de l'arbre de recherche (le nombre maximum de décisions à prendre pour parvenir à une solution).
Explication :
Le backtracking explore toutes les solutions possibles en construisant systématiquement une solution candidate, étape par étape. À chaque étape, il vérifie si le candidat actuel est prometteur (c’est-à-dire s’il pourrait potentiellement conduire à une solution valable). Si le candidat est prometteur, l’algorithme explore de manière récursive d’autres choix. Si le candidat n'est pas prometteur (une « impasse »), l'algorithme *revient* à l'étape précédente et tente un choix différent.
Étant donné que l'algorithme explore un arbre de possibilités et que le nombre de branches peut croître rapidement, la complexité temporelle peut devenir très importante, en particulier à mesure que la profondeur « d » augmente.
Pourquoi exponentiel ?
Pensez-y comme à une recherche dans un arbre. Si chaque nœud de l'arborescence a des enfants « b » (facteur de branchement « b ») et que la profondeur maximale de l'arborescence est « d », alors dans le pire des cas, vous pourriez potentiellement explorer tous les nœuds « b^d ».
Considérations importantes :
* Pire scénario : La complexité temporelle O(b^d) est généralement le *pire des cas*. Le temps d'exécution réel dépend fortement du problème et de l'efficacité de l'élagage (l'efficacité avec laquelle l'algorithme peut identifier et éviter d'explorer les branches peu prometteuses).
* Taille : Les bons algorithmes de backtracking utilisent diverses techniques d’élagage pour réduire considérablement l’espace de recherche. L'élagage peut améliorer considérablement le temps d'exécution, mais il ne change pas la nature exponentielle inhérente de l'algorithme dans le pire des cas.
* Exemple : Un exemple classique est la résolution du problème des N-Queens. Pour placer N reines sur un échiquier NxN, le facteur de branchement est lié au nombre de colonnes disponibles dans une rangée, et la profondeur est liée au nombre de rangées. La complexité temporelle dans le pire des cas est considérablement réduite en vérifiant les conflits (attaques des reines) à chaque étape, ce qui élimine de nombreuses branches potentielles.
* Autres facteurs : Outre « b » et « d », d'autres facteurs peuvent affecter le temps d'exécution. Par exemple, le temps nécessaire pour évaluer si une solution candidate est prometteuse peut également être un facteur important.
* NP-Exhaustivité : De nombreux problèmes résolus en utilisant le backtracking sont NP-complets. Cela signifie que l’on pense qu’il n’existe pas d’algorithme en temps polynomial pour les résoudre en général, et que le retour en arrière devient souvent une approche nécessaire (bien que parfois inefficace).
En résumé :
Bien que le retour en arrière puisse être une technique puissante de résolution de problèmes, sa complexité temporelle exponentielle signifie qu'elle est la mieux adaptée aux problèmes dans lesquels :
* La taille du problème est relativement petite.
* Des stratégies d'élagage efficaces peuvent être utilisées pour réduire considérablement l'espace de recherche.
* Une solution approximative est acceptable si la solution exacte prend trop de temps à trouver.
Si votre problème est important et que l’élagage est inefficace, vous devrez peut-être envisager d’autres algorithmes ou techniques d’approximation.
|
