Afficher la pageAnciennes révisionsLiens de retourAjouter au livre.Exporter en PDFHaut de page Cette page est en lecture seule. Vous pouvez afficher le texte source, mais ne pourrez pas le modifier. Contactez votre administrateur si vous pensez qu'il s'agit d'une erreur. ====== TP4 ====== Le but de ce TP est d'appliquer la théorie des flots dans les graphes à des problèmes concrets. <note> Le fait de tester toutes vos créations n'est plus explicitement demandé car cela doit **encore & toujours** être fait. </note> Les graphes seront représentés "mathématiquement" par des listes d'adjacence, & plus précisément/concrètement par des dictionnaires de dictionnaires de dictionnaires. Par exemple : <code python> CAPACITE = "capacite" FLUX = "flux" the_graph = {1: {2: {CAPACITE: 5, FLUX: 2}, 3:{CAPACITE: 6, FLUX: 1}}, 2: {3: {CAPACITE: 7, FLUX: 1}, 4: {CAPACITE: 8, FLUX: 1}}, 3: {5: {CAPACITE: 4, FLUX: 2}}, 4: {6: {CAPACITE: 3, FLUX: 2}}, 5: {4: {CAPACITE: 6, FLUX: 1}, 6: {CAPACITE: 8, FLUX: 1}}, 6: {} } </code> Dessinez le graphe ci-dessus. Implémentez l'Algorithme de Ford & Fulkerson. On pourra utiliser les fonctions suivantes : <code python> import math INFINI = math.inf CAPACITE = "capacite" FLUX = "flux" def mise_a_zero_flot(graph): for sommet in graph: for voisin in graph[sommet]: graph[sommet][voisin][FLUX] = 0 def construction_graphe_ecart(graphe_antisymetrique): graphe_ecart = {} for sommet in graphe_antisymetrique: graphe_ecart[sommet] = {} for sommet in graphe_antisymetrique: for voisin in graphe_antisymetrique[sommet]: capacite = graphe_antisymetrique[sommet][voisin][CAPACITE] flux = graphe_antisymetrique[sommet][voisin][FLUX] if capacite > flux: graphe_ecart[sommet][voisin] = capacite - flux if flux > 0: graphe_ecart[voisin][sommet] = flux return graphe_ecart def construction_chemin_via_dfs(graphe_ecart, source, puits): sommets_marques = {} antecedents = {} pile = [source] for sommet in graphe_ecart: antecedents[sommet] = None while pile != []: sommet = pile.pop() if sommet not in sommets_marques: sommets_marques[sommet] = True for voisin in graphe_ecart[sommet]: if voisin not in sommets_marques: antecedents[voisin] = sommet pile.append(voisin) if sommet == puits: return construction_effective_chemin(sommet, antecedents) def construction_effective_chemin(sommet, antecedents): chemin = [] while sommet is not None: chemin.append(sommet) sommet = antecedents[sommet] chemin.reverse() return chemin def min_sur_chemin(chemin, graphe_ecart): minimum = INFINI for i in range(len(chemin) - 1): courant = chemin[i] suivant = chemin[i + 1] if graphe_ecart[courant][suivant] < minimum: minimum = graphe_ecart[courant][suivant] return minimum def ajout_flot(valeur, chemin, graphe_antisymetrique): for i in range(len(chemin) - 1): courant = chemin[i] suivant = chemin[i + 1] if suivant in graphe_antisymetrique[courant]: graphe_antisymetrique[courant][suivant][FLUX] += valeur else: graphe_antisymetrique[suivant][courant][FLUX] -= valeur </code> Dans la fonction construction_graphe_ecart, le résultat graphe_ecart est-il représenté comme the_graph. Pourquoi ? Dans un deuxième temps, on l'appliquera au problème du mariage avec les données suivantes : <code python> CLEOPATRE = "Cleopatre" IPHIGENIE = "Iphigenie" JULIETTE = "Juliette" FANNY = "Fanny" CHIMENE = "Chimene" ACHILLE = "Achille" CESAR = "Cesar" RODRIGUE = "Rodrigue" ROMEO = "Romeo" MARIUS = "Marius" LES_COUPLES = [(CLEOPATRE, ACHILLE), (CLEOPATRE, CESAR), (CLEOPATRE, ROMEO), (IPHIGENIE, ACHILLE), (JULIETTE, CESAR), (JULIETTE, RODRIGUE), (JULIETTE, ROMEO), (FANNY, CESAR), (FANNY, MARIUS), (CHIMENE, RODRIGUE), (CHIMENE, ROMEO)] </code> On résoudra après le problème de "la bataille de la Marne", en supposant que, * Au temps 0, on a autant de taxis que nécessaire dans la ville 14 ("Paris"). * Au temps 50, il faut qu'il y en ait le plus possible dans la ville 0 ("La Marne"). * Chaque ville (intermédiaire) a 10 places de parking (Paris en a autant que nécessaire). * Les routes sont données dans le tableau suivant : <code python> LES_ROUTES = [{'depart': 0, 'capacite': 2, 'arrivee': 1, 'longueur': 5}, {'depart': 0, 'capacite': 3, 'arrivee': 2, 'longueur': 3}, {'depart': 0, 'capacite': 6, 'arrivee': 1, 'longueur': 6}, {'depart': 1, 'capacite': 3, 'arrivee': 2, 'longueur': 6}, {'depart': 1, 'capacite': 7, 'arrivee': 4, 'longueur': 7}, {'depart': 1, 'capacite': 6, 'arrivee': 2, 'longueur': 7}, {'depart': 2, 'capacite': 7, 'arrivee': 4, 'longueur': 4}, {'depart': 2, 'capacite': 6, 'arrivee': 4, 'longueur': 8}, {'depart': 2, 'capacite': 2, 'arrivee': 5, 'longueur': 5}, {'depart': 3, 'capacite': 7, 'arrivee': 5, 'longueur': 5}, {'depart': 3, 'capacite': 3, 'arrivee': 5, 'longueur': 4}, {'depart': 3, 'capacite': 7, 'arrivee': 6, 'longueur': 4}, {'depart': 4, 'capacite': 7, 'arrivee': 5, 'longueur': 8}, {'depart': 4, 'capacite': 8, 'arrivee': 7, 'longueur': 3}, {'depart': 4, 'capacite': 4, 'arrivee': 7, 'longueur': 3}, {'depart': 5, 'capacite': 8, 'arrivee': 6, 'longueur': 8}, {'depart': 5, 'capacite': 4, 'arrivee': 7, 'longueur': 7}, {'depart': 5, 'capacite': 4, 'arrivee': 6, 'longueur': 5}, {'depart': 6, 'capacite': 5, 'arrivee': 9, 'longueur': 3}, {'depart': 6, 'capacite': 5, 'arrivee': 7, 'longueur': 3}, {'depart': 6, 'capacite': 7, 'arrivee': 8, 'longueur': 3}, {'depart': 7, 'capacite': 2, 'arrivee': 8, 'longueur': 8}, {'depart': 7, 'capacite': 2, 'arrivee': 10, 'longueur': 5}, {'depart': 7, 'capacite': 7, 'arrivee': 10, 'longueur': 4}, {'depart': 8, 'capacite': 3, 'arrivee': 11, 'longueur': 4}, {'depart': 8, 'capacite': 5, 'arrivee': 9, 'longueur': 3}, {'depart': 8, 'capacite': 8, 'arrivee': 10, 'longueur': 3}, {'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 8}, {'depart': 9, 'capacite': 4, 'arrivee': 12, 'longueur': 3}, {'depart': 9, 'capacite': 1, 'arrivee': 11, 'longueur': 7}, {'depart': 10, 'capacite': 5, 'arrivee': 12, 'longueur': 7}, {'depart': 10, 'capacite': 3, 'arrivee': 13, 'longueur': 3}, {'depart': 10, 'capacite': 7, 'arrivee': 11, 'longueur': 4}, {'depart': 11, 'capacite': 4, 'arrivee': 14, 'longueur': 8}, {'depart': 11, 'capacite': 2, 'arrivee': 12, 'longueur': 3}, {'depart': 11, 'capacite': 6, 'arrivee': 14, 'longueur': 6}, {'depart': 12, 'capacite': 5, 'arrivee': 13, 'longueur': 6}, {'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 7}, {'depart': 12, 'capacite': 2, 'arrivee': 14, 'longueur': 6}, {'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 5}, {'depart': 13, 'capacite': 2, 'arrivee': 14, 'longueur': 3}, {'depart': 13, 'capacite': 8, 'arrivee': 14, 'longueur': 6}] </code> <note important> Les routes sont à double sens (il ne faut pas se fier aux appellations "départ" & "arrivée"). </note> On pourra commencer par une instance plus petite, par exemple en ne considérant que les villes jusqu'à 9, avec un borne max pour le temps de 15, c'est à dire avec : <code python> LES_ROUTES = [{'depart': 0, 'capacite': 2, 'arrivee': 1, 'longueur': 5}, {'depart': 0, 'capacite': 3, 'arrivee': 2, 'longueur': 3}, {'depart': 0, 'capacite': 6, 'arrivee': 1, 'longueur': 6}, {'depart': 1, 'capacite': 3, 'arrivee': 2, 'longueur': 6}, {'depart': 1, 'capacite': 7, 'arrivee': 4, 'longueur': 7}, {'depart': 1, 'capacite': 6, 'arrivee': 2, 'longueur': 7}, {'depart': 2, 'capacite': 7, 'arrivee': 4, 'longueur': 4}, {'depart': 2, 'capacite': 6, 'arrivee': 4, 'longueur': 8}, {'depart': 2, 'capacite': 2, 'arrivee': 5, 'longueur': 5}, {'depart': 3, 'capacite': 7, 'arrivee': 5, 'longueur': 5}, {'depart': 3, 'capacite': 3, 'arrivee': 5, 'longueur': 4}, {'depart': 3, 'capacite': 7, 'arrivee': 6, 'longueur': 4}, {'depart': 4, 'capacite': 7, 'arrivee': 5, 'longueur': 8}, {'depart': 4, 'capacite': 8, 'arrivee': 7, 'longueur': 3}, {'depart': 4, 'capacite': 4, 'arrivee': 7, 'longueur': 3}, {'depart': 5, 'capacite': 8, 'arrivee': 6, 'longueur': 8}, {'depart': 5, 'capacite': 4, 'arrivee': 7, 'longueur': 7}, {'depart': 5, 'capacite': 4, 'arrivee': 6, 'longueur': 5}, {'depart': 6, 'capacite': 5, 'arrivee': 9, 'longueur': 3}, {'depart': 6, 'capacite': 5, 'arrivee': 7, 'longueur': 3}, {'depart': 6, 'capacite': 7, 'arrivee': 8, 'longueur': 3}, {'depart': 7, 'capacite': 2, 'arrivee': 8, 'longueur': 8}, {'depart': 7, 'capacite': 2, 'arrivee': 10, 'longueur': 5}, {'depart': 7, 'capacite': 7, 'arrivee': 10, 'longueur': 4}, {'depart': 8, 'capacite': 3, 'arrivee': 11, 'longueur': 4}, {'depart': 8, 'capacite': 5, 'arrivee': 9, 'longueur': 3}] </code> voire même plus petit. tc_info/tp6.txt Dernière modification : 2019/09/28 16:34de edauce