monpseudo sur blog2geek

Ainsi, puisque TSP peut se réduire
dans HC qui est NP et comme tout problème NP peut se réduire
dans TSP alors TSP est NP-Complet

Nous avons donc vu qu'un problème
qui est en apparence simple est en fait un qui demande des temps de
calculs très long dès que le nombre de ville est assez
élevé. Heureusement, des algorithmes utilisant des méta
heuristiques peuvent arriver a résoudre ce genre de problème
(même si l'on pas pas la certitude que la solution trouvée
est la meilleure) dans des temps acceptable par rapport aux
algorithmes deterministes

Pour monter que TSP est dans la classe
NP-C nous allons monter que
le problème HC, qui est dans la classe NP-C peut se réduire
de façon polynomiale dans TSPd:

Soit G = (V, E) un graphe a n sommet
solution potentielle de HC.

On crée le graphe complet des
sommets V et on affecte aux arêtes la valeur 1 si elle est dans
E et 0 sinon.

Soit S la solution donnée par
TSPd avec K = n. Si la longueur de S est égale à n
alors le graphe G est hamiltonien. En effet cela veut dire que le
chemin de voyageur ne passe que par toutes les arêtes de G et
qu'il ne passe qu'une seule fois par chaque sommet de G ce qui
correspond a la définition d'un parcours hamiltonien.

En fait nous avons montré que le
problème TSP réduit a des villes étant à
des distances de 1 ou 2 est NP-complet, par extension TSP avec des
distances quelconque est aussi NP complet.

comme HC qui est NP-C, alors tout
problème NP peut se réduire dedans. Donc, comme HC peut
se réduire dans TSP, alors tout problème NP peut se
réduire dans TSP

Nous allons tout d'abord mettre se
problème sous une forme décisionnelle (que l'on note
min TSPd):

Soit G un graphe complet (c'est-a-dire
que tous les sommets sont reliés deux a deux), les sommets
représente chaque villes et les arêtes sont value avec
la distance entre les villes. soit K une constante, existe-t-il un
cycle hamiltonien (un chemin qui ne passe qu'une fois par ville) qui
soit de longueur au plus K. La valeur d'un cycle est la somme des
valeurs de ses arêtes.

Pour résoudre ce problème
il suffit de générer de façon non déterministe
un ordre de parcours du graphe (temps linéaire) et de tester
(temps polynomial) si ce graphe est un graphe hamiltonien de longueur
K.

ce mode de recherche correspond a la
définition de la phase d'acceptation d'une machine de Turing
NP: On peut tester en temps polynomial une solution proposée
par un processus non déterministe.

Nous avons donc que TSP appartient bien
à la classe NP

Soit un graphe G non-orienté, un cycle hamiltonien est un cycle dans G qui passe une et une seule fois par chaque sommet v du graphe et revient à son point de départ. Par la suite nous noterons HC les circuits hamiltoniens.

Les cycles hamiltoniens ont été décrit par W.R Hamilton au milieu du XIXe siècle.

Le problème est de décider si il existe un cycle hamiltonien dans le graphe G.Ce problème fait partie des 21 problèmes NP-Complet de Karp.

Le problème du voyageur de
commerce consiste a trouver le plus cours chemin reliant des villes
sur une carte en ne passant qu'une seule fois dans chaque ville. Les
villes sont séparées d'un certaine distance les unes
des autres. Nous noterons ce problème minTSP (minimum du
Traveling Salesman Problem)

Nous allons essayer de monter que ce
problème est NP-Complet, c'est a dire que ce problème
peut se résoudre a l'aide d'une machine non déterministe
en temps polynomiale. Pour cela nous allons monter que ce problème
peut être réduit a un autre problème de classe NP
et nous allons monter que tout problèmes de classe NP peut se
réduire a ce problème (en fait nous allons seulement
monter qu'un problème de classe NP-complet peut se réduire
a ce problème puisque tout problème de classe NP peut
se réduire a un problème de classe NP-Complet fixé)

chemin non optimise



chemin optimise