Dominierende Mengen

Begriffe: Näherungslösung, Greedy-Verfahren, Dominierende Menge, Backtracking

Der Bildungsplan bietet zwei verschiedene Beispiele für NP-vollständige Probleme an: Dominierende Mengen und das Kartenfärbeproblem. Ein weiteres Standardbeispiel ist das Traveling Salesman Problem. Beim Kartenfärbeproblem wird nicht ganz so schön das Konzept "Wähle die Erweiterung der bisherigen Teillösung, die den größten Gewinn/das beste Ergebnis verspricht" deutlich. Die Wahl der Farbe des nächsten Knotens ist recht willkürlich, wenn man nicht eine bisher noch gar nicht benutzte Farbe wählt und damit das Ergebnis verschlechtert. Daher empfiehlt sich ein Einstieg mit dem Problem, eine möglichst kleine dominierende Menge zu finden.

Die Bestimmung einer möglichst kleinen dominierenden Menge erscheint auf den ersten Blick nicht schwerer als die bisherigen Probleme. Anhand des Problems, Eisverkaufsstände nach bestimmten Kriterien über die Stadt zu verteilen, kann aber gezeigt werden, dass es gar nicht so einfach ist, eine optimale Lösung zu finden. Wenn man eine Lösung gefunden hat, ist man sich in der Regel nicht sicher, ob es nicht noch eine bessere gibt. Der Nachweis gelingt nur, wenn man alle Möglichkeiten, die Eisstände zu verteilen, untersucht und die beste ausgewählt hat. Um den Schülerinnen und Schülern das Ausprobieren vieler Varianten zu erleichtern, können Sie ihnen neben dem Arbeitsblatt fünfzehn "Eistüten"-Bilder ausgeben, die man auf dem Stadtplan verteilen kann. Fünfzehn Eisstände sind auf jeden Fall ausreichend, um die Stadt abzudecken.

Händisch ist es kaum möglich, alle Varianten auszuprobieren. Dies wird deutlich, wenn man die Anzahl der möglichen Teilmengen der Knoten des Graphen berechnet. Da jeder Knoten dazugehören kann oder auch nicht, gibt es für jeden Knoten 2 Möglichkeiten. Damit ergibt sich bei n Knoten die Anzahl der Möglichkeiten mit 2ⁿ (im Einstiegsbeispiel also 2³¹ ≈ 2,1 Milliarden). Einige scheiden davon sicherlich sofort aus, aber wer kann wissen, ob eine ungewöhnliche Lösung nicht doch ein besseres Gesamtergebnis bringt. Mit Hilfe des Graphentesters können für kleinere Graphen per Backtracking ("Dominierende Menge (Vollständig)") alle Varianten durchprobiert und die optimale Lösung bestimmt werden.

Sollten Sie das Thema Backtracking im Unterricht schon behandelt haben, können Sie das Verfahren an dieser Stelle erneut aufgreifen. Andernfalls können Sie es an dieser Stelle einführen oder es auch bei der Aussage belassen, dass alle Varianten durchprobiert werden. Für den weiteren Unterrichtsverlauf reicht es zu wissen, dass dieser Algorithmus systematisch alle Varianten durchprobiert.

Dazu wird der Algorithmus im Simulationsmodus ausgeführt und Graphen mit 5-10 Knoten untersucht. Stellt man den Geschwindigkeitsregler bei 5 Knoten so ein, dass es etwa 3 Sek. dauert, den Algorithmus vollständig (ohne Einzelschrittmodus) auszuführen, dann benötigt man mit 10 Knoten etwa 25=32 Mal so lange. Eine Wartezeit von 1,5 min ist schon recht eindrucksvoll. Ziel ist es, dass die Schülerinnen und Schüler erkennen, dass das Hinzufügen eines einzigen Knotens die Laufzeit verdoppelt. Sie liegt also in O(2ⁿ).

Dass man keine guten Algorithmen mit polynomieller Laufzeit für diese Art von Problemen kennt, kann man den Schülern nur mitteilen. Es ist im Bildungsplan nicht vorgesehen, den Begriff der NP-Vollständigkeit einzuführen. Es reicht, wenn Schüler erklären können, wie die exponentielle Laufzeit zustande kommt und dass diese so schnell steigt, dass der Algorithmus für größere Graphen auch mit sehr schnellen Rechnern in sinnvoller Zeit nicht durchführbar ist.

Sie sollen lernen, dass in diesen Fällen eine Näherungslösung die einzige praktikable Lösung ist. Der Bildungsplan schlägt das Greedy-Verfahren als Beispiel für eine Strategie vor, eine Näherungslösung zu finden. Andere Verfahren sind denkbar, aber nicht so leicht zugänglich. Es ist aber sicher sinnvoll, andere Verfahren zu zeigen (im Graphentester stehen für verschiedene Probleme fertige Algorithmen bereit), damit nicht der Eindruck entsteht, dass die Greedy- Strategie die einzige Möglichkeit sei.

Die Grundidee des Greedy-Verfahrens lässt sich leicht auch auf andere Probleme übertragen. Die Implementierung bleibt dabei nahezu gleich. Entscheidend für die Qualität der Näherungslösung ist die Auswahl der besten Erweiterung der bisherigen Teillösung: Wie wählt man den nächsten Knoten aus, der zur dominierenden Menge dazugehören soll?

Den Schülerinnen und Schülern werden dazu verschiedene Strategien angeboten, die sie zunächst ohne Computerunterstützung bewerten sollen. Danach können die verschiedenen Varianten mit dem Graphentester ausprobiert werden ("Dominierende Menge (Greedy (a-i))"). Stellen Sie den Schülern diese Algorithmen erst zu diesem Zeitpunkt bereit, da die Algorithmen ohne die dazugehörige Aufgabenstellung nicht hilfreich sind und durch die große Zahl verschiedener Varianten die Auswahl im Graphentester dominiert. Es stehen zwei Graphen bereit, bei denen sechs bzw. zehn Knoten mit einem Stern (*) markiert sind, die die optimale dominierende Menge darstellen. Diese Graphen sind so konstruiert, dass die markierten Knoten den Graphen genau einmal überdecken. Kein Knoten ist zwei markierten Knoten benachbart⁷ . Es lässt sich beurteilen, wie gut die Näherungslösung ist. Keine der Strategien liefert immer eine sehr gute Näherungslösung.

Eine Variante der Bestimmung einer Näherungslösung sollten die Schülerinnen und Schüler auch händisch durchführen können. Hier empfiehl sich die Variante "der Knoten, der die meisten noch nicht überdeckten Knoten überdeckt". Diese lässt sich gut händisch oder im Experimentiermodus des Graphentesters mit einem Graph mit 10 oder 15 Knoten durchführen: Im Graphentester startet man mit einer Liste aller Knoten und durchsucht sie nach dem "besten" Knoten. Ausgewählte Knoten kann man aus der Liste entfernen. Die ausgewählten Knoten markiert man rot, die überdeckten grün. In jedem Schritt wählt man denjenigen Knoten aus, bei dem die meisten noch nicht markierten (grauen) Knoten zu sehen sind/benachbart sind. Er selbst zählt auch mit. Wichtig ist, dass auch schon grün markierte Knoten ausgewählt werden dürfen und dann rot eingefärbt werden. Wenn man keinen grauen/unmarkierten Knoten mehr findet, ist man fertig. Es ist erstaunlich, dass man in der Froschperspektive eine recht gute Lösung finden kann, ohne den ganzen Graphen im Blick zu haben.

Allen Näherungslösungen gemeinsam ist, dass sie eine deutlich bessere Laufzeit haben als die Backtracking-Variante. Dies liegt daran, dass bei n Knoten im Graphen maximal n mal der "beste" Knoten ausgewählt und der dominierenden Menge hinzugefügt wird. Wenn die Auswahl in polynomieller Zeit durchführbar ist, dann ist es auch der ganze Algorithmus. Es ist sehr schwer, die Größenordnung der Laufzeit für einen Algorithmus zu ermitteln, da es dabei auf die Laufzeit der Operationen auf dem Graphen ankommt. Diese hängt mit der gewählten Repräsentation und der Implementierung der Operationen in der Klasse Graph zusammen (siehe Repräsentation von Graphen). Da diese den Schülerinnen und Schülern nicht bekannt ist, können sie nur die polynomielle Laufzeit feststellen. Dies kann aber zum Anlass genommen werden, sich über die Repräsentation von Graphen Gedanken zu machen.

Ergänzung: asymmetrische Verschlüsselung mit exakten dominierenden Mengen

Wer eine Schnittstelle zur Kryptologie herstellen möchte, kann eine Stunde zur asymmetrischen Verschlüsselung mit Hilfe von Graphen einschieben. Dabei gibt man den Schülerinnen und Schülern einen fertigen Graphen (2 Kopien: Zwischenstufe und verschlüsselte Nachricht), also den öffentlichen Schlüssel und erläutert das Verfahren. Die Schüler verschlüsseln nach dieser Anleitung eine Zahl und legen dem Lehrer die verschlüsselte Nachricht vor. Der Lehrer entschlüsselt diese Zahl "im Kopf".

Daraufhin erhalten die Schüler eine verschlüsselte Nachricht und versuchen, auch die Zahl zu ermitteln (Brechen der Verschlüsselung). Es reicht, einen recht einfachen Graphen zu wählen, da man die exakte dominierende Menge nicht so einfach "sehen" kann. Manchmal kommen Schüler auf die Idee, das Problem mit linearen Gleichungssystemen zu lösen.

Es wird deutlich, dass bei Kenntnis des Geheimnisses die Entschlüsselung einfach, ohne aber sehr schwer ist. Die Kenntnis des öffentlichen Schlüssels hilft dabei nicht.

⁷ Siehe Anleitung zur Erstellung solcher Graphen im Hintergrund.

Unterrichtsverlauf: Herunterladen [odt][298 KB]

Weiter zu Repräsentation von Graphen