Le problème du voyageur de commerce

Le problème du voyageur de commerce est un des problèmes les plus connus en informatique. Il est souvent utilisé comme premier exemple de problème NP-Complet.

Le problème

Le problème du voyageur de commerce est le suivant : un voyageur de commerce souhaite faire la tournée des villages de sa région puis rentrer chez lui (certaines fois le retour chez lui est ignoré). Son objectif est de minimiser la distance totale parcourue. Un tel problème est appelé problème “d’optimisation” car le but est de trouver les paramètres qui minimisent (ou maximisent) une certaine quantité.

Formellement, le problème consiste, étant donné un graphe pondéré et un sommet initial, à trouver un cycle (ou un chemin) élémentaire passant par tous les sommets du graphe et de longueur minimale. Remarque : Pour de nombreux cas d’utilisation, on considère souvent un graphe complet pondéré.

Ce problème est connu comme étant un exemple de problème NP-Complet.

Exemple d’algorithme solution

Afin de trouver la solution à ce problème, une solution simple consiste à énumérer l’ensemble des chemins possibles, à calculer pour chacun sa longueur et à sélectionner celui ou un de ceux qui sont minimaux. Pour cela, on adapte un parcours en profondeur :

# 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 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)
            nonlocal bestLength, bestPath
            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)

###################################################################
 
# Test graph
graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]]
(result, length) = travellingSalesman(graph, 0)
print(repr(result))
print(length)

# 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 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)

nonlocal bestLength, bestPath

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)

###################################################################

# Test graph

graph = [[(1, 1), (2, 7), (5, 3)], [(0, 1), (2, 1), (5, 1)], [(0, 7), (1, 1)], [(4, 2), (5, 2)], [(3, 2), (5, 5)], [(0, 3), (1, 1), (3, 2), (4, 5)]]

(result, length) = travellingSalesman(graph, 0)

print(repr(result))

print(length)

Dans cet exemple, le graphe utilisé est le suivant, où le sommet source est 0 (représenté sous forme d’un tableau de paires (voisin, poids)) :

Si ici on ne trouve que deux chemins hamiltoniens (0 – 2 – 1 – 5 – 3 – 4 et 0 – 2 – 1 – 5 – 4 – 3), il a quand même fallu tester tous les chemins possibles pour arriver à cette conclusion.

La complexité de cet algorithme est donc au moins celle qui consiste à énumérer tous les chemins possibles, soit O((|V|-1)!). C’est un nombre beaucoup trop important pour être calculable en pratique. Par exemple, avec un graphe complet à 30 sommets, cela représente 29!, soit 8.841.761.993.739.701.954.543.616.000.000 chemins à considérer.

Le voyageur de commerce au quotidien

Le problème du voyageur de commerce est un problème récurrent qui intervient dans de nombreux domaines de l’informatique. Voici quelques exemples :

Trajet d’un satellite artificiel

Le problème du voyageur de commerce intervient souvent lorsqu’il est question de minimiser un trajet potentiellement coûteux, en temps ou en argent. C’est par exemple le cas du trajet de certains satellites, qui pour effectuer leurs missions doivent passer par un certain nombre d’endroits différents.

Longueur d’un réseau de fibre optique

Le déploiement de la fibre optique pose le problème de desservir un ensemble d’endroits tout en limitant les travaux requis. Un tel problème peut généralement se formaliser sous la forme du voyageur de commerce.