BE Graphes - Problème ouvert

• Appliquer votre expertise des plus courts chemins à des problèmes complexes de calculs de trajets.

Prérequis

• Les nombreux tests de correction sont validés. Vous avez une confiance absolue dans les résultats de vos algorithmes.
• Vous n'avez pas de problème majeur de performance.

• Choisissez un problème parmi la liste des problèmes ouverts :

  ▸Les véhicules électriques (contraintes d'autonomie)

  • Batterie légère : nous considérons les trajets faisables avec un prototype de véhicule électrique plus léger que les véhicules habituels, équipé d'une batterie sodium-ion, plus petite, nécessitant donc moins de ressources à sa fabrication, et moins d'énergie pour son transport. Son autonomie est limitée à 200km (sans prendre en compte les conditions de trajets comme le dénivelé, le type de conduite, la charge du véhicule ou la météo, ...).
  • Points de recharge : cette batterie peut être rechargée très rapidement, en 2 minutes, à l'aide de stations de recharge particulières (pour simplifier, on considère qu'il y a une station de recharge à tous les sommets situés sur une autoroute - en terme d'autonomie, c'est sensiblement équivalent à supposer qu'il y a une station sur chaque aire de repos).
  • Proposez une méthode de calcul d'itinéraires longs (supérieurs à 200km) permettant à un conducteur d'obtenir le plus court chemin (en temps ou en distance) sans tomber en panne de batterie.
  • Optionnellement, prendre en compte le tarif de la recharge.
  • Pour information, notez que l'autonomie décroît fortement avec la vitesse (comme pour les véhicules thermiques d'ailleurs) : estimation de l'autonomie électrique.

  ▸Le marathon

  • À partir d'un point de départ O, trouver un parcours de marathon formant une boucle (le point d'arrivée doit se trouver à proximité du point de départ).
  • À vous de formaliser les contraintes sur le circuit pour que le parcours soit acceptable.
  • Optionnel : prendre en compte des contraintes de dénivelé.

  ▸Centres de graphe (aka les vendeurs de muguet, ou le placement de vos épiceries de proximité)

  • Un groupe de vendeurs de muguet souhaite proposer des bouquets dans k lieux différents d'un graphe.
  • Ce groupe souhaite placer ses stands de muguet de telle sorte qu'ils soient accessibles à tous le plus équitablement possible (c'est à dire en minimisant la pire accessibilité).
  • Vous devez lui dire où placer ces stands. On supposera qu'ils peuvent être placés sur tout sommet du graphe.
  • Votre méthode doit donc permettre de déterminer k centres dans un graphe de telle sorte que la pire distance (ou le pire temps) d'un sommet à un des centres soit minimale.

  ▸La Balade des confinés (tourner en rond, mais avec style)

  • On considère une personne placée à une origine O et n'ayant accès qu'à un périmètre limité pour effectuer des balades (situation absurde et ridicule, bien entendu).
  • La personne peut se déplacer à pied, à vélo ou en voiture (choix d'un seul mode à la fois).
  • Cette personne cherche à trouver des balades à faire autour de son origine. Pour simplifier, on considère qu'il y a au plus un seul arc entre deux sommets du graphe.
  • Selon les personnes, la définition d'une balade peut être différente. Nous vous en proposons une dans ce sujet. Si vous avez d'autres propositions de balades, discutez en avant avec vos encadrants.
  • Définition de la balade sans détour : dans un périmètre donné, trouver un circuit C et un réel d tel que : C entoure l'origine O et C est le plus court chemin permettant d'entourer O tel que tout point de C est à une distance supérieure ou égale à d de l'origine O. d doit être raisonnablement grand.
  • Extension : trouver la distance d maximale telle que le circuit C existe dans le périmètre fixé.

  ▸Le chemin à l'écart (le parcours ochlophobe)

  • Pour se rendre d'un point A à un point B, un usager (piéton, cycliste, automobiliste : à vous de choisir) souhaite trouver un trajet évitant les lieux (sommets) potentiellement les plus fréquentés.
  • Il souhaite de plus que ce trajet ne soit pas trop long par rapport au plus court chemin (paramètre de tolérance).
  • Trouvez une méthode pour identifier des lieux potentiellement fréquentés (au moins ceux pertinents pour aller de A vers B). À vous de caractériser la notion de lieux fréquentés (ou potentiellement fréquentés). Pour des raisons d'efficacité vous pouvez réduire la zone géographique considérée (en fonction des deux points donnés par l'usager et du paramètre de tolérance).
  • Puis trouvez une méthode pour déterminer le trajet de cet usager.
  • Si vous implémentez votre solution, testez par exemple avec des cartes comprenant des ponts (Toulouse, Paris, ...)
• Proposez un algorithme sans l'implémenter (sauf si vous êtes motivés).
• Essayez de démontrer que votre algorithme donne une solution correcte, bonus : démontrer que la solution est optimale.
• Calculez la complexité de votre algo.

• Vous avez compris en finesse les algorithmes de plus court chemin..
• ..au point d'être capable de les adapter à des problèmes plus complexes.
• Vous êtes fiers de votre implémentation en objets (en Java).