{"id":1273,"date":"2020-06-16T10:24:44","date_gmt":"2020-06-16T08:24:44","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1273"},"modified":"2020-09-09T19:16:31","modified_gmt":"2020-09-09T17:16:31","slug":"voyageur-de-commerce-correction","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/voyageur-de-commerce-correction\/","title":{"rendered":"Voyageur de commerce : correction"},"content":{"rendered":"\n<h2>1. Notre algorithme n&rsquo;est pas optimal.<\/h2>\n\n\n\n<p>L&rsquo;algorithme glouton par recherche de la ville la plus proche pour r\u00e9soudre notre probl\u00e8me du voyageur de commerce n&rsquo;est pas optimal.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"283\" height=\"283\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_1.png\" alt=\"\" class=\"wp-image-1274\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_1.png 283w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_1-150x150.png 150w\" sizes=\"(max-width: 283px) 100vw, 283px\" \/><figcaption>chemin avec recherche de la ville la plus proche<br><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"283\" height=\"283\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_2.png\" alt=\"\" class=\"wp-image-1275\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_2.png 283w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/plus_proche_pas_optimal_2-150x150.png 150w\" sizes=\"(max-width: 283px) 100vw, 283px\" \/><figcaption>Un meilleur trajet.<\/figcaption><\/figure>\n\n\n\n<p>Statistiquement, notre algorithme donne un trajet dont la longueur totale est sup\u00e9rieure d&rsquo;environ 25% \u00e0 celle du trajet optimal.<\/p>\n\n\n\n<h2>2. Proposition de correction<\/h2>\n\n\n\n<p>Le script :<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>import folium # module permettant d'afficher des cartes avec OpenStreetMap\n\nlatitude_Paris=48.65829086\nlongitude_Paris=2.086790085\n# on cr\u00e9e une carte centr\u00e9e sur Lille\ncarte = folium.Map(location=(latitude_Paris,longitude_Paris), tiles='OpenStreetMap', zoom_start=6)\n\ndef affichage_villes(villes):\n    '''\n    affiche sur une carte les diff\u00e9rentes villes pr\u00e9sentes dans la liste villes\n    return : carte avec marqueurs des stations\n    '''\n    # on met un marqueur diff\u00e9rent pour la premi\u00e8re ville\n    indice=ville_indice[villes[0]]\n    latitude=float(donnees[indice][2])\n    longitude=float(donnees[indice][1])\n    localisation=(latitude,longitude)\n    folium.Circle(\n      location=localisation,\n      popup='depart',\n      radius=15000,\n      color='crimson',\n      fill=True,\n      fill_color='crimson'\n   ).add_to(carte)\n    # on place des marqueurs pour les villes\n    for ville in villes:\n        indice=ville_indice[ville]\n        latitude=float(donnees[indice][2])\n        longitude=float(donnees[indice][1])\n        localisation=(latitude,longitude)\n        legende=ville+\" lat : \"+str(latitude)+\" long : \"+str(longitude)\n        folium.Marker(location=localisation, popup = legende,color=\"red\").add_to(carte)\n    return\n\ndef affichage_trajet(chemin):\n    '''\n    affiche sur une carte les diff\u00e9rentes villes pr\u00e9sentes dans la liste villes\n    return : carte avec marqueurs des stations\n    '''\n    trajet=[]\n    for ville in chemin:\n        indice=ville_indice[ville]\n        latitude=donnees[indice][2]\n        longitude=donnees[indice][1]\n        localisation=(float(latitude),float(longitude))\n        trajet.append(localisation)\n    folium.PolyLine(trajet, color=\"red\", weight=2.5, opacity=0.8).add_to(carte)\n    return\n\n\n\ndef donnees():\n    fichier = open(\"donnes_villes.csv\", \"r\")\n    donnees = fichier.read()\n    donnees = donnees.replace (\",\", \".\").split(\"\\n\")\n    donnees=[ t.strip (\"\\r\\n \").split (\";\") for t in donnees ]\n    fichier.close()\n    return donnees\n\ndef transcription_ville_indice(donnees):\n    ville_indice=dict()\n    for i in range(len(donnees)):\n        ville_indice[donnees[i][0]]=i\n    return ville_indice\n\ndef transcription_indice_ville(donnees):\n    indice_ville={}\n    for i in range(len(donnees)):\n        indice_ville[i]=donnees[i][0]\n    return indice_ville\n\ndef distance(ville1,ville2):\n    i1=ville_indice[ville1]\n    i2=ville_indice[ville2]\n    imin=min(i1,i2)\n    imax=max(i1,i2)\n    return int(donnees[imax][imin+3])\n\ndef meilleur_trajet(liste_villes):\n    villes_restantes=liste_villes.copy()\n    meilleur_trajet=[]\n    ville_depart=villes_restantes[0]\n    meilleur_trajet.append(ville_depart)\n    villes_restantes.remove(ville_depart)\n    while len(villes_restantes)>0:\n        ville_plus_proche=villes_restantes[0]\n        ville_depart=meilleur_trajet[-1]\n        distance_min=distance(ville_depart,ville_plus_proche)\n        for ville in villes_restantes:\n            if distance(ville_depart,ville)&lt;distance_min:\n                ville_plus_proche=ville\n                distance_min=distance(ville_depart,ville)\n        villes_restantes.remove(ville_plus_proche)\n        meilleur_trajet.append(ville_plus_proche)\n    meilleur_trajet.append(meilleur_trajet[0])\n    return meilleur_trajet\n\ndonnees=donnees()\nville_indice=transcription_ville_indice(donnees)\nindice_ville=transcription_indice_ville(donnees)\nvilles=[\"Lens\",\"Rennes\",\"Marseille\",\"Lille\",\"Toulouse\",\"Bordeaux\",\"Caen\",\"Sedan\",\"Grenoble\",\"Paris\"]\nprint(villes)\nprint(meilleur_trajet(villes))\naffichage_villes(villes)\naffichage_trajet(meilleur_trajet(villes))\ncarte.save(outfile='carte.html')\n<\/code><\/pre>\n\n\n\n<p>Le retour :<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>>>>runfile('\/Users\/davidlaignel\/Desktop\/nsi_juin\/voyageur.py', wdir='\/Users\/davidlaignel\/Desktop\/nsi_juin')\n['Lens', 'Rennes', 'Marseille', 'Lille', 'Toulouse', 'Bordeaux', 'Caen', 'Sedan', 'Grenoble', 'Paris']\n['Lens', 'Lille', 'Paris', 'Caen', 'Rennes', 'Bordeaux', 'Toulouse', 'Marseille', 'Grenoble', 'Sedan', 'Lens']<\/code><\/pre>\n\n\n\n<p>La carte obtenue dans notre r\u00e9pertoire :<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" width=\"1024\" height=\"958\" src=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/Capture-d\u2019e\u0301cran-2020-06-16-a\u0300-10.15.30-1024x958.png\" alt=\"\" class=\"wp-image-1276\" srcset=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/Capture-d\u2019e\u0301cran-2020-06-16-a\u0300-10.15.30-1024x958.png 1024w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/Capture-d\u2019e\u0301cran-2020-06-16-a\u0300-10.15.30-300x281.png 300w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/Capture-d\u2019e\u0301cran-2020-06-16-a\u0300-10.15.30-768x719.png 768w, https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2020\/06\/Capture-d\u2019e\u0301cran-2020-06-16-a\u0300-10.15.30.png 1368w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><figcaption>La ville de d\u00e9part est entour\u00e9e en rouge.<\/figcaption><\/figure>\n\n\n\n<p>Rappel : Pour installer le module folium en ligne de commande :<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>>>> pip install folium<\/code><\/pre>\n\n\n\n<p>ou aller voir la gestion des packages sur Thonny.<\/p>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>1. Notre algorithme n&rsquo;est pas optimal. L&rsquo;algorithme glouton par recherche de la ville la plus&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/labodemaths.fr\/WordPress3\/voyageur-de-commerce-correction\/\">Read the post<span class=\"screen-reader-text\">Voyageur de commerce : correction<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1276,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[1],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1273"}],"collection":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/comments?post=1273"}],"version-history":[{"count":1,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1273\/revisions"}],"predecessor-version":[{"id":1277,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1273\/revisions\/1277"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1276"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1273"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1273"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1273"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}