Le problème du v o y ageur de commerce Dans ce c hapitre, nous allons examiner

Le problème du v o y ageur de commerce Dans ce c hapitre, nous allons examiner le problème bien conn u du v o y ageur de com- merce, app elé aussi problème du commis v o y ageur  en anglais, T r aveling Salesman Pr ob- lem (TSP). L'étude de ce problème nous p ermettra d'in tro duire de nouv elles appro c hes de conception d'algorithmes  par exemple, algorithmes a v ec marc he arrière (b acktr acking ), al- gorithmes basés sur la métho de de sép ar ation et d'évaluation pr o gr essive (br anch-and-b ound ), algorithmes probabilistes et recuit sim ulé  tout en rev o y an t certaines des appro c hes vues précédemmen t (diviser-p our-régner, programmation dynamique, décomp osition p our algo- rithmes parallèles). 1 Présen tation du problème Soit un graphe orien té v alué G = (V, E) où les sommets V représen ten t des villes et les arcs 1 indiquen t les coûts p our aller d'une ville à une autre  les arcs son t orien tés et il est p ossible que le coût p our aller de vi à vj (i ̸= j , car le coût est n ul si i = j ) ne soit pas le même que p our aller de vj à vi . 2 Le problème du v o y ageur de commerce  qui a de nom breuses applications, par exemple, en fabrication de circuits VLSI ou en cristallographie aux ra y ons X  consiste à déterminer un c hemin (un circuit) dans le graphe qui p ermettra de visiter c hacune des villes une seule et unique fois en retournan t ensuite à la ville de départ (le circuit est donc un cycle ), et ce à un coût minimum. v1 v4 v2 v3 2 1 9 3 4 7 6 6 8 Figure 1: Un exemple de graphe p our le problème du v o y ageur de commerce 1 Rapp elons que la diérence en tre une arête et un arc est qu'un arc est orienté alors qu'une arête ne l'est pas. 2 Dans le cas où les coûts son t toujours les mêmes dans les deux directions, on parle alors du symmetric TSP . 1 P ar exemple, soit le graphe présen té à la gure 1. Des exemples de circuits p ossibles a y an t v1 comme p oin t de départ seraien t les suiv an ts, le dernier étan t celui de coût optimal (minim um) : • [v1, v2, v3, v4, v1] : coût 22. • [v1, v3, v2, v4, v1] : coût 26. • [v1, v3, v4, v2, v1] : coût 21. De façon générale, on app elle une tourné e  ou un cycle hamiltonien  d'un graphe orien té à n sommets, un c hemin (une suite d'arcs) qui part d'un sommet v1 , passe exactemen t une fois par c hacun des sommets vi puis retourne au sommet de départ v1 . Le problème du v o y ageur de commerce consiste donc à trouv er une tournée de coût optimal sur un tel graphe. Une appro c he naïv e p our résoudre ce problème consiste à générer l'ensem ble des c hemins p ossibles et à calculer leurs coûts. A v an t d'examiner cette solution, nous examinerons tout d'ab ord, à la pro c haine section, un algorithme p our générer l'ensem ble de tous les c hemins p ossibles, indép endammen t de leur coût. On v erra ensuite (section 3) commen t obtenir un c hemin de coût minimal en généran t l'ensem ble des c hemins p ossibles, puis ensuite com- men t obtenir un tel c hemin sans nécessairemen t examiner tous les c hemins. La section 4, quan t à elle, présen tera deux v ersions parallèles p our l'appro c he br anch-and-b ound. À la sec- tion 5, nous in tro duirons ensuite un algorithme de programmation dynamique p our résoudre le problème du v o y ageur de commerce. Comme nous le v errons, toutes ces solutions on t une complexité très élev ée, rendan t leur utilisation impraticable p our des problèmes comptan t plus d'une cen taine de villes  le record (en 1997) est p our une instance du problème a v ec 7397 villes, mais ce résultat a v ait alors demandé 34 anné es de temps CPU sur un réseau de stations Sun. Nous v errons alors, à la section 6, div erses heuristiques qui nous p ermettron t d'obtenir, en temps raisonnable, des solutions qui, bien que non optimales, ne seron t pas trop mauv aises. 2 Génération des circuits hamiltoniens a v ec marc he ar- rière (b acktr acking ) A v an t d'examiner commen t résoudre le problème du v o y ageur de commerce, nous allons in tro duire la notion d'algorithme a v ec mar che arrièr e (b acktr acking ). P our ce faire, nous allons tout d'ab ord examiner un problème  plus simple, à sa v oir générer l'ensemble des circuits hamiltoniens d'un graphe, et ce en ignoran t les coûts de ces div ers circuits. La stratégie de marc he arrière p ermet d'explorer un espace d'états, soit p our trouv er un état qui satisfait un critère, soit p our générer l'ensem ble des états qui satisfon t ce critère. Le Grand dictionnaire terminologique 3 , qui utilise plutôt le terme de pro cédure de  r etour arrièr e , donne la dé nition suiv an te du b acktr acking :  Pro cédure de rec herc he qui consiste, lorsqu'un c hoix fait à un certain no eud conduit à un résultat inacceptable, à rev enir au no eud d'origine p our faire un autre c hoix. La propriété imp ortan te d'un algorithme a v ec marc he arrière est de reconnaître certains culs-de-sac (de ad ends ), c'est-à-dire, certains états qui son t certains de ne pas conduire à une solution, ce qui évite dans certains cas de faire une rec herc he exhaustiv e de l'ensem ble des états. Dans de nom breux problèmes p our lesquels le b acktr acking est une stratégie appropriée, la sélection d'une solution se fait en eectuan t une série de décisions, c haque décision se faisan t sur la base de l'examen d'un ensem ble d'alternativ es p ossibles. Dans de nom breux cas, l'espace des états p eut être représen té (de façon eectiv e ou virtuelle) par un arbre, où c haque no eud in terne représen te un état in termédiaire et où les feuilles représen ten t un état nal, 3 http://www.granddiction na ir e. com 2 feuilles p ouv an t représen ter ou non une solution v alide. Dans ce con texte, un algorithme a v ec marc he arrière consiste alors à explorer (en profondeur) l'arbre (réel ou virtuel) et, lorsqu'un no eud est rencon tré qui ne satisfait pas un critère approprié de sélection (iden ti cation d'un cul-de-sac), à retourner (b acktr ack ) au no eud paren t p our explorer les autres alternativ es, c'est-à-dire les autres enfan ts de ce paren t. L'algorithme 0 (en MPD) est un algorithme récursif a v ec marc he arrière p our générer l'ensem ble des circuits hamiltoniens sur un graphe. On supp ose que la matrice W des coûts des arcs est dé nie par une v ariable globale et qu'elle est accédée directemen t par la fonc- tion arcExiste, laquelle retourne simplemen t true ou false selon qu'un arc existe ou non en tre les deux sommets (si aucun arc n'existe, alors le cout asso cié est +∞). La v ariable chemin représen te la séquence des sommets déjà visités, c'est-à-dire le c hemin parcouru jusqu'à présen t. Une solution imp ossible (un cul-de-sac) est détectée lorsque le sommet qu'on v oudrait visiter parce qu'il fait partie des sommets pas encore explorés (v ariable s dans la b oucle for) ne p ossède aucun arc le relian t au dernier sommet du c hemin couran t  en d'autres mots, le c hemin couran t ne p eut pas être étendu par ce nouv eau sommet s. L'exploration du c hemin couran t se termine donc et on ten te plutôt d'explorer un autre sommet (par l'in termédiaire des diéren ts v aleurs s n'a y an t pas déjà été visités de la b oucle for). Notons que le c hemin couran t est cloné (ch = cloner(chemin)), c'est-à-dire, copié (en profondeur) p our p ermettre que ce (pré xe de) c hemin puisse être réutilisé p our explorer les div ers autres sommets (ajouterEnQueue(ch, s)). 4 Lorsque tous les sommets p ossibles à explorer p our le c hemin couran t auron t été visités uploads/Geographie/ le-probleme-du-voyageur-de-commerce.pdf

Tags
Administrationcircuit algorithme l'algorithme sommets sommet
Documents similaires
  • 26
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager