Modélisation du problème

Visualisation interactive du problème d'optimisation du parcours d'un itinéraire en prenant en compte les contraintes de pondération et d'autonomie.

Outil Interactif

Autonomie max

Nœuds: 0 Arêtes: 0

Étapes d'exécution

Cliquez sur "Rechercher chemin" pour voir les étapes d'exécution.

Résultat

Aucune opération effectuée.

Le Problème du Voyageur de Commerce (TSP)

Imaginons un voyageur qui doit visiter plusieurs villes. Il a trois conditions :

Visiter chaque ville une seule fois.
Revenir à son point de départ.
Trouver le chemin le plus court.

L'objectif du Problème du Voyageur de Commerce (TSP) est de déterminer quel chemin (parmi tous les chemins possibles) est le plus court, en respectant ces trois conditions.

Pourquoi c'est compliqué ?

Le problème est difficile car le nombre de solutions possibles augmente très vite avec le nombre de villes. Par exemple :

Avec 5 villes, il y a 24 chemins possibles.
Avec 10 villes, il y en a 362.880.
Avec 20 villes, il y a 121.645.100.408.832.000 chemins possibles.

Cette explosion combinatoire rend la recherche de la solution exacte très difficile dès que le nombre de villes devient grand. Cela rend le problème intraitable avec les méthodes classiques de calcul, d'où le nom "problème NP-complet".

Que signifie NP-complet ?

Voici une explication simplifiée :

P : Ce sont les problèmes pour lesquels on peut trouver une solution rapidement (en temps "polynomial").
NP : Ce sont des problèmes pour lesquels on peut vérifier une solution rapidement, mais trouver la solution peut prendre un temps énorme.
NP-complet : Ce sont les problèmes les plus difficiles dans NP. Si on trouve une méthode pour résoudre un problème NP-complet rapidement, on pourrait résoudre tous les autres problèmes NP rapidement.

La réduction entre problèmes

L'idée de la réduction est de transformer un problème difficile en un autre problème difficile pour montrer que résoudre l'un des deux implique de résoudre l'autre.

Si on peut résoudre 3-SAT (en vérifiant une formule logique), on peut aussi résoudre le cycle hamiltonien (trouver le chemin optimal dans le TSP).

Implications pratiques

Les solutions exactes sont impraticables pour de grandes tailles
Si P ≠ NP, alors il n'existera probablement pas de solution rapide
On utilise souvent des heuristiques pour des solutions pratiques

Questions pièges à comprendre

Cela signifie que c'est un des problèmes les plus difficiles à résoudre. Il est dans NP, et si on arrive à le résoudre en temps raisonnable, on pourrait résoudre tous les autres problèmes dans NP.

Parce que le nombre de solutions possibles croît de manière exponentielle. Par exemple, pour 20 villes, il y aurait plus de 121 trillions de possibilités, ce qui prendrait un temps infini à explorer.

Les heuristiques permettent d'obtenir des solutions rapides mais approximatives, sans garantir qu'elles soient optimales. Par exemple, un algorithme de plus proche voisin donne une solution rapide mais pas forcément la meilleure.