{"id":1251,"date":"2020-06-14T20:22:05","date_gmt":"2020-06-14T18:22:05","guid":{"rendered":"http:\/\/labodemaths.fr\/WordPress3\/?p=1251"},"modified":"2020-09-09T19:16:46","modified_gmt":"2020-09-09T17:16:46","slug":"algorithme-glouton","status":"publish","type":"post","link":"https:\/\/labodemaths.fr\/WordPress3\/algorithme-glouton\/","title":{"rendered":"Algorithme glouton"},"content":{"rendered":"\n

1. Algorithme glouton<\/h2>\n\n\n\n

En informatique<\/a>, un algorithme glouton<\/strong> (greedy algorithm<\/em> en anglais, parfois appel\u00e9 aussi algorithme gourmand<\/strong>) est un algorithme<\/a> qui suit le principe de faire, \u00e9tape par \u00e9tape, un choix optimum local. Dans certains cas cette approche permet d’arriver \u00e0 un optimum global, mais dans le cas g\u00e9n\u00e9ral c’est une heuristique<\/a><\/p>https:\/\/fr.wikipedia.org\/<\/a><\/cite><\/blockquote>\n\n\n\n

Au sens \u00e9troit, plus fr\u00e9quent, une heuristique<\/em> est une m\u00e9thode de calcul qui fournit rapidement une solution r\u00e9alisable, pas n\u00e9cessairement optimale ou exacte, pour un probl\u00e8me d’optimisation<\/a> difficile<\/p>https:\/\/fr.wikipedia.org\/wiki\/Heuristique_(math%C3%A9matiques)<\/a><\/cite><\/blockquote>\n\n\n\n

2. Un exemple : le probl\u00e8me du voyageur de commerce.<\/h2>\n\n\n\n

Un voyageur de commerce doit effectuer un trajet pour visiter 20 villes et revenir ensuite \u00e0 son point de d\u00e9part.
Il cherche \u00e0 minimiser le chemin \u00e0 parcourir.
Un algorithme simple pour r\u00e9pondre \u00e0 ce probl\u00e8me serait de d\u00e9terminer tous les trajets possibles et la distance parcourue associ\u00e9e puis de d\u00e9terminer le trajet le plus court.
Le probl\u00e8me de cet algorithme est qu’il y a en tous : 20\u00d719\u00d718\u00d7……\u00d72\u00d71= 20! ( se lit factorielle de 20 ) trajets possibles.<\/p>\n\n\n\n

Exercice 1<\/h3>\n\n\n\n

Ecrire un script python permettant de calculer la factorielle d’un nombre entier positif.<\/p>\n\n\n\n

Pour r\u00e9soudre le probl\u00e8me du voyageur de commerce, on va pr\u00e9f\u00e9rer mettre en place un algorithme permettant de d\u00e9terminer pour chaque ville la ville la plus proche, puis de construire ainsi un trajet qui minimise la distance entre deux villes successives.
Pas \u00e0 pas, cet algorithme va apporter une solution locale au probl\u00e8me \u00e0 d\u00e9faut d’apporter la meilleure solution.<\/p>\n\n\n\n

3. Mise en place<\/h3>\n\n\n\n

Cr\u00e9er un dossier \u00ab\u00a0voyageur\u00a0\u00bb et y t\u00e9l\u00e9charger le fichier .csv ci-dessous :<\/p>\n\n\n\n

donnes_villes<\/a>T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n

Cr\u00e9er dans le m\u00eame dossier un fichier python \u00ab\u00a0voyageur\u00a0\u00bb et y ins\u00e9rer le code suivant permettant de lire les donn\u00e9es du fichier .csv<\/p>\n\n\n\n

def 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<\/code><\/pre>\n\n\n\n
Tester les commandes :<\/p>\n\n\n\n
>>>donnees=donnees()\n>>>donnees<\/code><\/pre>\n\n\n\n
Quelle est la nature de la variable donnees ?<\/p>\n\n\n\n
Exercice 2<\/h3>\n\n\n\n
Pour faciliter la lecture des donn\u00e9es, on va construire deux dictionnaires permettant de d\u00e9terminer l’indice associ\u00e9 \u00e0 une ville et r\u00e9ciproquement.
L’indice d’une ville correspond \u00e0 l’indice de la ligne du tableau concernant les donn\u00e9es de cette ville.
La premi\u00e8re ville \u00ab\u00a0Annecy\u00a0\u00bb a ainsi pour indice 0, et la ville d’indice 22 correspond \u00e0 \u00ab\u00a0Toulouse\u00a0\u00bb<\/p>\n\n\n\n
Compl\u00e9tant les deux fonctions permettant de construire ces deux dictionnaires.<\/p>\n\n\n\n
def transcription_ville_indice(donnees):\n    \n\ndef transcription_indice_ville(donnees):\n    \n<\/code><\/pre>\n\n\n\n
Les fonctions correctement d\u00e9finies doivent permettre le retour des commandes ci-dessous<\/p>\n\n\n\n
>>> ville_indice=transcription_ville_indice(donnees)\n>>> ville_indice[\"Lille\"]\n10\n>>> indice_ville=transcription_indice_ville(donnees)\n>>> indice_ville[0]\n'Annecy'\n>>> indice_ville[10]\n'Lille'\n>>> ville_indice[\"Toulouse\"]\n22<\/code><\/pre>\n\n\n\n
Exercice 3<\/h3>\n\n\n\n
Ecrire une fonction distance(ville1,ville2) permettant de d\u00e9terminer la distance entre 2 villes en utilisant le contenu de la variable donnees.
Cette fonction devra permettre le retour des commandes ci-dessous.<\/p>\n\n\n\n
>>> distance(\"Lille\",\"Lens\")\n37\n>>> distance(\"Lens\",\"Lille\")\n37\n>>> distance(\"Lens\",\"Lens\")\n0\n>>> distance(\"Toulouse\",\"Annecy\")\n648\n>>> distance(\"Annecy\",\"Toulouse\")\n648<\/code><\/pre>\n\n\n\n
Exercice 4<\/h3>\n\n\n\n
Ecrire une fonction meilleur_trajet() permettant de d\u00e9terminer pour une liste de villes donn\u00e9es, le chemin qui minimise la distance entre 2 villes cons\u00e9cutives.
La premi\u00e8re ville de la liste sera consid\u00e9r\u00e9e comme la ville de d\u00e9part.
On n’oubliera pas de boucler le chemin sur la ville de d\u00e9part.
On pourra utiliser le module folium pour voir le bon d\u00e9roulement de l’algorithme.<\/p>\n\n\n\n
Module folium<\/p>\n\n\n\n
Pour mieux voir le fonctionnement de votre algorithme, il peut \u00eatre int\u00e9ressant d’utiliser le module folium que l’on a d\u00e9j\u00e0 utilis\u00e9 pour placer les stations de v\u00e9los ayant des v\u00e9los disponibles dans un pr\u00e9c\u00e9dent tp.<\/p>\n\n\n\n
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 Paris\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    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).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=\"blue\", weight=2.5, opacity=0.8).add_to(carte)\n    return\n\nvilles=[\"Lens\",\"Marseille\",\"Lille\",\"Toulouse\",\"Bordeaux\",\"Caen\",\"Rennes\",\"Sedan\",\"Grenoble\",\"Paris\"]\n# affiche les marqueurs des villes\naffichage_villes(villes) \n# relie les villes\naffichage_trajet(villes)\n# la carte est un fichier html sauvegard\u00e9 dans le dossier contenant votre script\ncarte.save(outfile='carte.html')<\/code><\/pre>\n\n\n\n
Pour en savoir plus sur folium :<\/p>\n\n\n\n
https:\/\/iut-info.univ-reims.fr\/users\/nocent\/python\/?section=9<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
1. Algorithme glouton En informatique, un algorithme glouton (greedy algorithm en anglais, parfois appel\u00e9 aussi algorithme gourmand) est un algorithme qui suit…<\/p>\n
Read the postAlgorithme glouton<\/span><\/a><\/div>\n","protected":false},"author":2,"featured_media":1252,"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\/1251"}],"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=1251"}],"version-history":[{"count":6,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1251\/revisions"}],"predecessor-version":[{"id":1263,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/posts\/1251\/revisions\/1263"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media\/1252"}],"wp:attachment":[{"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/media?parent=1251"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/categories?post=1251"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/labodemaths.fr\/WordPress3\/wp-json\/wp\/v2\/tags?post=1251"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}