Cette semaine, nous allons entrer dans le vif du sujet en vous présentant la structure de données centrale du cours : Les graphiques. Vous apprendrez les bases et aurez ensuite l'occasion de plonger un peu plus profondément dans le code, afin de vous préparer à construire cette application semblable à Google Maps.

Cette semaine, vous allez mettre en place l'ossature de votre moteur de recherche cartographique. Dans les cours précédents, y compris les cours précédents de cette spécialisation, on vous a probablement fourni la plupart des classes dont vous aviez besoin pour réaliser les travaux. Mais apprendre à concevoir des classes à partir de zéro est une compétence clé dont vous aurez besoin au fur et à mesure que vous deviendrez un programmeur Java plus sophistiqué. Cette semaine, nous allons vous donner les outils dont vous avez besoin pour créer une classe robuste et élégante pour votre moteur de recherche de cartes. Nous vous présenterons un problème similaire et vous montrerons comment il peut être représenté sous la forme d'un graphe. Nous vous présenterons ensuite deux algorithmes de recherche fondamentaux : la recherche en profondeur d'abord et la recherche en largeur d'abord. Enfin, nous transformerons notre problème de graphe en un ensemble de classes Java. Votre tâche de programmation cette semaine consistera à faire la même chose, mais dans le contexte du moteur de recherche de cartes !

Au cours des deux dernières semaines, vous avez acquis une bonne compréhension de la manière de concevoir des classes pour représenter un graphique et d'utiliser un graphique pour représenter une carte. Cette semaine, vous allez ajouter une caractéristique clé des données cartographiques à notre représentation graphique - les distances - en ajoutant des poids à vos arêtes pour produire un "graphe pondéré". Bien que ce changement puisse sembler anodin, les algorithmes qui fonctionnent pour les graphes non pondérés peuvent s'avérer inefficaces pour les graphes pondérés. Pour résoudre ce problème, vous explorerez des algorithmes de plus court chemin plus avancés. Vous verrez d'abord comment trouver le plus court chemin sur un graphe pondéré, puis comment le trouver plus rapidement. Dans le cadre du projet, vous appliquerez ces idées pour créer le cœur de toute bonne application cartographique : trouver le chemin le plus court d'un endroit à un autre.

Cette semaine, nous irons au-delà du problème de la recherche d'un chemin entre deux points, et nous nous concentrerons sur des problèmes nécessitant une planification globale du chemin. Par exemple, si vous voulez faire des courses et visiter six endroits différents avant de rentrer chez vous, quel est l'itinéraire optimal ? Ce problème est en fait un problème très connu en informatique, connu sous le nom de problème du vendeur itinérant (TSP). En tentant de résoudre ce problème, nous explorerons la théorie de la complexité, ce que signifie être NP-Hard, et comment résoudre des problèmes "difficiles" à l'aide d'heuristiques et d'algorithmes d'approximation. Nous terminerons la semaine en montrant comment la reformulation d'un problème peut avoir un impact énorme : rendre un problème qui était effectivement insoluble auparavant, désormais soluble !

Vous avez atteint la dernière semaine de notre cours ! Nous sommes heureux que vous soyez toujours avec nous. En guise de récompense, il n'y a pas de nouveau contenu à apprendre cette semaine. Au lieu de cela, vous aurez l'occasion d'étendre votre projet dans la direction de votre choix. Nous espérons que vous avez des idées intéressantes pour personnaliser votre application cartographique et nous attendons avec impatience de les voir dans la galerie d'évaluation par les pairs. La soumission à la galerie d'évaluation par les pairs est facultative (bien que l'extension soit obligatoire), mais nous espérons que vous choisirez d'y participer.