{"id":1967,"date":"2024-05-12T09:18:00","date_gmt":"2024-05-12T07:18:00","guid":{"rendered":"https:\/\/labodemaths.fr\/WordPress3\/?p=1967"},"modified":"2024-05-16T08:34:29","modified_gmt":"2024-05-16T06:34:29","slug":"nsi-le-probleme-du-voyageur-de-commerce","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/nsi-le-probleme-du-voyageur-de-commerce\/","title":{"rendered":"NSI: le probleme du voyageur de commerce"},"content":{"rendered":"\n<div class=\"wp-block-file\"><a href=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2022\/06\/Probleme-du-voyageur-de-commerce.pdf\">Probleme-du-voyageur-de-commerce<\/a><a href=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2022\/06\/Probleme-du-voyageur-de-commerce.pdf\" class=\"wp-block-file__button\" download>T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>TP : <br>1. T\u00e9l\u00e9charger le fichier csv suivant<\/p>\n\n\n\n<div class=\"wp-block-file\"><a href=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2022\/06\/donnes_villes.csv\">donnes_villes<\/a><a href=\"https:\/\/labodemaths.fr\/WordPress3\/wp-content\/uploads\/2022\/06\/donnes_villes.csv\" class=\"wp-block-file__button\" download>T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>2. Copier et coller le code python suivant dans un fichier voyageur_commerce.py situ\u00e9 dans le m\u00eame dossier que le pr\u00e9c\u00e9dent fichier csv<\/p>\n\n\n\n<p>3. Compl\u00e9ter la fonction meilleur_trajet<\/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&#91;villes&#91;0]]\n    latitude=float(donnees&#91;indice]&#91;2])\n    longitude=float(donnees&#91;indice]&#91;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&#91;ville]\n        latitude=float(donnees&#91;indice]&#91;2])\n        longitude=float(donnees&#91;indice]&#91;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=&#91;]\n    for ville in chemin:\n        indice=ville_indice&#91;ville]\n        latitude=donnees&#91;indice]&#91;2]\n        longitude=donnees&#91;indice]&#91;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=&#91; 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&#91;donnees&#91;i]&#91;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&#91;i]=donnees&#91;i]&#91;0]\n    return indice_ville\n\ndef distance(ville1,ville2):\n    i1=ville_indice&#91;ville1]\n    i2=ville_indice&#91;ville2]\n    imin=min(i1,i2)\n    imax=max(i1,i2)\n    return int(donnees&#91;imax]&#91;imin+3])\n\ndef meilleur_trajet(liste_villes):\n    # on definit les villes_restantes comme une copie de la liste des villes\n    villes_restantes=..........\n    # on d\u00e9finit le meilleur trajet comme une liste vide\n    meilleur_trajet=..........\n    # on d\u00e9finit la ville de d\u00e9part comme la premi\u00e8re ville des villes_restantes\n    ville_depart=.....................\n    # on ajoute la ville_depart au meilleur trajet\n    .................\n    # on enleve la ville_depart au villes_restantes\n    ....................\n    # tant que la liste des villes_restantes n'est pas vide\n    while len(villes_restantes)........... :\n        # la ville la plus proche est la premiere des villes_restantes\n        ville_plus_proche=.....................\n        # la ville_depart est la derniere du meilleur_trajet\n        ville_depart=........................\n        distance_min=distance(ville_depart,ville_plus_proche)\n        # on parcourt les villes_restantes\n        for ville in ...................:\n            # si ville est plus proche de la ville_depart\n            if distance(ville_depart,ville)&lt;...............:\n                # elle devient la nouvelle ville_plus_proche\n                ville_plus_proche=..............\n                # on modifie alors la distance_min\n                distance_min=distance(ville_depart,ville)\n        # on enleve la ville_plus_proche des villes restantes\n        ...................\n        # on l'ajoute au meilleur_trajet\n        ......................\n    # on ajoute au final la ville de depart pour boucler le trajet\n    meilleur_trajet.append(meilleur_trajet&#91;0])\n    return meilleur_trajet\n\ndonnees=donnees()\nville_indice=transcription_ville_indice(donnees)\nindice_ville=transcription_indice_ville(donnees)\nvilles=&#91;\"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\n<\/code><\/pre>\n\n\n\n<p>proposition de correction<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>def meilleur_trajet(liste_villes):\r\n    # on definit les villes_restantes comme une copie de la liste des villes\r\n    villes_restantes=liste_villes.copy()\r\n    # on d\u00e9finit le meilleur trajet comme une liste vide\r\n    meilleur_trajet=&#91;]\r\n    # on d\u00e9finit la ville de d\u00e9part comme la premi\u00e8re ville des villes_restantes\r\n    ville_depart=villes_restantes&#91;0]\r\n    # on ajoute la ville_depart au meilleur trajet\r\n    meilleur_trajet.append(ville_depart)\r\n    # on enleve la ville_depart au villes_restantes\r\n    villes_restantes.remove(ville_depart)\r\n    # tant que la liste des villes_restantes n'est pas vide\r\n    while len(villes_restantes)>0 :\r\n        # la ville la plus proche est la premiere des villes_restantes\r\n        ville_plus_proche=villes_restantes&#91;0]\r\n        # la ville_depart est la derniere du meilleur_trajet\r\n        ville_depart= meilleur_trajet&#91;-1]\r\n        distance_min=distance(ville_depart,ville_plus_proche)\r\n        # on parcourt les villes_restantes\r\n        for ville in villes_restantes:\r\n            # si ville est plus proche de la ville_depart\r\n            if distance(ville_depart,ville)&lt;distance_min:\r\n                # elle devient la nouvelle ville_plus_proche\r\n                ville_plus_proche=ville\r\n                # on modifie alors la distance_min\r\n                distance_min=distance(ville_depart,ville)\r\n        # on enleve la ville_plus_proche des villes restantes\r\n        villes_restantes.remove(ville_plus_proche)\r\n        # on l'ajoute au meilleur_trajet\r\n        meilleur_trajet.append(ville_plus_proche)\r\n    # on ajoute au final la ville de depart pour boucler le trajet\r\n    meilleur_trajet.append(meilleur_trajet&#91;0])\r\n    return meilleur_trajet\r\n<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"<p>TP : 1. T\u00e9l\u00e9charger le fichier csv suivant 2. Copier et coller le code python&#8230;<\/p>\n<div class=\"more-link-wrapper\"><a class=\"more-link\" href=\"https:\/\/labodemaths.fr\/WordPress3\/nsi-le-probleme-du-voyageur-de-commerce\/\">Read the post<span class=\"screen-reader-text\">NSI: le probleme du voyageur de commerce<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1972,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[57],"tags":[],"_links":{"self":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1967"}],"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=1967"}],"version-history":[{"count":2,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1967\/revisions"}],"predecessor-version":[{"id":2489,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1967\/revisions\/2489"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1972"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1967"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1967"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1967"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}