Différences

Ci-dessous, les différences entre deux révisions de la page.

--- tc_info:tp6 [2018/11/23 10:15] – pprea
+++ tc_info:tp6 [2019/09/28 16:34] (Version actuelle) – edauce
@@ Ligne 1: / Ligne 1: @@
+====== 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}},
+: {3: {CAPACITE: 7, FLUX: 1}, 4: {CAPACITE: 8, FLUX: 1}},
+: {5: {CAPACITE: 4, FLUX: 2}},
+: {6: {CAPACITE: 3, FLUX: 2}},
+: {4: {CAPACITE: 6, FLUX: 1}, 6: {CAPACITE: 8, FLUX: 1}},
+: {}
+             }
+</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.