Remerciez-le!

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

Algo voyageur de commerce 1

L ? algorithme du voyageur de commerce consiste à trouver le plus court chemin passant par toutes les villes On parle aussi de circuit hamiltonien qui consiste à trouver le plus court chemin passant par tous les noeuds d ? un graphe Le notebook explore quelques solutions approchées et intuitives Ce problème est NP-complet à savoir qu ? il n ? existe pas d ? algorithme qui permette de trouver la solution avec un coût polynômiale C ? est aussi un problème di ?érent du plus court chemin dans un graphe qui consiste à trouver le plus court chemin reliant deux noeuds d ? un graphe mais pas forcément tous les noeuds de ce graphe matplotlib inline Populating the interactive namespace from numpy and matplotlib import random n x random random for in range n y random random for in range n import matplotlib pyplot as plt plt plot x y o Un parcours aléatoire de tous les noeuds de graphe donnera quelque chose de très éloigné de la solution optimale plt plot x x y y o- CLa première constation est que le chemin ne peut pas être optimal car des arcs se croisent On en déduit qu ? une façon d ? améliorer ce chemin est de décroiser certaines parties On peut par exemple choisir deux points au hasard retourner la partie du chemin au milieu de ces deux points et voir si la longueur du chemin s ? en trouve diminuée On peut également parcourir toutes les paires de noeuds possibles C ? est ce qui est implémenté ci-dessous def longueur x y ordre i ordre - x y x i y i d for o in ordre x y x o y o d x -x y -y x y x y return d ordre list range len x print longueur initiale longueur x y ordre def permutation x y ordre d longueur x y ordre d d it while d d it print iteration it d d d d for i in range len ordre - for j in range i len ordre r ordre i j copy r reverse ordre ordre i r ordre j t longueur x y ordre if t d Creturn ordre d t ordre ordre ordre permutation x y list range len x print longueur min longueur x y ordre xo x o for o in ordre ordre yo y o for o in ordre ordre plt plot xo yo o- longueur initiale iteration d iteration d iteration d iteration d iteration d iteration d longueur min Voilà qui est mieux Maintenant supposons que nous faisons une erreur lors du calcul de la distance nous oublions le dernier arc qui boucle le chemin du dernier noeud au premier def longueur x y ordre on change cette fonction d for i in range len ordre n ordre i- o ordre i x y x n y n x y x o y o d x -x y -y return d Cordre