restricted:tc-a:tp4:travaux_pratiques_premiere_seance_2017

Différences

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

Lien vers cette vue comparative

Les deux révisions précédentes Révision précédente
Prochaine révision		 Révision précédente
restricted:tc-a:tp4:travaux_pratiques_premiere_seance_2017 [2017/10/11 18:13] – pprearestricted:tc-a:tp4:travaux_pratiques_premiere_seance_2017 [2017/10/19 09:21] (Version actuelle) – pprea
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>
 +
 +
 +On commencera par implémenter l'algorithme des graphes d'écarts. Il faut pour cela utiliser un algorithme de (plus courts) chemins. On pourra reprendre celui programmé au TP 3 ou utiliser un BFS (cf TD-TP 2).
 +
 +<note important>
 +Si on le souhaite, on peut considérer qu'il peut y avoir plusieurs arcs entre deux mêmes sommets. La représentation des graphes doit alors en tenir compte.
 +
 +Mais ceci n'et pas obligatoire.
 +</note>
 +
 +
 +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.
 +  * 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>