[PDF] Le problème du voyageur de commerce





Previous PDF Next PDF



Chapitre 6: Graphes eulériens et hamiltoniens 6.1 Introduction et les

Si ce chemin est fermé on parlera de cycle eulérien. • Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule 



Cours 7 - voyageur de commerce cycle et chemin hamiltonien

Un chemin hamiltonien est un chemin simple qui contient tous les sommets du graphe. • Sortie : OUI si G contient un chemin hamiltonien NON sinon. 13/14 



NP complétude du problème de lexistence dun chemin hamiltonien

Un chemin dans G est dit hamiltonien lorsqu'il passe une et une seule fois par chaque sommet du graphe. Définition 2. On note HAM(G s



Chemin et circuit hamiltonien Exercice 3 : Eléments de solutions

Si vous voyez des erreurs prévenez moi. Exercice 3 :Chemin et circuit hamiltonien. En utilisant le fait que le problème du chemin hamiltonnien est NP-.



Cheminement eul´erien et hamiltonien 1 Chemins eulériens

chemin hamiltonien est un circuit ou un chemin passant une et une seule fois par tous les sommets de G. Un graphe est hamiltonien s'il admet un cycle ...



Algorithmes quantiques cycles hamiltoniens et la k-coloration des

4 avr. 2016 ... hamiltonien. Le problème du chemin hamiltonien consiste à : - Trouver une chaîne hamiltonienne ou un cycle hamiltonien dans un graphe non ...



ne Condition SuiTsante dExistence dun dans un Graphe Oriente

11 possedera un circuit hamiltonien passant necessairement par l'arc (zO zt) d'oti dans G urn circuit plus long que X



Calculabilité Combinatoire et Complexité

Chemin Hamiltonien est NP-difficile : Réduction de CNF-SAT à Chemin Hamiltonien. Réductions. 10 / 7. Page 6. Transformer une formule φ en graphe Gφ. Donnée de 



Cycles eulériens et hamiltoniens

Un cycle qui passe exactement une fois par chaque sommet d'un graphe est dit. « hamiltonien ». En effet le parcours de la souris depuis sa cage jusqu'à sa ...



Algorithme dEuler pour trouver un circuit hamiltonien dans le cas du

Le jeu (en solitaire) consiste à trouver un parcours pour un cavalier aux échecs qui passe une fois et une seule par chaque case de l'échiquier. L'article d' 



Chapitre 6: Graphes eulériens et hamiltoniens 6.1 Introduction et les

Si ce chemin est fermé on parlera de cycle eulérien. • Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule 



NP complétude du problème de lexistence dun chemin hamiltonien

Un chemin dans G est dit hamiltonien lorsqu'il passe une et une seule fois par chaque sommet du graphe. Définition 2. On note HAM(G s



Chemin et circuit hamiltonien Exercice 3 : Eléments de solutions

En utilisant le fait que le problème du chemin hamiltonnien est NP- ment si L décrit un chemin hamiltonien du graphe G. C'est à dire que L est.



chemins et circuits hamiltoniens

problème posé : Trouver un chemin ou un circuit hamiltonien sur n'importe quelle figure géométrique. définitions : Un chemin hamiltonien passe une 



Algorithme dEuler pour trouver un circuit hamiltonien dans le cas du

L'article d'Euler est antérieur de plus d'un siècle à la publication du jeu icosien d'Hamilton. Il s'agit néanmoins d'un cas particulier de chemin hamiltonien.



Chapitre 13 Théorie des graphes

Un chemin dans un graphe orienté est une séquence (suite) de sommets et d'arcs Un chemin Hamiltonien est un chemin qui contient chaque sommet exactement.





Le problème du voyageur de commerce

Un problème lié au TSP est le problème du chemin hamiltonien : étant donné un graphe. (donné par matrice ou listes d'adjacence) et deux sommets A et B 



Cycles eulériens et hamiltoniens

Un cycle qui passe exactement une fois par chaque sommet d'un graphe est dit. « hamiltonien ». Certains graphes ne possèdent ni cycle hamiltonien ni cycle 



Hamiltonicité dans une grille un jeu denfant ?

En coupant le cycle au niveau de A on a un chemin hamiltonien partant de A. Fig. 2 – Circuit hamiltonien dans une grille paire. Pour les grilles impaires ( 



Searches related to chemin hamiltonien PDF

• Un chemin hamiltonien est un chemin dans le graphe qui passe par tous les sommets une et une seule fois Si ce chemin est fermé (i e il existe une arête reliant le sommet de départ au sommet d'arrivée) on parlera de cycle hamiltonien • Un graphe est dit hamiltonien s'il possède un cycle hamiltonien

What is the problem of Chemin hamiltonien?

Le problème du chemin hamiltonien est le problème de décision qui consiste, étant donné un graphe, à décider s'il admet un chemin hamiltonien. Ce problème est NP-complet, c'est-à-dire qu'on sait vérifier une éventuelle solution dans un temps polynomial en fonction du nombre

Is a Hamiltonian path NP-complete?

A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path. Determining whether such paths and cycles exist in graphs (the Hamiltonian path problem and Hamiltonian cycle problem) are NP-complete .

What is a Hamiltonian cycle?

A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex exactly once. A Hamiltonian path that starts and ends at adjacent vertices can be completed by adding one more edge to form a Hamiltonian cycle, and removing any edge from a Hamiltonian cycle produces a Hamiltonian path.

What is a Hamiltonian graph?

A Hamiltonian cycle, Hamiltonian circuit, vertex tour or graph cycle is a cycle that visits each vertex exactly once. A graph that contains a Hamiltonian cycle is called a Hamiltonian graph .

École polytechnique - X2013 - INF412 Fondements de l"informatique

Le problème du voyageur de commerce

Sujet proposé par David Monniaux et Bruno Salvy (corrigé) On appelleproblème du voyageur de commercele problème informel suivant : étant donné

une carte avec des villes, des chemins et des distances (ou temps de trajet) entre ces villes, fournir

un itinéraire qui passe par toutes les villes, revient à la ville de départ, ne visite chaque ville

qu"une fois, et qui réalise la distance (ou le temps) minimal. On explique ainsi le nom donné

à ce problème : auxixesiècle, les guides à l"usage des voyageurs de commerce proposaient des

itinéraires, sinon minimaux, du moins optimisés. Plus proche de nous, étant donné un ensemble de

positions de trous ou de soudures à réaliser, ainsi que les temps de déplacement de la machine-outil

d"un emplacement à l"autre, donner l"ordre de réalisation optimal est un problème de voyageur

de commerce. Nous nous intéresserons ici au problème formel suivant : on fixe un nombrende sommets d"un graphe orienté, et on se donne une matricennqui à chaque couple(i;j)de sommets associe soit+1, soit un entier naturel, mesurant le coût pour passer sur l"arête(i;j); on se

donne également une borneb, le problème est de décider s"il existe un circuit (un chemin qui

revient à son point de départ) passant exactement une fois par chacun des sommets et dont la

somme des coûts est inférieure ou égale àb. Nous allons montrer que ce problème, noté TSP

(traveling salesman problem), est NP-complet.

1 Mise en jambes

Question 1.1.Montrez que TSP est dans NP.

Solution :La donnée des sommetss1;:::;snsuccessifs dans le circuits1!:::sn!s1est un certificat : clairement, on peut vérifier en temps polynomial qu"il ne passe pas deux fois par le

même sommet et qu"il est bien de coût total inférieur àb.Un problème lié au TSP est le problème duchemin hamiltonien: étant donné un graphe

(donné par matrice ou listes d"adjacence), et deux sommetsAetBdistincts dans ce graphe, dire s"il existe un chemin deAàBqui passe par tous les sommets du graphe, et ne visite chacun qu"une fois. Question 1.2.Montrez que le problème du chemin hamiltonien est dans NP.

Solution :De même qu"à la question précédente, le chemin est un certificat.Le problème ducircuit hamiltonienest voisin : étant donné un graphe (donné par matrice

ou listes d"adjacence), dire s"il existe un circuit qui passe par tous les sommets du graphe, et ne visite chacun qu"une fois. Question 1.3.Montrez que le problème du circuit hamiltonien est dans NP.

Solution :De même qu"à la question précédente, le circuit est un certificat.Question 1.4.Montrez que le problème du circuit hamiltonien est un cas particulier du problème

du voyageur de commerce. 1 Solution :C"est le problème du voyageur de commerce avec un coût de un pour les arêtes

présentes dans le graphe, et+1pour celles qui n"y sont pas.Question 1.5.Montrez que le problème du circuit hamiltonien se réduit au problème du chemin

hamiltonien.

Solution :Soits1un sommet arbitraire du graphe. On le dédouble en deux sommetss01ets001(s01ets001remplacents1et sont connectés aux mêmes noeuds ques1) et on recherche un chemin

hamiltonien entres01ets001: tout cycle hamiltoniens1!s2!sn!s1du graphe d"origine donne

un chemin hamiltoniens01!:::s2!sn!s001, et réciproquement.Question 1.6.Montrez que le problème du chemin hamiltonien se réduit au problème du circuit

hamiltonien. Solution :SoitGun graphe dans lequel on cherche s"il y a un chemin hamiltonien entre les noeudsaetb. On rajoute un noeudcet deux arêtesb!c!apour obtenir le grapheG0, dans lequel on cherche un circuit hamiltonien. Si l"on trouve un tel circuit, on peut le mettre sous la formec!a!v1! !vn!b!cet alorsa!v1! !vn!best un chemin hamiltonien dansG. Réciproquement, tout chemin hamiltoniena!v1! !vn!bdansG

donne un circuit hamiltonienc!a!v1! !vn!b!cdansG0.En utilisant le fait que 3SAT (dit aussi 3CNFSAT) est NP-complet, on a donc les réductions

suivantes :voyageur de commercecircuit hamiltonienchemin hamiltonien3SAT q1.4q1.5 q1.6q1.1q1.3 q1.2

Il reste donc à prouver que l"on peut réduire 3SAT vers le problème du chemin hamiltonien (la

flèche en pointillés).

2 Réduction 3SAT vers le problème du chemin hamiltonien

Il s"agit, à partir d"un problème 3SAT, de construire un graphe de taille polynomiale en celle du problème, qui aura un chemin hamiltonien entre deux points distingués si et seulement si ce problème 3SAT a une solution, ce chemin permettant de construire une solution du problème

3SAT, et réciproquement une solution du problème 3SAT permettant de construire un chemin

hamiltonien. . On va supposer que l"on dispose d"un graphe TRIPLETTE ayant les propriétés suivantes : 1. TRIPLETTE p ossède,en treautres noeuds, trois noeuds d"en tréee1,e2ete3, et trois noeudss1,s2ets3, tous distincts. On dit que chaque noeudsicorrespond au noeudei. 2. P ourtout ensem bled"un (resp ectivementdeux, trois) noeuds d"en trée,il ex isteun (resp ec- tivement deux, trois) chemins commençant sur ces noeuds, finissant sur les noeuds de sortie correspondant respectifs, et tels qu"à eux tous, ces chemins passent par chaque noeud une et une seule fois. 2

3.P ourtout ensem bled" un(resp ectivementdeux, trois) noeuds d"en trée,il n"existe qu"un

(respectivement deux, trois) chemins commençant sur ces noeuds, finissant sur des noeuds de sortie, et, dans leur ensemble, passant par chaque noeud une et une seule fois. SoitC1^ ^Cmle problème 3SAT, chaqueCiétant une clause formée sur les variables propositionnellesy1;:::;yn. On construit le graphe formé : Des noeuds v1;:::;vn+1. Les noeudsv1;:::;vnsont respectivement associés aux variables y

1;:::;yn.

De mcopies de TRIPLETTE, chacune correspondant à une clauseCi, avec les 3 entrées et sorties respectives étiquetées par les variables de la clause. P ourc haquev ariableyi, on répertorie les clausesCi1;:::;Cipdans laquelle elle intervient positivement, aveci1<< ip; on connectevià l"entrée correspondante àyidansCi1, la sortie correspondante deCi1à l"entrée correspondante deCi2, etc., et la sortie deCip

est connectée àvi+1. On appelle ces branchements le "sous-graphe positif associé àyi».

On op èreexactemen tde la même manière p ourles clauses où elle in tervientnégativ ement.

On appelle ces branchements le "sous-graphe négatif associé àyi». Question 2.1.Montrez qu"à tout chemin hamiltonien dev1àvn+1on peut associer une valuation dey1;:::;ynsatisfaisantC1^ ^Cm. Solution :Soit un tel chemin. Pour toute variable propositionnelleyi, le chemin hamiltonien

part devisoit vers le sous-graphe positif associé àyi, auquel cas on associera la valeur "vrai»

àyi, soit vers le sous-graphe négatif associé àyi, auquel cas on associera la valeur "faux» àyi.

Cette valuation est bien définie : on ne peut associer deux valeurs de vérité différentes à une

même variableyi. En effet, le chemin ne peut passer deux fois par un noeudvi. Le chemin doit, par définition d"un chemin hamiltonien, passer dans chaque TRIPLETTE

donc notamment par un noeud d"entrée. Par définition du graphe, cela veut dire que le littéral

associé à la variable qui étiquette le noeud d"entrée est vrai, donc que la clause associée à la

TRIPLETTE est vrai.Question 2.2.Montrez qu"à toute valuation dey1;:::;ynsatisfaisantC1^ ^Cmon peut

associer un chemin hamiltonien. Solution :Pour tout1jn, on choisit comme arête sortante devjcelle vers le sous-graphe

positif associé àyjsiyjest vraie, celle vers le sous-graphe négatif associé àyjsiyjest fausse;

on choisit comme arête entrante devj+1celle depuis le sous-graphe positif associé àyjsiyjest

vraie, celle depuis le sous-graphe négatif associé àyjsiyjest fausse. Soit1im, considérons la TRIPLETTE correspondant àCi. La valuation satisfait la clauseCi; elle rend donc vrais un, deux ou trois littéraux dansCi. Ceci correspond à une, deux

ou trois arêtes arrivant sur les noeuds d"entrée, et une, deux ou trois arêtes partant des noeuds de

sortie. D"après la 2 epropriété de la TRIPLETTE, on peut trouver trois chemins partant de ces noeuds d"entrée et arrivant aux noeuds de sortie correspondants, qui, pris tous ensemble, passent une fois exactement par chaque noeud de la triplette. D"après la 3 epropriété, cette construction est unique. Comme la TRIPLETTE est un graphe fini, on peut énumérer toutes les configurations de chemin dedans jusqu"à trouver l"unique configuration qui vérifie ces conditions.

Le chemin ainsi construit est un chemin hamiltonien dev1àvn+1.Question 2.3.Donnez un graphe TRIPLETTE vérifiant les 3 conditions.

3

Solution :Ceci achève la preuve que le problème du chemin hamiltonien, et donc ceux du circuit hamil-

tonien et du voyageur de commerce, sont NP-complets. Le problème du voyageur de commerce

reste NP-complet si les distances indiquées respectent l"inégalité triangulaire, et le reste encore

si elles sont des distances euclidiennes dans le plan.

3 Solutions approchées

Dans le cours, un algorithme en temps polynomial a été présenté pour trouver un chemin

presque optimal (à un facteur 2 de l"optimal) lorsque la matrice des coûts est symétrique et

vérifie l"inégalité triangulaire : siAest la matrice,Aij+AjkAikpour tout(i;j;k). Toujours

avec cette hypothèse d"inégalité triangulaire, mais maintenant sans la symétrie de la matrice,

les meilleurs algorithmes connus s"approchent de l"optimum à un facteurlogn. L"idée du plus

classique d"entre eux remonte à 1982 et mène à un facteurlog2nde l"optimum. Ce résultat n"a

été amélioré que très récemment, en 2008, où une solution à un facteur0;999log2nde l"optimum

a été élaborée. Cette section repose sur le résultat plus simple de 1982.

Question 3.1.Montrer que sans l"hypothèse d"inégalité triangulaire, il n"existe pas d"algorithme

pour trouver une solution approchée à un facteur constant en complexité polynomiale sauf si P=NP. [Indication : prendre un problème de circuit Hamiltonien et rendre le graphe complet en y rajoutant toutes les arêtes manquantes avec un coûtc >1.] Solution :Si le graphe possède un circuit hamiltonien, alors un circuit de voyageur de commerce

optimal sur le graphe modifié a un coûtn, alors qu"un circuit qui n"est pas optimal possède au

moins une arête de coûtcet donc un coût total d"au moinsn+(c1). Si on choisitc >(1)n+1

alors une solution approchée à un facteurde l"optimum est le circuit hamiltonien s"il en existe 1

et a un coût supérieur ànsinon.À partir de maintenant, nous considérons que la matrice de coût vérifie l"inégalité triangulaire.

Question 3.2.Montrer que tout circuit est au plus à un facteurnde l"optimal.

Solution :Toute arête joint deux sommets qui appartiennent au circuit optimal. Par l"inégalité

triangulaire, son coût est donc borné par celui du chemin optimal. Comme il y anarêtes dans

un circuit, le coût total est donc à un facteurnde l"optimal.On admettra qu"il est possible de trouver en complexité polynomiale un recouvrement de

tous les sommets du graphe par une union de circuits (chaque sommet du graphe appartient à

un et un seul de ces circuits), la somme des coûts de cette union étant optimale. (L"algorithme

correspondant s"appelle "la méthode hongroise"). Question 3.3.Montrer que la somme de ces coûts est au plus celle du circuit optimal, et que le nombre de circuits est au plusn=2. 4 Solution :Puisque la somme des coûts est optimale, et que le circuit optimal est une telle union

de circuits réduite à un seul circuit, le circuit optimal est plus coûteux que la couverture optimale

par des circuits. Chaque circuit a longueur au moins 2, ce qui permet de borner leur nombre.Question 3.4.En choisissant un sommet dans chacun de ces circuits et en considérant récur-

sivement le sous-graphe induit par ces sommets, montrer que l"on aboutit à une solution à un facteurlog2nde l"optimal en complexité polynomiale. Solution :Le sous-grapheG0induit par ces sommets peut à nouveau être couvert de manière optimale par des circuits. Le coût de cette couverture est encore majoré par celui du circuit optimal : du circuit optimal sur le graphe entier on déduit une couverture des sommets deG0

par un circuit en remplaçant les suites d"arêtes qui sortent deG0par une seule arête de coût

moindre (par inégalité triangulaire). On obtient alors un nombre de circuits borné parjG0j=2. La

procédure se répète au pluslog2nétapes, et à chaque fois la couverture par des circuits a coût

borné par celui du circuit du voyageur de commerce optimal. À l"inverse, on peut recoller un circuit qui passe par les sommets deG0et les circuits cou- vrantG: il suffit de parcourir chaque circuit couvrantGen partant de l"arête provenant deG0

et remplaçant l"arête qui termine le circuit par une arête reliant ce sommet au suivant dans le

cycle couvrantG0. Le coût total est alors borné par la somme des coûts des circuits couvrantG

et du circuit deG0. Procédant ainsi dans la remontée de la récursion, on obtient un coût total

borné parlog2nfois l"optimum.Références [1] Da vidL. Applegate, Rob ertE. Bixb y,V asekCh vátal,and Will iamJ. Co ok.The trave- ling salesman problem : a computational study. Princeton university press, 2007. ISBN

9780691129938.

[2] inequality.ACM Trans. Algorithms, 4(4) :Art. 47, 15, 2008. ISSN 1549-6325. doi:

10.1145/1383369.1383378. URLhttp://dx.doi.org/10.1145/1383369.1383378.

[3] A. M. F rieze,G. Galbiati, and F. Maffioli. On the w orst-casep erformanceof some algorithms for the asymmetric traveling salesman problem.Networks, 12(1) :23-39, 1982. ISSN 0028-

3045. doi: 10.1002/net.3230120103. URLhttp://dx.doi.org/10.1002/net.3230120103.

[4] Mic haelMa chteya ndP aulY oung.An introduction to the general theory of algorithms. Computer science library, Theory of computation series. North-Holland, New York, 1978.

ISBN 044400226X.

[5] Sarta jSahni and T eofiloGonzale z.P-complete approximation problems.J. Assoc. Comput.

Mach., 23(3) :555-565, 1976. ISSN 0004-5411.

5quotesdbs_dbs44.pdfusesText_44
[PDF] de l'année 1789 ? l'exécution du roi cm1

[PDF] graphe d'ordonnancement

[PDF] sujet algorithme bts sio corrigé

[PDF] calcul matrice booléenne

[PDF] calcul matriciel bts

[PDF] prise de note rapide tableau abréviations

[PDF] sauzay programme

[PDF] programme voltaire

[PDF] un petit paragraphe sur l'environnement

[PDF] exemple de texte argumentatif sur l'environnement

[PDF] texte sur l'environnement

[PDF] texte argumentatif sur l'environnement 4am

[PDF] protection de l'environnement définition

[PDF] graphe probabiliste calculatrice

[PDF] graphe étiqueté