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 :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
# This function returns the shortest path in the graph going through all nodes def travellingSalesman (graph, sourceNode) : # We store the best path here bestLength = float("inf") bestPath = None # Thus function takes as an argument the nodes that are not visited yet, the graph and a current location # In addition, we remember the currently crossed path and the associated weight # Basically, we perform a depth-first search and study the path length if it contains all nodes def exhaustive (remainingNodes, currentNode, currentPath, currentLength, graph) : # If the portion of path we have discovered is already bigger than the best path, we stop nonlocal bestLength, bestPath if currentLength >= bestLength : return # If no nodes are remaining, we have a path comprising all nodes # We save it as the best if it is better than the current best if not remainingNodes : print("Found Hamiltonian path", repr(currentPath), "of size", currentLength) if currentLength < bestLength : bestLength = currentLength bestPath = currentPath # If some nodes are remaining, we perform a depth-first search # We increase the path and its length in the recursive call # Obviously, we only consider nodes that are reachable else : for neighbor, weight in graph[currentNode] : if neighbor in remainingNodes : otherNodes = [x for x in remainingNodes if x != neighbor] exhaustive(otherNodes, neighbor, currentPath + [neighbor], currentLength + weight, graph) # We initiate the search from the source node otherNodes = [x for x in range(len(graph)) if x != sourceNode] exhaustive(otherNodes, sourceNode, [sourceNode], 0, graph) # We return the result return (bestPath, bestLength) |
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.