Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

cd 882 f 827 Introduction Ce problème du voyageur de commerce est un problème de recherche opérationnelle et n ? est pas sans rappeler les cycles hamiltoniens En effet le nom donné à ce problème du voyageur de commerce a pour origine le fait qu ? un circu

Introduction Ce problème du voyageur de commerce est un problème de recherche opérationnelle et n ? est pas sans rappeler les cycles hamiltoniens En effet le nom donné à ce problème du voyageur de commerce a pour origine le fait qu ? un circuit hamiltonien est celui que suivrait un voyageur de commerce partant d ? une ville pour traverser une seule et unique fois n autres villes et revenir à son point de départ et ce à cause de son travail Son objectif est rationnellement d ? effectuer ces trajets ce circuit en un temps minimal une distance minimale ou un coût minimal Pour parvenir à ses fins le voyageur commercial peut bien sûr effectuer des essais successifs différents en notant à chaque essai le temps nécessaire le coût et la distance Il pourra certainement trouver la solution mais cela pourra lui prendre d ? autant plus de temps que le nombre de villes à traverser est lui aussi grand Cette façon de procéder devient donc vite irréalisable Mais avant de poursuivre sur le problème on abordera dans un premier temps les origines du problème avec Sir William Rowan Hamilton Ensuite par poser le problème et la problématique sous jacente puis on énoncera des méthodes de résolution Et pour finir on va donner des exemples qui appliquent une de ces méthodes de résolution sur quelques exemples ou exercices i Les origines du problème du voyageur de commerce ii Le problème du voyageur de commerce iii Méthodes de résolution iv Exemples de résolution du problème du voyageur de commerce a Les origines du problème du voyageur de commerce C ? est en que la notion de cycle hamiltonien est apparue et ce à la suite du lancement par l ? illustre mathématicien Sir William Rowan Hamilton d ? un casse tête celui du voyage fermé autour du monde principalement composé d ? un dodécaèdre régulier en bois C ? est l ? un des soldes de Platon un polyèdre dont les faces sont des pentagones réguliers et dont arêtes de ces pentagones se rencontrent à chacun des sommets Dans son casse tête Hamilton a donné à chacun des sommets du dodécaèdre le nom d ? une grande ville du monde Bruxelles Francfort Delhi etc ce qui n ? est pas sans faire penser au tour du monde en jours écris par Jules Verne en L ? objectif était alors de passer une seule et unique fois dans chaque ville et ce en n ? utilisant que les arêtes du dodécaèdre mais en partant d ? une ville pour au final y revenir Cela revient donc à chercher un cycle Hamiltonien dans la figure car le dodécaèdre étant assez difficilement manipulable Sir Hamilton la remplacer par un graphe planaire isomorphe En effet la difficulté de manipulation venait du fait que pour noter les passages on pouvait planter un clou sur chaque sommet et faire passer une ficelle Rien ne peut amener la preuve du succès de ce dodécaèdre auprès du public