Diese Woche werden wir technisch und führen Sie in die zentrale Datenstruktur des Kurses ein: Graphen. Sie lernen die Grundlagen kennen und haben dann die Möglichkeit, etwas tiefer in den Code einzutauchen, um mit der Erstellung einer Google Maps-ähnlichen Anwendung zu beginnen.

In dieser Woche werden Sie das Rückgrat Ihrer Kartensuchmaschine zum Laufen bringen. In früheren Kursen, auch in den früheren Kursen dieser Spezialisierung, haben Sie wahrscheinlich die meisten der Klassen erhalten, die Sie für die Erfüllung der Aufgaben benötigten. Aber zu lernen, wie man Klassen von Grund auf entwirft, ist eine Schlüsselqualifikation, die Sie brauchen werden, wenn Sie ein anspruchsvoller Java-Programmierer werden. In dieser Woche werden wir Ihnen die Werkzeuge an die Hand geben, die Sie benötigen, um ein robustes und elegantes Klassendesign für Ihre Kartensuchmaschine zu erstellen. Wir stellen Ihnen ein ähnliches Problem vor und zeigen Ihnen, wie es als Graph dargestellt werden kann. Dann stellen wir Ihnen zwei zentrale Suchalgorithmen vor: die Tiefensuche und die Breitensuche. Schließlich werden wir unser Graphenproblem in eine Reihe von Java-Klassen umwandeln. Ihre Aufgabe bei der Programmieraufgabe in dieser Woche wird darin bestehen, dasselbe zu tun, allerdings im Kontext der Kartensuchmaschine!

In den vergangenen zwei Wochen haben Sie ein gutes Verständnis dafür entwickelt, wie man Klassen zur Darstellung eines Graphen entwirft und wie man einen Graphen zur Darstellung einer Karte verwendet. In dieser Woche werden Sie ein wichtiges Merkmal von Kartendaten zu unserer Graphendarstellung hinzufügen - Entfernungen - indem Sie Ihren Kanten Gewichtungen hinzufügen, um einen "gewichteten Graphen" zu erstellen. Auch wenn dies nur eine kleine Änderung zu sein scheint, können sich die Algorithmen, die für ungewichtete Graphen funktionieren, bei gewichteten Graphen als unwirksam erweisen. Um dieses Problem zu lösen, werden Sie sich mit fortgeschritteneren Algorithmen für kürzeste Pfade beschäftigen. Zunächst werden Sie sehen, wie man den kürzesten Weg in einem gewichteten Graphen findet, und dann werden Sie sehen, wie man ihn schneller finden kann. Im Projekt werden Sie diese Ideen anwenden, um den Kern jeder guten Mapping-Anwendung zu erstellen: die Suche nach der kürzesten Route von einem Ort zum anderen.

In dieser Woche werden wir über das Problem der Suche nach einem Weg zwischen zwei Punkten hinausgehen und uns auf Probleme konzentrieren, die eine umfassende Wegplanung erfordern. Wenn Sie zum Beispiel Besorgungen machen und 6 verschiedene Orte besuchen wollen, bevor Sie nach Hause zurückkehren, was ist dann die optimale Route? Bei diesem Problem handelt es sich eigentlich um ein sehr bekanntes Problem in der Informatik, das so genannte Travelling Salesperson Problem (TSP). Bei dem Versuch, das Problem zu lösen, werden wir uns mit der Komplexitätstheorie beschäftigen, mit der Frage, was es bedeutet, NP-hart zu sein, und wie man "harte" Probleme mit Hilfe von Heuristiken und Näherungsalgorithmen lösen kann. Zum Abschluss der Woche werden wir zeigen, wie die Neuformulierung eines Problems große Auswirkungen haben kann: etwas, das vorher praktisch unlösbar war, wird nun lösbar!

Sie haben es bis zur letzten Woche unseres Kurses geschafft! Wir freuen uns, dass Sie immer noch bei uns sind. Zur Belohnung gibt es diese Woche keine neuen Inhalte zu lernen. Stattdessen erhalten Sie die Gelegenheit, Ihr Projekt in eine Richtung Ihrer Wahl zu erweitern. Wir hoffen, Sie haben ein paar tolle Ideen für die Gestaltung Ihrer Kartenanwendung und freuen uns darauf, sie in der Peer-Review-Galerie zu sehen. Die Teilnahme an der Peer-Review-Galerie ist optional (die Erweiterung ist jedoch obligatorisch), aber wir hoffen, dass Sie sich dafür entscheiden, daran teilzunehmen.