Remerciez-le!

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

Problème de voyageurs de commerce Présente par : LAMRINI OTMANE TALHA AMINE Pla

Problème de voyageurs de commerce Présente par : LAMRINI OTMANE TALHA AMINE Planning Introduction Définition Théorie des graphe L’Arbre couvrant de poids minimum Algorithme de Kruskal Algorithme de Prim Etude de cas Introduction et Définition En informatique, le problème du voyageur de commerce, ou problème du commis voyageur1, 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 difficulté. 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 planification 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é). Théorie des graphes POURQUOI LA THÉORIE DES GRAPHES ? - Modélisation : Plusieurs problèmes dans diffé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. L’arbre couvrant de poids minimum Arbre : est une famille particulière de graphe. Définition d’un arbre - Pour un arbre T a n sommets il y a équivalence entre les définitions suivantes : T est un arbre. T est un graphe connexe à n-1 arêtes T est un graphe acyclique à n-1 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 Arbre couvrant : Un arbre couvrant T d’un graphe G(V,E) est: Un graphe partiel, sans cycle. Poids 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) Algorithme 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 1956 par Joseph Kruska Description du problème On considère un graphe connexe non-orienté et pondéré ː chaque arête possède un poids qui est un nombre qui représente le coût de cette arête. Dans un tel graphe, un arbre couvrant est un sous-graphe connexe sans cycle qui contient tous les sommets du graphe. Le poids d'un tel arbre est la somme des poids des arêtes qui le compose. L'objectif de l'algorithme de Kruskal est de calculer un tel arbre couvrant minimum Principe de l'algorithme L'algorithme construit un arbre couvrant minimum en sélectionnant des arêtes par poids croissant. Plus précisément, l'algorithme considère toutes les arêtes du graphe par poids croissant (en pratique, on trie d'abord les arêtes du graphe par poids croissant) et pour chacune d'elles Algorithme de Prim L'algorithme de Prim est un algorithme déterminant un arbre couvrant minimal d'un graphe connexe valué. C'est-à-dire qu'il trouve un sous-ensemble d'arêtes formant un arbre incluant tous les sommets, tel que la somme des poids de chaque arête soit minimal. Si le graphe n'est pas connexe l'algorithme ne déterminera l'arbre couvrant minimal que d'une composante connexe du graphe. Il a été conçu en 1957 par Robert Prim Principe L'algorithme consiste à choisir arbitrairement un sommet et à faire croître un arbre à partir de ce sommet. Chaque augmentation se fait de la manière la plus économique possible. uploads/Geographie/ probleme-de-voyageurs-de-commerce.pdf