Remerciez-le!

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

Probleme de voyageurs de commerce

Problème de voyageurs de commerce Présente par LAMRINI OTMANE TALHA AMINE CPlanning ? Introduction ? Dé ?nition ? Théorie des graphe ? L ? Arbre couvrant de poids minimum ? Algorithme de Kruskal ? Algorithme de Prim ? Etude de cas CIntroduction et Dé ?nition ? En informatique le problème du voyageur de commerce ou problème du commis voyageur est un problème d'optimisation qui étant donné une liste de villes et des distances entre toutes les paires de villes détermine un plus court chemin qui visite chaque ville une et une seule fois et qui termine dans la ville de départ ? Malgré la simplicité de son énoncé il s'agit d'un problème d'optimisation pour lequel on ne connait pas d'algorithme permettant de trouver une solution exacte rapidement dans tous les cas Plus précisément on ne connait pas d'algorithme en temps polynomial et sa version décisionnelle pour une distance D existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ est un problème NP-complet ce qui est un indice de sa di ?culté C ? C'est un problème algorithmique célèbre qui a généré beaucoup de recherches et qui est souvent utilisé comme introduction à l'algorithmique ou à la théorie de la complexité Il présente de nombreuses applications que ce soit en plani ?cation et en logistique ou bien dans des domaines plus éloignés comme la génétique en remplaçant les villes par des gènes et la distance par la similarité CThéorie des graphes ? POURQUOI LA THÉORIE DES GRAPHES - Modélisation Plusieurs problèmes dans di ?érentes disciplines Réseaux informatique télécommunications chimie applications industrielles ? ? Un graphe peut représenter simplement la structure les connexions les cheminements possibles d ? un ensemble complexe comprenant un grand nombre de situation ? Un graphe est une structure de données puissante pour l ? informatique CL ? arbre couvrant de poids minimum ? Arbre est une famille particulière de graphe ? Dé ?nition d ? un arbre Pour un arbre T a n sommets il y a équivalence entre les dé ?nitions suivantes T est un arbre ? T est un graphe connexe à n- arêtes T est un graphe acyclique à n- arêtes T est un graphe connexe et la suppression de toute arête le déconnecte T est un graphe acyclique et l'ajout de toute arête le rend cyclique C ? Arbre couvrant Un arbre couvrant T d ? un graphe G V E est Un graphe partiel sans cycle CPoids d ? un graphe Le poids o? coût d ? un graphe est la somme des poids des arêtes du graphe On le note ? G CAlgorithme de krusksal ? En informatique l'algorithme de Kruskal est un algorithme de recherche d'arbre recouvrant de poids minimum ARPM ou arbre couvrant minimum ACM dans un graphe connexe non-orientéet pondéré Il a été conçu en par Joseph Kruska CDescription du problème ? On considère un graphe connexe non-orienté et pondéré chaque arête possède un poids qui est