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/12 11:30] – pprea | restricted:tc-a:tp4:travaux_pratiques_premiere_seance_2017 [2017/10/19 09:21] (Version actuelle) – pprea |
---|
| ====== 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> |