Le problème du voyageur de commerce
Question 1 :
Un voyageur de commerce doit visiter une et une seule fois un nombre fini de
villes et revenir à son point d’origine.
Il faut trouver l’ordre de visite des villes qui minimise la distance totale
parcourue par le voyageur.
Question 2 :
Pour un ensemble de n points, il existe au total n! chemins possibles.
Le point de départ et le point d'arrivée sont fixes donc ils ne changent pas la
longueur du chemin.
=> on aboutit à un (n-1)! chemins possibles.
Puisque pour chaque chemin on a deux sens qui ont la même longueur donc
on peut éliminer l'un des deux
donc le nombre de chemins candidats est (n-1)! / 2
Pour chaque chemin candidat : calculons le coût total et sauvegardons le coût
minimal.
Question 3 :
1. Orientation :
On considère qu'un chemin existe dans un sens mais pas dans l'autre
(graphe orienté)
2. Asymétrie :
a. Problème du voyageur de commerce symétrique :
Étant donné un ensemble de nœuds et de distances pour chaque paire de
nœuds, trouver un cycle de longueur minimale qui visite chaque nœud
exactement une fois.
Pour i et j deux nœuds d'une arête, la distance de i à j est la même que celle
de j à i.
b. Problème du voyageur de commerce asymétrique :
Étant donné un ensemble de n noeuds et de distances pour chaque paire de
noeuds,
trouver un cycle de longueur minimale qui visite chaque nœud exactement
une fois.
Cette fois-ci la distance entre deux noeuds i et j d'une arête n'est pas
forcément la même qu'on aille de i à j ou bien
de j à i.
Question 4 :
1. -la poste
2. -la distribution de repas à domicile
3. -l'inspection d'installations (plombier..)
Question 5 :
On a (n-1)! chemins possibles : 6 chemins possibles.
=> 3 chemins candidats.
Les chemins candidats sont :
1-2-3-4-1
1-4-2-3-1
1-3-4-2-1
Calculons le coût pour chaque chemin :
coût 1er chemin : 95
coût 2eme chemin : 95
coût 3eme chemin : 80
=> le chemin le plus optimal est le 3eme chemin avec un coût 80.
Question 6 :
On peut résoudre le problème de deux façons :
- Résolution naïve :
- Résolution itérative :