Problem und Probleminstanz
Problem und Probleminstanz
Ein Navi löst immer dieselbe Art von Aufgabe: Es bekommt eine Karte, einen Start und ein Ziel und sucht den kürzesten Weg. Dieselbe Aufgabe stellt sich in Saarbrücken, in Tokio oder in einem Computerspiel – nur mit anderen Daten.
Merke
Ein Problem beschreibt allgemein, was gegeben ist und was gesucht wird, z. B. „Gegeben: ein gewichteter Graph, ein Start- und ein Zielknoten. Gesucht: ein kürzester Weg vom Start zum Ziel.“
Eine Probleminstanz ist ein konkreter Fall dieses Problems mit festen Daten, z. B. „der schnellste Weg von Lebach nach Saarbrücken ohne Verkehr“.
Eine Instanz lösen
S = Saarlouis, D = Dillingen, L = Lebach, W = Schwalbach, V = Völklingen, P = Püttlingen, R = Riegelsberg, H = Heusweiler, B = Saarbrücken
Aufgabe 3: Bist du sicher, dass dein Weg aus Aufgabe 2 wirklich der kürzeste ist? Beschreibe, wie man das sicher überprüfen könnte.
Merke: zulässige und optimale Lösung
Eine Lösung, die alle Bedingungen der Probleminstanz erfüllt, heißt zulässige Lösung (hier: jeder Weg, der in L beginnt, in B endet und nur Straßen der Karte benutzt).
Bei einem Optimierungsproblem gibt es viele zulässige Lösungen. Gesucht ist die optimale Lösung: eine zulässige Lösung, die in Bezug auf ein festgelegtes Kriterium (hier: die Fahrzeit) die beste ist. Es kann mehrere optimale Lösungen geben, wenn sie gleich gut sind.
Alle Wege aufschreiben
Um sicher zu sein, braucht man also alle Wege. Probiere das zuerst an einem kleinen Graphen aus.
Ein etwas größerer Graph
Aufgabe 6: Schreibe alle einfachen Wege von A nach E auf, jeweils als Knotenfolge (z. B. ACE).
Aufgabe 7: Wie bist du in Aufgabe 6 vorgegangen? Wie kannst du sicher sein, dass du keinen Weg vergessen hast? Überlege, wie man das Aufschreiben besser organisieren könnte – gerade bei noch größeren Graphen.