Gymnasium OttweilerSkript zum MINT-Zweig
Informatisches ProblemlösenKapitel 3

Kapitel 3

Informatisches Problemlösen

Skript Informatik · Klasse 10 · MINT

Notebooks in diesem Kapitel DS23–DS29

Alle Notebooks der Klasse · Das grüne Schild an einer Überschrift zeigt, zu welchem Notebook der Abschnitt gehört.

PDF zum Ausdrucken zusammenstellen

Kreuze an, welche Abschnitte du brauchst. Die PDF hat dasselbe Aussehen wie das gedruckte Skript, mit Platz zum Schreiben. Jeden Abschnitt gibt es auch einzeln unter seiner Überschrift, das ganze Kapitel unten auf der Seite.

Ein Paketdienst will die kürzeste Route durch alle Orte finden. Beim Packen für eine Wanderung soll der Rucksack nicht zu schwer werden, aber möglichst viel Nützliches enthalten. Solche Aufgaben heißen Optimierungsprobleme. In diesem Kapitel lernst du, Probleme genau zu beschreiben, alle Möglichkeiten systematisch auszuprobieren und clevere Abkürzungen zu finden, wenn das Ausprobieren zu lange dauert. Du arbeitest dabei vor allem mit Papier und Stift: mit Tabellen, Graphen und Listen. Programmieren musst du in diesem Kapitel nicht.

Das erwartet dich in diesem Kapitel:

  1. Problem und Probleminstanz – Aufgaben genau beschreiben und als Graph, Tabelle oder Liste darstellen.
  2. Optimale Lösung und Brute-Force – alle Möglichkeiten ausprobieren und die beste sicher finden.
  3. Heuristiken – mit einer cleveren Faustregel schnell eine gute Lösung finden.
  4. Das Rucksackproblem – Brute-Force und Greedy an einem zweiten Problem vergleichen.
  5. Aufwand – warum das Ausprobieren schon bei wenigen Orten oder Gegenständen viel zu lange dauert.
  6. Heuristiken bewerten – wie gut eine Faustregel wirklich ist, über viele Probleminstanzen hinweg.
So kannst du es sagen

Mit diesen Satzanfängen beschreibst und begründest du deine Ergebnisse in diesem Kapitel:

Am Ende hilft dir ein Rückblick mit den wichtigsten Begriffen und einem Kompetenz-Check beim Wiederholen.

3.1Problem und Probleminstanz: Aufgaben genau beschreiben DS23

Diesen Abschnitt als PDF (S. 2–18)

Das Jupyter-Notebook aus dem Unterricht: DS23_Problem_Probleminstanz.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Eine Paketbotin startet morgens im Depot, fährt zu mehreren Adressen und kehrt am Ende zurück. Welche Reihenfolge ist die kürzeste? Morgen hat sie andere Adressen – die Frage bleibt aber dieselbe. In der Informatik unterscheidet man deshalb genau zwischen der allgemeinen Fragestellung und dem konkreten Fall mit festen Zahlen. Außerdem lässt man alles weg, was für die Lösung keine Rolle spielt, und stellt den Fall übersichtlich dar: als Tabelle, als Graph oder als Liste. In diesem Abschnitt lernst du diese Werkzeuge kennen. Damit untersuchst du ein berühmtes Problem der Informatik: das Problem des Handlungsreisenden.

Lernziele

Nach diesem Abschnitt kannst du

3.1.1Allgemeine Aufgabe oder konkreter Fall?

Aus dem Matheunterricht kennst du Aufgaben wie „Löse eine quadratische Gleichung“. Das ist eine allgemeine Aufgabe. Welche Gleichung gemeint ist, steht noch nicht fest. Erst bei „Löse x2−5x+6=0x^2 - 5x + 6 = 0“ sind alle Zahlen bekannt, und du kannst loslegen.

Genauso ist es in der Informatik. Eine allgemeine Aufgabe hat noch Leerstellen – wie ein Formular, in dem die Felder noch leer sind. Man nennt sie ein Problem. Füllt man alle Leerstellen mit festen Werten aus, entsteht eine Probleminstanz. Zu einem Problem gibt es also sehr viele Probleminstanzen.

Definition: Problem

Ein Problem ist eine allgemeine Fragestellung mit Leerstellen. Es beschreibt, was gegeben ist und was gesucht wird, aber noch nicht mit festen Werten.

Definition: Probleminstanz

Eine Probleminstanz (kurz: Instanz) ist ein konkreter Fall eines Problems. Alle Leerstellen sind mit festen Werten gefüllt.

Ein Beispiel: „Finde die kürzeste Route zwischen beliebigen Städten“ ist ein Problem. Welche Städte gemeint sind und wie weit sie voneinander entfernt sind, bleibt offen. „Finde die kürzeste Route zwischen genau diesen fünf Städten mit diesen Entfernungen“ ist eine Probleminstanz.

Merke

So erkennst du den Unterschied: Frage dich, ob du sofort anfangen könntest zu rechnen. Fehlen noch Angaben („beliebige Städte“, „eine begrenzte Tragkraft“), ist es ein Problem. Stehen alle Werte fest („diese fünf Gegenstände“, „höchstens 10 kg“), ist es eine Probleminstanz.

Das Problem des Handlungsreisenden

Durch das ganze Kapitel begleitet dich ein berühmtes Problem. Ein Handlungsreisender (ein Vertreter, der Kunden besucht) will mehrere Städte besuchen und am Ende wieder zu Hause ankommen. Er möchte dabei möglichst wenig fahren. Heute stehen Paketdienste, Pflegedienste oder Müllabfuhr vor derselben Frage. Auf Englisch heißt es Traveling Salesman Problem, kurz TSP.

Beispiel: Problem des Handlungsreisenden

Problem: Finde für eine beliebige Menge von Städten mit gegebenen paarweisen Entfernungen die kürzeste Rundreise. Eine Rundreise besucht jede Stadt genau einmal und kehrt zum Ausgangspunkt zurück.

Probleminstanz: Vier Städte A, B, C und D mit diesen Entfernungen (in km):

A B C D
A – 10 15 20
B 10 – 35 25
C 15 35 – 30
D 20 25 30 –

Die Tabelle liest du so: Suche die Zeile des einen Ortes und die Spalte des anderen. Wo sich Zeile und Spalte kreuzen, steht die Entfernung. In der Zeile B und der Spalte D steht zum Beispiel 25: Von B nach D sind es 25 km. Auf der Diagonale stehen Striche, denn von A nach A muss man nicht fahren.

Diese Probleminstanz wird dir in den nächsten Abschnitten immer wieder begegnen. Merke sie dir gut – oder markiere dir die Seite.

Arbeitsauftrag 1: Problem oder Probleminstanz?

Entscheide für jede Aussage, ob es sich um ein Problem (allgemein) oder um eine Probleminstanz (konkret) handelt. Begründe jeweils kurz.

  1. „Packe möglichst wertvolle Gegenstände in einen Rucksack mit maximal 10 kg Tragkraft, wobei diese fünf Gegenstände zur Verfügung stehen: …“
  2. „Packe möglichst wertvolle Gegenstände in einen Rucksack mit begrenzter Tragkraft.“
  3. „Finde den kürzesten Weg von Saarbrücken nach Trier im gegebenen Straßennetz.“
  4. „Finde in einem beliebigen Graphen den kürzesten Weg zwischen zwei beliebigen Knoten.“

Deine Antworten mit Begründung:

Lösung vergleichen
  1. Probleminstanz. Die Tragkraft (10 kg) und die fünf Gegenstände sind fest vorgegeben. Man könnte sofort anfangen, Kombinationen auszuprobieren.
  2. Problem. Welche Gegenstände es gibt und wie groß die Tragkraft ist, bleibt offen („begrenzte Tragkraft“). Das sind Leerstellen.
  3. Probleminstanz. Start, Ziel und Straßennetz stehen fest.
  4. Problem. Graph, Start und Ziel sind „beliebig“, also noch nicht festgelegt. Aussage 3 ist eine Instanz dieses Problems.

Achte auf Signalwörter: „beliebig“, „begrenzt“, „gegebene Städte“ ohne Angabe, welche, deuten auf ein Problem hin. Konkrete Zahlen, Namen und Orte deuten auf eine Probleminstanz hin.

So kannst du es sagen

So begründest du deine Entscheidung – vom einfachen zum fachsprachlichen Satz:

3.1.2Abstrahierte Darstellung: nur das Wichtige behalten

Denk an einen Netzplan von Bussen oder U-Bahnen. Dort fehlen Häuser, Parks und Straßennamen. Die Linien sind gerade gezeichnet, obwohl die echten Strecken Kurven haben. Trotzdem – oder gerade deshalb – findest du darauf schnell heraus, wo du umsteigen musst. Der Plan lässt alles weg, was für diese Frage unwichtig ist.

Dieses Weglassen nennt man Abstrahieren. Für das Problem des Handlungsreisenden sind nur die Orte und ihre Entfernungen wichtig. Straßennamen, Ampeln oder die Farbe der Häuser spielen keine Rolle. Die Entfernungstabelle oben ist deshalb eine abstrahierte Darstellung der Probleminstanz.

Definition: Abstrahierte Darstellung

Eine abstrahierte Darstellung enthält nur die Informationen, die für das Problem wichtig sind. Alles andere wird weggelassen. Häufige Formen sind Tabellen, Graphen und Listen.

Darstellung als Graph

Dieselbe Probleminstanz kannst du auch zeichnen. Jeder Ort wird ein Kreis, und zwischen zwei Orten zieht man eine Linie. An die Linie schreibt man die Entfernung. Eine solche Zeichnung heißt in der Informatik Graph (nicht zu verwechseln mit dem Funktionsgraphen aus Mathe).

Die Probleminstanz mit vier Orten als Graph. Die Zahlen an den Kanten sind die Entfernungen in km (Kantengewichte)
Definition: Graph

Ein Graph besteht aus Knoten (den Objekten, hier den Orten) und Kanten (den Verbindungen zwischen zwei Knoten). Steht an jeder Kante eine Zahl, zum Beispiel eine Entfernung, nennt man diese Zahl Kantengewicht und den Graphen gewichtet.

Im Graphen oben gibt es 4 Knoten und 6 Kanten, denn jeder Ort ist mit jedem anderen direkt verbunden. Die Kante zwischen A und D hat das Gewicht 20, die Kante zwischen B und C das Gewicht 35. Diese beiden Kanten kreuzen sich in der Mitte. Das ist nur eine Folge der Zeichnung: Es gibt dort keinen Knoten, man kann also an der Kreuzung nicht „abbiegen“.

Stolperstein

In einem Graphen zählen nur die Zahlen an den Kanten, nicht die gezeichnete Länge. Im Bild oben ist die Kante A–B (10 km) länger gezeichnet als die Kante A–C (15 km). Das ist kein Fehler. Wo die Knoten auf dem Papier liegen, darfst du frei wählen – Hauptsache, sie sind übersichtlich angeordnet.

Darstellung als Liste

Nicht jedes Problem hat mit Orten zu tun. Beim Packen eines Rucksacks sind die Gegenstände wichtig, und von jedem Gegenstand nur sein Gewicht und sein Wert. Farbe, Marke oder Form lässt man weg. Eine Probleminstanz kann man dann als Liste aufschreiben, zum Beispiel so:

Gegenstand Gewicht (kg) Wert (€)
Zelt 5 60
Schlafsack 4 40
Kocher 2 30

Diese Art von Problem lernst du im Abschnitt über das Rucksackproblem genauer kennen.

Merke

Probleminstanzen werden häufig abstrahiert dargestellt, um sie handhabbar zu machen, z. B. als

Arbeitsauftrag 2: Vom Graphen zur Tabelle

Ein Sportverein plant eine Fahrt zu vier Turnierorten P, Q, R und S. Der Graph zeigt die Entfernungen in km.

Vier Turnierorte mit Entfernungen in km
  1. Übertrage die Entfernungen in die Tabelle.
  2. Nenne die Anzahl der Knoten und der Kanten.
P Q R S
P –
Q –
R –
S –

Anzahl der Knoten und Kanten:

Lösung vergleichen
P Q R S
P – 12 7 16
Q 12 – 11 9
R 7 11 – 14
S 16 9 14 –

Der Graph hat 4 Knoten und 6 Kanten. Jede Entfernung steht zweimal in der Tabelle, zum Beispiel 12 in Zeile P/Spalte Q und in Zeile Q/Spalte P. Das ist kein Zufall – mehr dazu weiter unten im Abschnitt über Symmetrien.

3.1.3Rundreisen systematisch auflisten

Bevor man die kürzeste Rundreise suchen kann, muss man wissen, welche Rundreisen es überhaupt gibt. Wir bleiben bei den vier Orten A, B, C und D und legen fest: Die Reise beginnt und endet in A. Eine Rundreise schreiben wir mit Pfeilen auf, zum Beispiel A → B → C → D → A.

Damit du keine Rundreise vergisst und keine doppelt zählst, gehst du systematisch vor. Das gelingt mit einem Baum, wie in der Abbildung unten:

Alle Rundreisen mit Start in A. Jeder Weg von oben nach unten ist eine Rundreise. Es gibt 3 \cdot 2 \cdot 1 = 6 Stück

Mit Start in A gibt es also 3⋅2⋅1=63 \cdot 2 \cdot 1 = 6 Rundreisen. Die Schreibweise 3⋅2⋅13 \cdot 2 \cdot 1 kürzt man in Mathe mit 3!3! ab (gelesen: „drei Fakultät“). Mehr dazu im nächsten Abschnitt.

Versuch: Andere Reihenfolge im Baum

Zeichne den Baum noch einmal, aber beginne in Ort B. Welche Rundreisen erhältst du? Vergleiche sie mit den sechs Rundreisen oben.

3.1.4Symmetrien erkennen

Wer eine Probleminstanz genau anschaut und dabei auch kleine Varianten ausprobiert (anderer Startort, andere Zahlen), entdeckt oft Regelmäßigkeiten. Solche Regelmäßigkeiten heißen strukturelle Eigenschaften eines Problems. Sie helfen später, Arbeit zu sparen.

Eine wichtige strukturelle Eigenschaft ist die Symmetrie. Im Alltag kennst du Symmetrie von Figuren: Eine symmetrische Figur sieht gespiegelt genauso aus. Bei Tabellen ist es ähnlich. Bei einer symmetrischen Tabelle kannst du an der Diagonale (den Strichen) spiegeln – es kommen dieselben Zahlen heraus.

Merke

Das Untersuchen mehrerer Varianten einer Probleminstanz hilft, Symmetrien und Muster zu erkennen, die spätere Lösungsstrategien vereinfachen können.

Arbeitsauftrag 3: Symmetrien erkennen

Betrachte die Entfernungstabelle der vier Orte A, B, C und D (im Beispiel Problem des Handlungsreisenden).

  1. Welche strukturelle Eigenschaft erkennst du an der Tabelle, wenn du die Entfernung von A nach B mit der Entfernung von B nach A vergleichst? Prüfe auch die anderen Paare. Was bedeutet diese Eigenschaft für die Anzahl der Rundreisen, die du tatsächlich unterscheiden musst?
  2. Wie viele verschiedene Rundreisen gibt es bei vier Orten, wenn du diese Eigenschaft berücksichtigst? Zähle systematisch. Tipp: Suche in der Liste der sechs Rundreisen nach Paaren.

Deine Antworten:

Lösung vergleichen
  1. Die Entfernung von A nach B ist genauso groß wie die von B nach A (jeweils 10 km). Das gilt für alle Paare: Die Tabelle ist symmetrisch zur Diagonale. Für Rundreisen bedeutet das: Eine Rundreise und dieselbe Rundreise rückwärts sind gleich lang, denn sie benutzen genau dieselben Kanten. Man muss deshalb nur eine von beiden untersuchen.
  2. Jede der sechs Rundreisen hat genau eine „Rückwärts-Partnerin“:
Rundreise rückwärts gefahren
A → B → C → D → A A → D → C → B → A
A → B → D → C → A A → C → D → B → A
A → C → B → D → A A → D → B → C → A

Es gibt also nur 6:2=36 : 2 = 3 verschiedene Rundreisen.

Die Symmetrie spart also die Hälfte der Arbeit. Bei vier Orten musst du statt 6 nur 3 Rundreisen untersuchen.

Stolperstein

Die Symmetrie gilt nur, wenn Hin- und Rückweg wirklich gleich lang sind. Das ist nicht immer so. Gibt es Einbahnstraßen, kann der Weg von A nach B kürzer sein als der Weg von B nach A. Misst man statt der Entfernung die Fahrzeit, kann ein Weg bergab schneller sein als bergauf. Dann ist die Tabelle nicht symmetrisch, und du musst alle 6 Rundreisen einzeln untersuchen.

Eine zweite Symmetrie steckt im Startort. Die Rundreise B → D → C → A → B besucht die Orte in derselben Reihenfolge wie A → B → D → C → A. Sie beginnt nur an einer anderen Stelle des Kreises. Beide benutzen dieselben vier Kanten und sind gleich lang. Deshalb darf man den Startort einfach festlegen – wir nehmen immer A.

Arbeitsauftrag 4: Gleiche Rundreise?

Gib bei jedem Paar an, ob es sich um dieselbe Rundreise handelt (also dieselben Kanten benutzt werden). Begründe kurz.

  1. A → C → D → B → A und C → D → B → A → C
  2. A → B → C → D → A und B → A → D → C → B
  3. A → B → C → D → A und A → C → B → D → A

Deine Antworten:

Lösung vergleichen
  1. Ja. Die Orte werden in derselben Reihenfolge besucht, nur der Startpunkt ist ein anderer (C statt A). Beide benutzen die Kanten A–C, C–D, D–B und B–A.
  2. Ja. Das ist die Rundreise A → B → C → D → A rückwärts gefahren und in B begonnen. Kanten: A–B, B–C, C–D, D–A.
  3. Nein. Die erste benutzt die Kanten A–B, B–C, C–D und D–A. Die zweite benutzt A–C, C–B, B–D und D–A. Nur die Kante D–A kommt in beiden vor, die übrigen Kanten sind verschieden. Also sind es verschiedene Rundreisen.

Ein sicherer Test: Schreibe für beide Rundreisen die Kanten auf und vergleiche die beiden Listen.

3.1.5Für Interessierte: Rundreisen mit Python auflisten

Dieser Unterabschnitt ist freiwillig. Für das Kapitel musst du nicht programmieren. Wenn du Lust hast, kannst du mit Python überprüfen, ob du alle Rundreisen gefunden hast.

Die Idee: Für den zweiten, dritten und vierten Ort probiert das Programm jeweils alle drei Orte B, C und D aus. Dafür braucht es drei ineinander geschachtelte for-Schleifen. Eine Reihenfolge ist aber nur dann eine Rundreise, wenn kein Ort doppelt vorkommt. Das prüft eine Bedingung.

orte = ["B", "C", "D"]
anzahl = 0
for ort2 in orte:
    for ort3 in orte:
        for ort4 in orte:
            if ort2 != ort3 and ort2 != ort4 and ort3 != ort4:
                anzahl += 1
                print("A ->", ort2, "->", ort3, "->", ort4, "-> A")
print("Anzahl der Rundreisen:", anzahl)
A -> B -> C -> D -> A
A -> B -> D -> C -> A
A -> C -> B -> D -> A
A -> C -> D -> B -> A
A -> D -> B -> C -> A
A -> D -> C -> B -> A
Anzahl der Rundreisen: 6

Die Ausgabe zeigt dieselben sechs Rundreisen wie der Baum – sogar in derselben Reihenfolge.

3.1.6Übungen

Arbeitsauftrag 5: Probleminstanz als Liste

Eine Lehrerin will 6 Schülerinnen und Schüler so auf zwei Teams aufteilen, dass beide Teams möglichst gleich stark sind. Jede Person hat eine Spielstärke von 1 bis 10: Ali 7, Ben 4, Cem 9, Dana 6, Ela 5, Finn 3.

  1. Formuliere das allgemeine Problem, zu dem diese Situation gehört.
  2. Stelle die Probleminstanz abstrahiert als Liste dar. Welche Angaben lässt du weg?

Deine Antworten:

Lösung vergleichen
  1. Problem: Teile eine beliebige Gruppe von Personen mit gegebenen Spielstärken so in zwei Teams auf, dass sich die Summen der Spielstärken der beiden Teams möglichst wenig unterscheiden.
  2. Probleminstanz als Liste:
Person Spielstärke
Ali 7
Ben 4
Cem 9
Dana 6
Ela 5
Finn 3

Weggelassen wird alles, was für die Aufteilung keine Rolle spielt, zum Beispiel Alter, Klasse oder Lieblingsposition. Eigentlich sind sogar die Namen unwichtig – man könnte die Personen einfach durchnummerieren.

Arbeitsauftrag 6 (Zusatz): Eigenes Problem

Formuliere selbst ein Problem und eine dazu passende Probleminstanz aus einem Bereich deiner Wahl, zum Beispiel Stundenplanung, Einkaufstour oder Gruppeneinteilung. Gib an, wie man die Probleminstanz abstrahiert darstellen kann (Tabelle, Graph oder Liste).

Dein Problem und deine Probleminstanz:

Lösung vergleichen

Ein mögliches Beispiel (Einkaufstour):

  • Problem: Finde für eine beliebige Einkaufsliste und beliebige Geschäfte mit gegebenen Entfernungen die kürzeste Tour, die von zu Hause aus alle nötigen Geschäfte besucht und wieder nach Hause führt.
  • Probleminstanz: Ich brauche Brot, Briefmarken und Batterien. Die Bäckerei ist 400 m entfernt, die Post 700 m, der Elektroladen 900 m. Zwischen den Geschäften sind es 300 m (Bäckerei–Post), 500 m (Post–Elektroladen) und 800 m (Bäckerei–Elektroladen).
  • Darstellung: als Graph mit den Knoten Zuhause, Bäckerei, Post und Elektroladen und den Entfernungen als Kantengewichten – oder als Entfernungstabelle.

Worauf es ankommt: Im Problem stehen Leerstellen („beliebige Einkaufsliste“), in der Instanz stehen feste Werte. Die Instanz muss wirklich zum Problem passen.

3.1.7Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 7: Problem oder Probleminstanz? Noch einmal ●○○

Entscheide bei jeder Aussage, ob es sich um ein Problem oder um eine Probleminstanz handelt. Notiere in der Tabelle auch das Wort oder die Angabe, an der du es erkennst.

  1. „Plane für beliebig viele Freundinnen und Freunde eine Abholreihenfolge, sodass die Fahrt möglichst kurz ist.“
  2. „Mia startet zu Hause und will zur Bäckerei, zum Getränkemarkt und zum Supermarkt. Die Entfernungen stehen in dieser Tabelle: …“
  3. „Teile eine Klasse so in zwei Gruppen auf, dass beide Gruppen gleich groß sind.“
  4. „Packe in einen Koffer mit höchstens 20 kg möglichst nützliche Dinge aus dieser Liste: Jacke 2 kg, Schuhe 1 kg, …“
  5. „Finde die kürzeste Rundreise durch die Landeshauptstädte Saarbrücken, Mainz, Wiesbaden und Stuttgart.“
  6. „Finde in einem Straßennetz den kürzesten Weg zwischen zwei Orten.“
Nr. Problem oder Probleminstanz? daran erkenne ich es
1
2
3
4
5
6
Lösung vergleichen
Nr. Problem oder Probleminstanz? daran erkenne ich es
1 Problem „beliebig viele“ – wer abgeholt wird und wo, steht nicht fest
2 Probleminstanz die Orte und die Entfernungen sind festgelegt
3 Problem „eine Klasse“ – welche Klasse und wie viele Personen, bleibt offen
4 Probleminstanz Tragkraft 20 kg und eine feste Liste von Gegenständen
5 Probleminstanz vier genau genannte Städte; ihre Entfernungen kann man nachschlagen
6 Problem „einem Straßennetz“, „zwei Orten“ – nichts ist festgelegt

Bei Nr. 5 stehen die Entfernungen zwar nicht im Text. Sie sind aber durch die vier Städte eindeutig festgelegt. Deshalb ist es eine Probleminstanz.

Arbeitsauftrag 8: Die Entfernungstabelle lesen ●○○

Mia kauft für eine Klassenparty ein. Sie startet zu Hause (Z) und fährt mit dem Fahrrad zur Bäckerei (B), zum Getränkemarkt (G) und zum Supermarkt (S). Die Tabelle zeigt die Entfernungen in km.

Z B G S
Z – 3 7 6
B 3 – 9 5
G 7 9 – 4
S 6 5 4 –
  1. Wie weit ist es von der Bäckerei zum Supermarkt?
  2. Welches Geschäft liegt am nächsten an Mias Zuhause?
  3. Welche zwei Orte liegen am weitesten auseinander?
  4. Die Tabelle hat 12 Zahlen. Wie viele verschiedene Strecken musste man trotzdem nur messen? Begründe.

Deine Antworten:

Lösung vergleichen
  1. Zeile B, Spalte S: 5 km.
  2. In der Zeile Z ist 3 die kleinste Zahl: Die Bäckerei liegt am nächsten (3 km).
  3. Die größte Zahl in der Tabelle ist 9: Bäckerei und Getränkemarkt liegen 9 km auseinander.
  4. Nur 6 Strecken: Z–B, Z–G, Z–S, B–G, B–S und G–S. Jede Entfernung steht zweimal in der Tabelle, weil der Hinweg genauso lang ist wie der Rückweg. Die Tabelle ist symmetrisch.
Arbeitsauftrag 9: Von der Tabelle zum Graphen ●○○

Skizziere die Probleminstanz aus dem Auftrag Die Entfernungstabelle lesen als Graph. Zeichne für jeden Ort einen Knoten und für jedes Paar von Orten eine Kante. Schreibe die Entfernungen als Kantengewichte an die Kanten. Gib an, wie viele Knoten und Kanten dein Graph hat.

Dein Graph:

Anzahl der Knoten und Kanten:

Lösung vergleichen
Mias Partyeinkauf als Graph (Entfernungen in km)

Der Graph hat 4 Knoten und 6 Kanten. Wo du die Knoten hinzeichnest, ist egal. Wichtig ist nur, dass jede Kante das richtige Kantengewicht trägt. Die Kante B–G (9 km) darf zum Beispiel kürzer gezeichnet sein als die Kante Z–B (3 km).

Arbeitsauftrag 10: Nur das Wichtige behalten ●●○

Lies den Text.

Jonas trägt jeden Samstag Prospekte aus. Er startet mit seinem roten Fahrrad am Kiosk (K) und muss in drei Straßen: Ahornweg (A), Birkenstraße (B) und Lindenplatz (L). Im Ahornweg stehen 12 Häuser, in der Birkenstraße wohnt ein Hund, der immer bellt. Vom Kiosk sind es 400 m zum Ahornweg, 700 m zur Birkenstraße und 500 m zum Lindenplatz. Vom Ahornweg zur Birkenstraße sind es 300 m, vom Ahornweg zum Lindenplatz 600 m und von der Birkenstraße zum Lindenplatz 400 m. Die Prospekte wiegen zusammen 6 kg. Am Ende bringt Jonas die leere Tasche zum Kiosk zurück. Er möchte möglichst wenig fahren.

  1. Nenne die Angaben, die für Jonas’ Frage wichtig sind, und mindestens drei Angaben, die du weglassen kannst.
  2. Stelle die Probleminstanz abstrahiert als Entfernungstabelle (in m) dar.
K A B L
K –
A –
B –
L –

Wichtige und unwichtige Angaben:

Lösung vergleichen
  1. Wichtig sind die vier Orte (Kiosk, Ahornweg, Birkenstraße, Lindenplatz), die sechs Entfernungen und die Bedingung, dass die Fahrt am Kiosk beginnt und endet. Weglassen kannst du zum Beispiel die Farbe des Fahrrads, die Zahl der Häuser, den bellenden Hund und das Gewicht der Prospekte.
  2. Entfernungstabelle in m:
K A B L
K – 400 700 500
A 400 – 300 600
B 700 300 – 400
L 500 600 400 –

Jonas’ Frage ist eine Probleminstanz des Problems des Handlungsreisenden: kürzeste Rundreise durch vier Orte mit Start und Ende am Kiosk.

Arbeitsauftrag 11: Rundreisen beim Partyeinkauf ●●○

Mia aus dem Auftrag Die Entfernungstabelle lesen startet und endet zu Hause (Z) und besucht B, G und S in irgendeiner Reihenfolge.

  1. Liste alle Rundreisen systematisch auf. Tipp: Zeichne dir zuerst einen Baum wie im Abschnitt Rundreisen systematisch auflisten.
  2. Schreibe zu jeder Rundreise die Nummer ihrer Rückwärts-Partnerin.
  3. Wie viele verschiedene Rundreisen muss Mia wirklich vergleichen? Begründe mit der Symmetrie der Tabelle.
Nr. Rundreise rückwärts gefahren ist das Nr.
1
2
3
4
5
6

Anzahl der verschiedenen Rundreisen und Begründung:

Lösung vergleichen
Nr. Rundreise rückwärts gefahren ist das Nr.
1 Z → B → G → S → Z 6
2 Z → B → S → G → Z 4
3 Z → G → B → S → Z 5
4 Z → G → S → B → Z 2
5 Z → S → B → G → Z 3
6 Z → S → G → B → Z 1

Es gibt 6 Rundreisen. Weil die Tabelle symmetrisch ist, ist jede Rundreise genauso lang wie ihre Rückwärts-Partnerin. Mia muss deshalb nur 6:2=36 : 2 = 3 verschiedene Rundreisen vergleichen, zum Beispiel Nr. 1, 2 und 3.

Typischer Fehler: Rundreisen, die nicht mit Z beginnen, zusätzlich aufschreiben. Mia startet aber immer zu Hause.

Arbeitsauftrag 12: Bergauf und bergab ●●●

Noah wohnt unten im Tal (H). Die Schule (S) und die Musikschule (M) liegen weiter oben am Hang, das Freibad (F) ganz oben. Die Tabelle zeigt, wie viele Minuten Noah mit dem Fahrrad braucht. Lies sie so: Zeile = von, Spalte = nach. Von H nach S braucht er also 8 Minuten.

von \ nach H S M F
H – 8 10 15
S 6 – 7 9
M 8 7 – 8
F 9 6 5 –
  1. Prüfe, ob die Tabelle symmetrisch ist. Nenne alle Paare von Orten, bei denen Hin- und Rückweg gleich lange dauern.
  2. Erkläre, warum die Tabelle hier nicht symmetrisch ist.
  3. Noah plant eine Rundreise mit Start und Ende bei H durch S, M und F. Wie viele Rundreisen muss er vergleichen, wenn er die Fahrzeit möglichst klein halten will? Begründe, warum es nicht wie beim Partyeinkauf weniger sind.

Deine Antworten:

Lösung vergleichen
  1. Die Tabelle ist nicht symmetrisch. Nur bei S und M dauern Hin- und Rückweg gleich lange (je 7 Minuten). Bei allen anderen Paaren unterscheiden sie sich, zum Beispiel H → F 15 Minuten, aber F → H nur 9 Minuten.
  2. Bergauf fährt man langsamer als bergab. Von H (unten) nach F (oben) geht es nur bergauf, zurück nur bergab. S und M liegen ungefähr gleich hoch, deshalb sind dort beide Richtungen gleich schnell.
  3. Mit Start in H gibt es wieder 6 Rundreisen. Noah muss alle 6 vergleichen. Eine Rundreise und ihre Rückwärts-Partnerin benutzen zwar dieselben Strecken, aber in der anderen Richtung. Weil die Fahrzeiten in beiden Richtungen verschieden sind, können die beiden Rundreisen verschieden lange dauern. Die Symmetrie, mit der man die Hälfte sparen konnte, fehlt hier.

3.1.8Das Wichtigste in Kürze

Selbstcheck

3.2Optimale Lösung und Brute-Force: alle Möglichkeiten ausprobieren DS24

Diesen Abschnitt als PDF (S. 19–37)

Das Jupyter-Notebook aus dem Unterricht: DS24_Optimale_Loesung_BruteForce.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Im letzten Abschnitt hast du alle Rundreisen durch die vier Orte A, B, C und D aufgelistet. Jetzt geht es um die eigentliche Frage: Welche davon ist die kürzeste? Die sicherste Methode klingt fast zu einfach: Man rechnet für jede Rundreise die Länge aus und nimmt die kürzeste. Diese Methode heißt Brute-Force. Sie findet garantiert die beste Lösung. In diesem Abschnitt führst du sie von Hand durch – und merkst dabei, wo ihr Haken liegt.

Lernziele

Nach diesem Abschnitt kannst du

3.2.1Lösung, zulässige Lösung, optimale Lösung

Stell dir vor, du suchst einen Weg von zu Hause zur Schule. Es gibt viele Wege. Manche kommen aber gar nicht in Frage, zum Beispiel einer, der durch einen gesperrten Park führt. Von den erlaubten Wegen suchst du den besten. Aber was heißt „der beste“? Der kürzeste? Der schnellste? Der mit den wenigsten Ampeln? Erst wenn du das festlegst, kannst du sagen, welcher Weg gewinnt.

Genau diese drei Stufen unterscheidet man auch in der Informatik:

  1. Ein Lösungsvorschlag ist irgendeine Antwort auf die Frage, zum Beispiel irgendeine Reihenfolge der Orte.
  2. Eine zulässige Lösung hält alle Bedingungen des Problems ein.
  3. Eine optimale Lösung ist unter allen zulässigen Lösungen die beste – gemessen an einem vorher festgelegten Kriterium.
Definition: Zulässige Lösung

Eine zulässige Lösung ist eine Lösung, die alle Bedingungen des Problems erfüllt.

Definition: Optimale Lösung

Eine optimale Lösung ist eine zulässige Lösung, die in Bezug auf ein festgelegtes Kriterium die beste ist.

Beim Problem des Handlungsreisenden heißt die Bedingung: Jeder Ort wird genau einmal besucht, und die Reise endet am Startort. Das Kriterium ist die Gesamtlänge. Die beste Rundreise ist also die mit der kleinsten Gesamtlänge.

Vorschlag zulässig? Grund
A → B → C → D → A ✓ jeder Ort genau einmal, zurück in A
A → B → C → A ✗ D wird nicht besucht
A → B → C → B → D → A ✗ B wird zweimal besucht
A → B → C → D ✗ die Reise endet nicht in A
Merke
Stolperstein

„Optimal“ ergibt nur Sinn, wenn das Kriterium feststeht. Die kürzeste Rundreise muss nicht die schnellste sein, wenn auf einer Strecke Stau ist. Achte außerdem darauf: Eine optimale Lösung muss nicht die einzige sein. Haben zwei Rundreisen dieselbe kleinste Länge, sind beide optimal.

Arbeitsauftrag 13: Zulässig oder nicht?

Für die vier Orte A, B, C und D liegen diese Vorschläge vor. Entscheide jeweils, ob sie zulässige Lösungen für das Problem des Handlungsreisenden mit Start in A sind. Begründe, wenn ein Vorschlag nicht zulässig ist.

  1. A → D → C → B → A
  2. A → C → D → A
  3. A → D → B → D → C → A
  4. A → C → B → D → A

Deine Antworten:

Lösung vergleichen
  1. zulässig: Jeder Ort wird genau einmal besucht, die Reise endet in A.
  2. nicht zulässig: B wird nicht besucht.
  3. nicht zulässig: D wird zweimal besucht.
  4. zulässig.

Ob eine Lösung zulässig ist, hat nichts mit ihrer Länge zu tun. Auch eine sehr lange Rundreise ist zulässig, solange sie alle Bedingungen erfüllt.

3.2.2Die Länge einer Rundreise berechnen

Um Rundreisen zu vergleichen, brauchst du ihre Gesamtlänge. Du addierst dafür die Entfernungen aller Teilstrecken. Nimm die Entfernungstabelle der vier Orte zur Hand:

A B C D
A – 10 15 20
B 10 – 35 25
C 15 35 – 30
D 20 25 30 –

Für die Rundreise A → B → C → D → A gibt es vier Teilstrecken. Die Rückfahrt von D nach A gehört dazu – sie wird leicht vergessen.

A-B:  10
B-C:  35
C-D:  30
D-A:  20
----------
      95

Die Rundreise A → B → C → D → A ist also 95 km lang. Kurz schreibt man: 10+35+30+20=9510 + 35 + 30 + 20 = 95. Im Graphen sind die vier benutzten Kanten rot eingezeichnet:

Die Rundreise A \to B \to C \to D \to A (rot) ist 10 + 35 + 30 + 20 = 95 km lang
Tipp

Schreibe bei jeder Teilstrecke die beiden Orte dazu, wie oben (A-B, B-C, …). So siehst du sofort, ob eine Strecke fehlt. Eine Rundreise durch nn Orte hat immer genau nn Teilstrecken.

Arbeitsauftrag 14: Rundreisen vergleichen
  1. Berechne die Längen der Rundreisen A → B → D → C → A und A → C → B → D → A. Schreibe die Rechnung mit auf.
  2. Vergleiche mit der Rundreise A → B → C → D → A (95 km). Welche der drei Rundreisen ist am kürzesten?
  3. Zeichne die kürzeste der drei Rundreisen in den Graphen ein.
Vorlage: Zeichne die kürzeste Rundreise ein

Deine Rechnungen und dein Vergleich:

Lösung vergleichen
  1. A → B → D → C → A: 10+25+30+15=8010 + 25 + 30 + 15 = 80 km. A → C → B → D → A: 15+35+25+20=9515 + 35 + 25 + 20 = 95 km.
  2. A → B → D → C → A ist mit 80 km am kürzesten. Die beiden anderen sind je 95 km lang.
  3. Im Graphen werden die Kanten A–B, B–D, D–C und C–A markiert. Das ist genau der äußere Rand des Vierecks (siehe die Abbildung im Abschnitt über den Brute-Force-Ansatz).

Du hast damit schon die drei verschiedenen Rundreisen untersucht. Wegen der Symmetrie sind die übrigen drei Rundreisen nur die rückwärts gefahrenen Varianten und genauso lang.

3.2.3Der Brute-Force-Ansatz

Stell dir ein Fahrradschloss mit drei Zahlenrädern vor. Du hast die Zahl vergessen. Was tun? Du kannst einfach alle Zahlen von 000 bis 999 durchprobieren. Das ist mühsam, aber du findest die richtige Zahl garantiert – spätestens nach 1000 Versuchen.

Diese Methode heißt Brute-Force (englisch, gesprochen „brut fors“, wörtlich „rohe Gewalt“). Gemeint ist: Man denkt nicht lange nach, sondern probiert stur alles aus.

Definition: Brute-Force-Ansatz

Beim Brute-Force-Ansatz werden alle zulässigen Lösungen systematisch erzeugt und bewertet. Die beste davon ist die optimale Lösung.

Für das Problem des Handlungsreisenden besteht der Brute-Force-Ansatz aus drei Schritten:

  1. Erzeugen: Liste alle Rundreisen systematisch auf, zum Beispiel mit dem Baum aus dem letzten Abschnitt.
  2. Bewerten: Berechne für jede Rundreise die Gesamtlänge.
  3. Auswählen: Wähle die Rundreise mit der kleinsten Gesamtlänge.
Beispiel: Brute-Force für die vier Orte A, B, C, D
Rundreise Rechnung Länge (km)
A → B → C → D → A 10+35+30+2010 + 35 + 30 + 20 95
A → B → D → C → A 10+25+30+1510 + 25 + 30 + 15 80
A → C → B → D → A 15+35+25+2015 + 35 + 25 + 20 95
A → C → D → B → A 15+30+25+1015 + 30 + 25 + 10 80
A → D → B → C → A 20+25+35+1520 + 25 + 35 + 15 95
A → D → C → B → A 20+30+35+1020 + 30 + 35 + 10 95

Die kleinste Länge ist 80 km. Die optimale Rundreise ist A → B → D → C → A. Ihre Rückwärts-Variante A → C → D → B → A ist ebenfalls optimal.

Die optimale Rundreise A \to B \to D \to C \to A (rot) ist 10 + 25 + 30 + 15 = 80 km lang

Warum kann man sicher sein, dass es keine kürzere Rundreise gibt? Weil jede Rundreise in der Tabelle steht. Eine bessere kann es also nicht geben. Das ist die große Stärke von Brute-Force.

Merke

Was „faktoriell“ bedeutet, erfährst du gleich im Abschnitt über die Anzahl der Rundreisen.

So kannst du es sagen

So beschreibst du das Vorgehen in Fachsprache:

3.2.4Brute-Force mit fünf Orten

Mit vier Orten war Brute-Force schnell erledigt. Was passiert mit einem Ort mehr? Das probierst du jetzt selbst aus.

Wie viele Rundreisen gibt es bei fünf Orten mit Start in A? Für den zweiten Ort gibt es 4 Möglichkeiten, dann 3, dann 2, dann 1. Das sind 4⋅3⋅2⋅1=244 \cdot 3 \cdot 2 \cdot 1 = 24 Rundreisen. Wegen der Symmetrie musst du aber nur die Hälfte berechnen, also 12.

Tipp

So findest du die 12 verschiedenen Rundreisen, ohne eine doppelt zu zählen: Gehe vor wie im Baum (zweiter Ort B, C, D, E der Reihe nach) und schreibe nur die Rundreisen auf, bei denen der zweite Ort im Alphabet vor dem Ort steht, der direkt vor der Rückkehr nach A besucht wird. A → B → C → D → E → A schreibst du auf (B vor E), A → E → D → C → B → A nicht (E nach B) – sie ist ja dieselbe Reise rückwärts.

Arbeitsauftrag 15: Neue Probleminstanz mit fünf Orten
  1. Stelle eine eigene Entfernungstabelle für fünf Orte A bis E auf. Die Werte darfst du frei erfinden, sie sollten aber plausibel sein. Wenn du keine eigenen Werte erfinden möchtest, nimm die Tabelle und den Graphen unten: Die Orte A bis D sind die bekannten, Ort E ist neu dazugekommen.
  2. Bestimme mit dem Brute-Force-Ansatz die optimale Rundreise: Liste die 12 verschiedenen Rundreisen auf, berechne ihre Längen und wähle die kürzeste.
A B C D E
A – 10 15 20 28
B 10 – 35 25 32
C 15 35 – 30 18
D 20 25 30 – 32
E 28 32 18 32 –
Vorschlag für eine Probleminstanz mit fünf Orten (Entfernungen in km)

Trage deine Rundreisen hier ein:

Nr. Rundreise Rechnung Länge
1
2
3
4
5
6
7
8
9
10
11
12

Optimale Rundreise und ihre Länge:

Lösung vergleichen

Lösung für die vorgeschlagene Tabelle:

Nr. Rundreise Rechnung Länge
1 A → B → C → D → E → A 10+35+30+32+2810 + 35 + 30 + 32 + 28 135
2 A → B → C → E → D → A 10+35+18+32+2010 + 35 + 18 + 32 + 20 115
3 A → B → D → C → E → A 10+25+30+18+2810 + 25 + 30 + 18 + 28 111
4 A → B → D → E → C → A 10+25+32+18+1510 + 25 + 32 + 18 + 15 100
5 A → B → E → C → D → A 10+32+18+30+2010 + 32 + 18 + 30 + 20 110
6 A → B → E → D → C → A 10+32+32+30+1510 + 32 + 32 + 30 + 15 119
7 A → C → B → D → E → A 15+35+25+32+2815 + 35 + 25 + 32 + 28 135
8 A → C → B → E → D → A 15+35+32+32+2015 + 35 + 32 + 32 + 20 134
9 A → C → D → B → E → A 15+30+25+32+2815 + 30 + 25 + 32 + 28 130
10 A → C → E → B → D → A 15+18+32+25+2015 + 18 + 32 + 25 + 20 110
11 A → D → B → C → E → A 20+25+35+18+2820 + 25 + 35 + 18 + 28 126
12 A → D → C → B → E → A 20+30+35+32+2820 + 30 + 35 + 32 + 28 145

Die optimale Rundreise ist A → B → D → E → C → A mit 100 km (und rückwärts A → C → E → D → B → A). Die längste Rundreise (Nr. 12) ist mit 145 km fast um die Hälfte länger.

Wenn du eigene Werte benutzt hast, kannst du deine Rechnung nicht mit dieser Tabelle vergleichen. Prüfe dann: Hast du 12 verschiedene Rundreisen, und hat jede genau 5 Teilstrecken? Diese Probleminstanz brauchst du im nächsten Abschnitt noch einmal.

Du hast es sicher gemerkt: Mit fünf Orten ist Brute-Force schon richtig Arbeit. Statt 3 Rundreisen waren es 12. Und das bei nur einem Ort mehr!

3.2.5Wie viele Rundreisen gibt es?

Die Anzahl der Rundreisen kannst du ausrechnen, ohne sie aufzuschreiben. Bei nn Orten legst du den Startort fest. Dann gibt es

Insgesamt sind es (n−1)⋅(n−2)⋅…⋅2⋅1(n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 Rundreisen. Für so ein Produkt gibt es in der Mathematik eine Abkürzung, die Fakultät: Man schreibt die Zahl mit einem Ausrufezeichen dahinter.

Definition: Fakultät

Die Fakultät einer natürlichen Zahl kk ist das Produkt aller natürlichen Zahlen von 1 bis kk. Man schreibt k!k! (gelesen: „kk Fakultät“). Beispiele: 3!=3⋅2⋅1=63! = 3 \cdot 2 \cdot 1 = 6 und 5!=5⋅4⋅3⋅2⋅1=1205! = 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120. Für k=1k = 1 ist 1!=11! = 1. Außerdem legt man fest: 0!=10! = 1.

Bei nn Orten gibt es mit festem Startort also (n−1)!(n-1)! Rundreisen. Ist die Entfernungstabelle symmetrisch, sind davon nur (n−1)!:2(n-1)! : 2 verschieden (ab drei Orten).

Stolperstein

Die Klammer in (n−1)!(n-1)! ist wichtig. Bei n=5n = 5 Orten ist (5−1)!=4!=24(5-1)! = 4! = 24. Ohne Klammer stünde n−1!=5−1=4n - 1! = 5 - 1 = 4 da – das ist etwas ganz anderes. Rechne immer zuerst die Klammer aus und dann die Fakultät.

Arbeitsauftrag 16: Wachstum beobachten
  1. Berechne die Anzahl der Rundreisen bei 4, 5 und 6 Orten (Startort fest) und trage sie in die Tabelle ein. Ergänze auch die Anzahl der verschiedenen Rundreisen, wenn man die Symmetrie berücksichtigt.
  2. Was fällt dir am Wachstum auf? Um welchen Faktor wächst die Anzahl, wenn ein Ort dazukommt?
Orte nn Rechnung Rundreisen (n−1)!(n-1)! verschieden (mit Symmetrie)
4
5
6

Deine Beobachtung:

Lösung vergleichen
Orte nn Rechnung Rundreisen (n−1)!(n-1)! verschieden (mit Symmetrie)
4 3⋅2⋅13 \cdot 2 \cdot 1 6 3
5 4⋅3⋅2⋅14 \cdot 3 \cdot 2 \cdot 1 24 12
6 5⋅4⋅3⋅2⋅15 \cdot 4 \cdot 3 \cdot 2 \cdot 1 120 60

Die Anzahl wächst sehr schnell. Von 4 auf 5 Orte vervierfacht sie sich (6⋅4=246 \cdot 4 = 24), von 5 auf 6 Orte verfünffacht sie sich (24⋅5=12024 \cdot 5 = 120). Der Faktor wird mit jedem neuen Ort größer: Beim nächsten Ort kommt der Faktor 6 dazu, dann 7 und so weiter. Für 6 Orte müsstest du von Hand schon 60 Rundreisen berechnen.

Ein solches Wachstum heißt faktorielles Wachstum. Schon bei 10 Orten gibt es 9!=3628809! = 362\,880 Rundreisen. Wie lange selbst ein Computer dafür braucht, untersuchst du im Abschnitt über den Aufwand.

3.2.6Für Interessierte: Brute-Force mit Python

Dieser Unterabschnitt ist freiwillig. Mit einem kleinen Programm kannst du deine Handrechnung kontrollieren.

Zuerst muss die Entfernungstabelle ins Programm. Dafür benutzen wir eine Liste, deren Einträge selbst wieder Listen sind – für jede Zeile der Tabelle eine.

Werkzeug

Eine Tabelle als Liste von Listen: In entfernung = [[0, 10], [10, 0]] ist entfernung[0] die erste Zeile, also die Liste [0, 10]. Mit einem zweiten Index wählst du darin die Spalte: entfernung[0][1] ist 10. Die Orte bekommen Nummern: A ist 0, B ist 1, C ist 2, D ist 3. Die Entfernung von B nach C steht dann in entfernung[1][2]. Auf der Diagonale steht 0 statt eines Strichs.

namen = ["A", "B", "C", "D"]
entfernung = [[0, 10, 15, 20],
              [10, 0, 35, 25],
              [15, 35, 0, 30],
              [20, 25, 30, 0]]

def laenge(reise):
    summe = 0
    for i in range(len(reise) - 1):
        summe += entfernung[reise[i]][reise[i + 1]]
    return summe

def als_text(reise):
    text = namen[reise[0]]
    for i in range(1, len(reise)):
        text = text + " -> " + namen[reise[i]]
    return text

kuerzeste = 1000000
beste_reise = []
for ort2 in [1, 2, 3]:
    for ort3 in [1, 2, 3]:
        for ort4 in [1, 2, 3]:
            if ort2 != ort3 and ort2 != ort4 and ort3 != ort4:
                reise = [0, ort2, ort3, ort4, 0]
                strecke = laenge(reise)
                print(als_text(reise), "Länge:", strecke)
                if strecke < kuerzeste:
                    kuerzeste = strecke
                    beste_reise = reise

print("Optimal:", als_text(beste_reise), "mit Länge", kuerzeste)
A -> B -> C -> D -> A Länge: 95
A -> B -> D -> C -> A Länge: 80
A -> C -> B -> D -> A Länge: 95
A -> C -> D -> B -> A Länge: 80
A -> D -> B -> C -> A Länge: 95
A -> D -> C -> B -> A Länge: 95
Optimal: A -> B -> D -> C -> A mit Länge 80

Die Rückwärts-Variante A → C → D → B → A ist ebenfalls 80 km lang. Sie wird nicht übernommen, weil 80 < 80 falsch ist. Das Programm merkt sich also die erste optimale Rundreise, die es findet.

Arbeitsauftrag 17 (Zusatz): Programm für fünf Orte

Passe das Programm für deine Probleminstanz mit fünf Orten an (oder für die vorgeschlagene Tabelle). Das Programm soll nur die optimale Rundreise und die Anzahl der geprüften Rundreisen ausgeben. Tipp: Statt der langen Bedingung kannst du eine Funktion ist_rundreise(reise) schreiben, die prüft, ob jeder Ort 1 bis 4 in der Liste vorkommt (mit in).

Lösung vergleichen
namen = ["A", "B", "C", "D", "E"]
entfernung = [[0, 10, 15, 20, 28],
              [10, 0, 35, 25, 32],
              [15, 35, 0, 30, 18],
              [20, 25, 30, 0, 32],
              [28, 32, 18, 32, 0]]

def laenge(reise):
    summe = 0
    for i in range(len(reise) - 1):
        summe += entfernung[reise[i]][reise[i + 1]]
    return summe

def als_text(reise):
    text = namen[reise[0]]
    for i in range(1, len(reise)):
        text = text + " -> " + namen[reise[i]]
    return text

def ist_rundreise(reise):
    for ort in range(1, len(namen)):
        if ort not in reise:
            return False
    return True

orte = [1, 2, 3, 4]
kuerzeste = 1000000
beste_reise = []
anzahl = 0
for ort2 in orte:
    for ort3 in orte:
        for ort4 in orte:
            for ort5 in orte:
                reise = [0, ort2, ort3, ort4, ort5, 0]
                if ist_rundreise(reise):
                    anzahl += 1
                    strecke = laenge(reise)
                    if strecke < kuerzeste:
                        kuerzeste = strecke
                        beste_reise = reise

print("Geprüfte Rundreisen:", anzahl)
print("Optimal:", als_text(beste_reise), "mit Länge", kuerzeste)
Geprüfte Rundreisen: 24
Optimal: A -> B -> D -> E -> C -> A mit Länge 100

Neu sind die fünfte Zeile und Spalte der Tabelle, der Name "E" und eine vierte Schleife. Die Funktion ist_rundreise ersetzt die lange Bedingung: Kommen alle vier Orte 1 bis 4 in der Reise vor, ist keiner doppelt. Das Wort in funktioniert bei Listen genauso wie bei Zeichenketten: ort not in reise ist wahr, wenn ort nicht in der Liste reise vorkommt. Dann ist die Reise keine Rundreise, und die Funktion gibt sofort False zurück. Das Programm prüft alle 24 Rundreisen, auch die rückwärts gefahrenen. Das Ergebnis stimmt mit der Handrechnung überein.

3.2.7Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

In mehreren Aufträgen geht es um Mias Partyeinkauf. Sie startet und endet zu Hause (Z) und fährt zur Bäckerei (B), zum Getränkemarkt (G) und zum Supermarkt (S). Die Entfernungen in km:

Z B G S
Z – 3 7 6
B 3 – 9 5
G 7 9 – 4
S 6 5 4 –
Arbeitsauftrag 18: Länge einer Rundreise ●○○

Berechne die Länge der beiden Rundreisen. Schreibe zu jeder Teilstrecke die beiden Orte dazu.

  1. Z → G → S → B → Z
  2. Z → S → B → G → Z

Deine Rechnungen:

Lösung vergleichen
  1. Z-G 7, G-S 4, S-B 5, B-Z 3: 7+4+5+3=197 + 4 + 5 + 3 = 19 km.
  2. Z-S 6, S-B 5, B-G 9, G-Z 7: 6+5+9+7=276 + 5 + 9 + 7 = 27 km.

Häufigster Fehler: Die Rückfahrt zum Start (B-Z bzw. G-Z) wird vergessen. Eine Rundreise durch 4 Orte hat immer 4 Teilstrecken.

Arbeitsauftrag 19: Zulässige Lösung beim Partyeinkauf? ●○○

Mia muss zu Hause starten, jedes Geschäft genau einmal besuchen und wieder nach Hause fahren. Entscheide bei jedem Vorschlag, ob er eine zulässige Lösung ist. Begründe, wenn er es nicht ist.

Vorschlag zulässig? Begründung
Z → B → G → S → Z
Z → B → S → Z
Z → G → S → G → B → Z
Z → S → G → B
Z → S → B → G → Z
Lösung vergleichen
Vorschlag zulässig? Begründung
Z → B → G → S → Z ✓ jedes Geschäft genau einmal, zurück nach Hause
Z → B → S → Z ✗ der Getränkemarkt G fehlt
Z → G → S → G → B → Z ✗ G wird zweimal besucht
Z → S → G → B ✗ Mia fährt am Ende nicht nach Hause
Z → S → B → G → Z ✓ jedes Geschäft genau einmal, zurück nach Hause

Die letzte Rundreise ist mit 27 km zwar lang, aber trotzdem zulässig. Ob eine Lösung zulässig ist, hat mit ihrer Länge nichts zu tun.

Arbeitsauftrag 20: Fakultäten berechnen ●○○
  1. Berechne die Anzahl der Rundreisen (Startort fest) für 3, 7 und 8 Orte. Ergänze auch die Anzahl der verschiedenen Rundreisen bei einer symmetrischen Tabelle.
  2. Bei wie vielen Orten gibt es genau 720 Rundreisen?
  3. Bei wie vielen Orten gibt es mit Symmetrie genau 60 verschiedene Rundreisen?
Orte nn Rechnung Rundreisen (n−1)!(n-1)! verschieden (mit Symmetrie)
3
7
8

Deine Antworten zu 2 und 3:

Lösung vergleichen
Orte nn Rechnung Rundreisen (n−1)!(n-1)! verschieden (mit Symmetrie)
3 2!=2⋅12! = 2 \cdot 1 2 1
7 6!=6⋅5⋅4⋅3⋅2⋅16! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 720 360
8 7!=7⋅6⋅5⋅4⋅3⋅2⋅17! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 5 040 2 520
  1. 720=6!720 = 6!, also gilt n−1=6n - 1 = 6. Bei 7 Orten gibt es 720 Rundreisen.
  2. 60 verschiedene Rundreisen bedeuten 2⋅60=120=5!2 \cdot 60 = 120 = 5! Rundreisen. Also ist n−1=5n - 1 = 5, und es sind 6 Orte.

Bei 3 Orten gibt es nur eine verschiedene Rundreise: A → B → C → A und A → C → B → A sind dieselbe, nur rückwärts.

Arbeitsauftrag 21: Die Fachbegriffe ●○○

Ergänze die Sätze mit den passenden Fachbegriffen.

Satzanfang Ergänzung
Eine Lösung, die alle Bedingungen des Problems erfüllt, heißt …
Die beste zulässige Lösung bezüglich eines Kriteriums heißt …
Ein Ansatz, der alle zulässigen Lösungen erzeugt, bewertet und die beste auswählt, heißt …
Beim Problem des Handlungsreisenden ist das Kriterium meistens …
Der große Vorteil von Brute-Force ist, dass …
Der große Nachteil von Brute-Force ist, dass …
Lösung vergleichen
Satzanfang Ergänzung
Eine Lösung, die alle Bedingungen des Problems erfüllt, heißt … zulässige Lösung.
Die beste zulässige Lösung bezüglich eines Kriteriums heißt … optimale Lösung.
Ein Ansatz, der alle zulässigen Lösungen erzeugt, bewertet und die beste auswählt, heißt … Brute-Force-Ansatz.
Beim Problem des Handlungsreisenden ist das Kriterium meistens … die Gesamtlänge der Rundreise.
Der große Vorteil von Brute-Force ist, dass … er garantiert die optimale Lösung findet.
Der große Nachteil von Brute-Force ist, dass … die Anzahl der zu prüfenden Lösungen sehr schnell wächst.
Arbeitsauftrag 22: Welche Verbindung ist optimal? ●●○

Lara will mit der Bahn zum Freizeitpark. Die App zeigt drei Verbindungen. Lara hat höchstens 20 € für die Fahrt.

Verbindung Fahrzeit Umstiege Preis
V1 1 h 40 min 2 18 €
V2 2 h 10 min 0 12 €
V3 1 h 25 min 3 22 €
  1. Welche Verbindungen sind zulässige Lösungen? Begründe.
  2. Bestimme die optimale Verbindung, wenn das Kriterium (a) die Fahrzeit, (b) die Anzahl der Umstiege, (c) der Preis ist.
  3. Erkläre an diesem Beispiel, warum man bei „optimal“ immer das Kriterium angeben muss.

Deine Antworten:

Lösung vergleichen
  1. V1 und V2 sind zulässig. V3 kostet 22 € und verletzt damit die Bedingung „höchstens 20 €“.
    1. Fahrzeit: V1 (1 h 40 min). V3 wäre zwar schneller, ist aber nicht zulässig. (b) Umstiege: V2 (kein Umstieg). (c) Preis: V2 (12 €).
  2. Je nach Kriterium ist eine andere Verbindung die beste. Ohne Kriterium kann man gar nicht sagen, welche Verbindung optimal ist.

Typischer Fehler: V3 als schnellste Verbindung wählen. Die optimale Lösung wird aber nur unter den zulässigen Lösungen gesucht.

Arbeitsauftrag 23: Brute-Force beim Partyeinkauf ●●○

Bestimme mit dem Brute-Force-Ansatz die optimale Rundreise für Mias Partyeinkauf.

  1. Schreibe alle 6 Rundreisen mit Start in Z auf (oder nimm deine Liste aus dem Auftrag Rundreisen beim Partyeinkauf).
  2. Berechne ihre Längen. Zwei kennst du schon aus dem Auftrag Länge einer Rundreise.
  3. Wähle die kürzeste Rundreise aus. Ist sie die einzige optimale Lösung?
Rundreise Rechnung Länge (km)

Optimale Rundreise:

Lösung vergleichen
Rundreise Rechnung Länge (km)
Z → B → G → S → Z 3+9+4+63 + 9 + 4 + 6 22
Z → B → S → G → Z 3+5+4+73 + 5 + 4 + 7 19
Z → G → B → S → Z 7+9+5+67 + 9 + 5 + 6 27
Z → G → S → B → Z 7+4+5+37 + 4 + 5 + 3 19
Z → S → B → G → Z 6+5+9+76 + 5 + 9 + 7 27
Z → S → G → B → Z 6+4+9+36 + 4 + 9 + 3 22

Optimal ist Z → B → S → G → Z mit 19 km. Die Rundreise Z → G → S → B → Z ist ebenfalls 19 km lang. Sie ist aber dieselbe Rundreise, nur rückwärts gefahren. Es gibt also eine optimale Rundreise, die man in zwei Richtungen fahren kann. Die Längen kommen paarweise vor (22, 19, 27), genau wie es die Symmetrie vorhersagt.

Arbeitsauftrag 24: Fehler in der Brute-Force-Tabelle ●●○

Tom hat Brute-Force für Mias Partyeinkauf so aufgeschrieben:

Rundreise Toms Rechnung Toms Länge
Z → B → G → S → Z 3+9+4+63 + 9 + 4 + 6 22
Z → B → S → G → Z 3+5+43 + 5 + 4 12
Z → G → B → S → Z 7+9+5+67 + 9 + 5 + 6 27
Z → G → S → B → Z 7+4+5+37 + 4 + 5 + 3 18
Z → B → G → S → Z 3+9+4+63 + 9 + 4 + 6 22
Z → S → G → B → Z 6+4+9+36 + 4 + 9 + 3 22

Toms Ergebnis: „Optimal ist Z → B → S → G → Z mit 12 km.“

Finde drei Fehler in Toms Tabelle. Erkläre jeweils, was falsch ist, und gib das richtige Ergebnis an.

Toms Fehler:

Lösung vergleichen
  1. Zeile 2: Die Rückfahrt G-Z (7 km) fehlt. Richtig: 3+5+4+7=193 + 5 + 4 + 7 = 19 km.
  2. Zeile 4: Rechenfehler. 7+4+5+3=197 + 4 + 5 + 3 = 19, nicht 18.
  3. Zeile 5: Diese Rundreise steht schon in Zeile 1. Dafür fehlt Z → S → B → G → Z (6+5+9+7=276 + 5 + 9 + 7 = 27 km).

Richtiges Ergebnis: Optimal ist Z → B → S → G → Z mit 19 km (und rückwärts Z → G → S → B → Z).

Ein guter Test für deine eigenen Tabellen: Jede Rechnung hat so viele Summanden, wie es Orte gibt, und bei symmetrischer Tabelle kommt jede Länge genau zweimal vor.

Arbeitsauftrag 25: Radtour mit fünf Zielen ●●●

Eine Klasse übernachtet in einer Jugendherberge (J). Mit dem Fahrrad will sie die Burg (B), den See (S), den Turm (T) und den Wasserfall (W) besuchen und dann zurückfahren. Die Entfernungen in km:

J B S T W
J – 9 11 10 13
B 9 – 6 14 4
S 11 6 – 15 9
T 10 14 15 – 12
W 13 4 9 12 –
  1. Wie viele Rundreisen mit Start in J gibt es? Wie viele davon sind verschieden?
  2. Die Tabelle unten enthält die 12 verschiedenen Rundreisen. Sechs Längen sind schon berechnet. Berechne die übrigen sechs.
  3. Bestimme die optimale Rundreise. Wie viel länger ist die längste Rundreise?
Nr. Rundreise Rechnung Länge (km)
1 J → B → S → T → W → J 9+6+15+12+139 + 6 + 15 + 12 + 13 55
2 J → B → S → W → T → J 9+6+9+12+109 + 6 + 9 + 12 + 10 46
3 J → B → T → S → W → J 9+14+15+9+139 + 14 + 15 + 9 + 13 60
4 J → B → T → W → S → J 9+14+12+9+119 + 14 + 12 + 9 + 11 55
5 J → B → W → S → T → J 9+4+9+15+109 + 4 + 9 + 15 + 10 47
6 J → B → W → T → S → J 9+4+12+15+119 + 4 + 12 + 15 + 11 51
7 J → S → B → T → W → J
8 J → S → B → W → T → J
9 J → S → T → B → W → J
10 J → S → W → B → T → J
11 J → T → B → S → W → J
12 J → T → S → B → W → J

Deine Antworten zu 1 und 3:

Lösung vergleichen
  1. Es gibt (5−1)!=4!=24(5-1)! = 4! = 24 Rundreisen. Weil die Tabelle symmetrisch ist, sind 24:2=1224 : 2 = 12 davon verschieden.
  2. Die fehlenden Längen:
Nr. Rundreise Rechnung Länge (km)
7 J → S → B → T → W → J 11+6+14+12+1311 + 6 + 14 + 12 + 13 56
8 J → S → B → W → T → J 11+6+4+12+1011 + 6 + 4 + 12 + 10 43
9 J → S → T → B → W → J 11+15+14+4+1311 + 15 + 14 + 4 + 13 57
10 J → S → W → B → T → J 11+9+4+14+1011 + 9 + 4 + 14 + 10 48
11 J → T → B → S → W → J 10+14+6+9+1310 + 14 + 6 + 9 + 13 52
12 J → T → S → B → W → J 10+15+6+4+1310 + 15 + 6 + 4 + 13 48
  1. Optimal ist J → S → B → W → T → J mit 43 km (Nr. 8). Die längste Rundreise ist Nr. 3 mit 60 km, also 60−43=1760 - 43 = 17 km länger.

Beachte: Die optimale Rundreise steht erst in der zweiten Hälfte der Tabelle. Hättest du nach den ersten sechs Rundreisen aufgehört, hättest du nur Nr. 2 mit 46 km gefunden. Brute-Force ist nur dann sicher, wenn wirklich alle Rundreisen geprüft werden.

3.2.8Das Wichtigste in Kürze

Selbstcheck

3.3Heuristiken: schnell eine gute Lösung finden DS25

Diesen Abschnitt als PDF (S. 38–55)

Das Jupyter-Notebook aus dem Unterricht: DS25_Heuristik_Greedy.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Brute-Force findet immer die beste Rundreise – aber schon bei wenigen Orten wird das Ausprobieren sehr mühsam. Eine Paketbotin mit 100 Adressen kann unmöglich alle Reihenfolgen durchrechnen. Was macht sie stattdessen? Vermutlich etwas ganz Naheliegendes: Sie fährt immer zur nächstgelegenen Adresse, die sie noch nicht beliefert hat. So eine Faustregel heißt in der Informatik Heuristik. In diesem Abschnitt lernst du, wie solche Faustregeln funktionieren, wendest eine davon von Hand an und prüfst, wie gut ihr Ergebnis ist.

Lernziele

Nach diesem Abschnitt kannst du

3.3.1Faustregeln statt Ausprobieren

Im Alltag benutzt du ständig Faustregeln. An der Supermarktkasse stellst du dich an die kürzeste Schlange. Das geht schnell und klappt meistens gut. Eine Garantie gibt es aber nicht: Vielleicht hat die Person vor dir einen riesigen Einkauf, und an der Nachbarkasse wärst du schneller gewesen. Um sicherzugehen, müsstest du alle Einkaufswagen genau ansehen – das dauert länger als das Warten selbst.

Genau solche Faustregeln nennt man in der Informatik Heuristiken. Das Wort kommt vom griechischen heuriskein, „finden“. Eine Heuristik verzichtet darauf, alle Möglichkeiten zu prüfen. Dafür ist sie schnell.

Definition: Heuristik

Eine Heuristik ist eine Lösungsstrategie, die schnell eine zulässige Lösung liefert, ohne alle Möglichkeiten zu prüfen. Die Lösung ist meist gut, aber nicht garantiert optimal.

Merke

Eine Heuristik ist eine Lösungsstrategie, die schnell eine (meist gute, aber nicht garantiert optimale) Lösung liefert, ohne alle Möglichkeiten zu prüfen.

3.3.2Greedy: immer das, was gerade am besten aussieht

Eine besonders einfache Art von Heuristik geht so vor: Sie baut die Lösung Schritt für Schritt auf. In jedem Schritt nimmt sie das, was im Moment am besten aussieht. Was später passiert, bedenkt sie nicht. Eine einmal getroffene Entscheidung wird nie mehr geändert.

Solche Heuristiken heißen Greedy-Heuristiken (englisch greedy, gesprochen „griedi“, heißt „gierig“). Denk an ein Kind am Buffet, das sich zuerst das größte Stück Kuchen nimmt – ohne zu überlegen, ob danach noch Platz für den Nachtisch bleibt.

Definition: Greedy-Heuristik

Eine Greedy-Heuristik baut eine Lösung schrittweise auf. In jedem Schritt trifft sie die Entscheidung, die im Moment am besten erscheint, ohne die Auswirkungen auf spätere Schritte zu berücksichtigen.

Eine Greedy-Strategie hast du übrigens schon in Klasse 9 kennengelernt: Beim Lernen eines Entscheidungsbaums wählt man in jedem Schritt das Merkmal, das die Daten im Moment am besten aufteilt. Ob eine andere Wahl später zu einem besseren Baum geführt hätte, prüft man nicht.

Merke

Eine Greedy-Heuristik („gierig“) trifft in jedem Schritt die Entscheidung, die im Moment am besten erscheint, ohne spätere Auswirkungen zu berücksichtigen.

3.3.3Die Nearest-Neighbor-Heuristik

Für das Problem des Handlungsreisenden gibt es eine naheliegende Greedy-Heuristik. Sie heißt Nearest Neighbor (englisch für „nächster Nachbar“, gesprochen „nierest neiber“). Ihre Regel lautet: Fahre immer zum nächstgelegenen Ort, an dem du noch nicht warst.

So gehst du Schritt für Schritt vor:

  1. Beginne im Startort. Er ist der aktuelle Ort.
  2. Suche unter allen noch nicht besuchten Orten den, der vom aktuellen Ort am wenigsten weit entfernt ist. Sind zwei Orte gleich weit entfernt, nimm den, der im Alphabet zuerst kommt.
  3. Fahre dorthin. Dieser Ort ist jetzt der aktuelle Ort und gilt als besucht.
  4. Wiederhole die Schritte 2 und 3, bis alle Orte besucht sind.
  5. Fahre zurück zum Startort.
Merke

Beim Problem des Handlungsreisenden wählt die Greedy-Heuristik Nearest Neighbor von der aktuellen Stadt aus immer die nächstgelegene, noch nicht besuchte Stadt.

Beispiel: Nearest Neighbor von Hand, Start in A

Wir benutzen wieder die Entfernungstabelle der vier Orte:

A B C D
A – 10 15 20
B 10 – 35 25
C 15 35 – 30
D 20 25 30 –
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 A B 10, C 15, D 20 B (10 km)
2 B C 35, D 25 D (25 km)
3 D C 30 C (30 km)
4 C alle besucht zurück nach A (15 km)

Rundreise: A → B → D → C → A. Länge: 10+25+30+15=8010 + 25 + 30 + 15 = 80 km.

Lies die Tabelle Zeile für Zeile:

Vergleiche mit dem Ergebnis von Brute-Force aus dem letzten Abschnitt: Die optimale Rundreise ist A → B → D → C → A mit 80 km. Die Heuristik hat hier also mit nur vier kurzen Blicken in die Tabelle die optimale Lösung gefunden. Ist das immer so? Das untersuchst du jetzt.

Stolperstein

Die drei häufigsten Fehler bei Nearest Neighbor:

Arbeitsauftrag 26: Anderer Startpunkt

Wende die Nearest-Neighbor-Heuristik von Hand an, aber starte diesmal in Ort C. Lege dazu eine Tabelle an wie im Beispiel. Vergleiche Rundreise und Länge mit dem Ergebnis für den Start in A. Was fällt dir auf?

Deine Tabelle und dein Vergleich:

Lösung vergleichen
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 C A 15, B 35, D 30 A (15 km)
2 A B 10, D 20 B (10 km)
3 B D 25 D (25 km)
4 D alle besucht zurück nach C (30 km)

Rundreise: C → A → B → D → C. Länge: 15+10+25+30=8015 + 10 + 25 + 30 = 80 km.

Die Länge ist dieselbe wie beim Start in A. Das ist kein Zufall: C → A → B → D → C ist dieselbe Rundreise wie A → B → D → C → A. Sie benutzt dieselben Kanten (A–B, B–D, D–C, C–A) und beginnt nur an einer anderen Stelle. Auch vom Start C aus findet die Heuristik also die optimale Rundreise.

Arbeitsauftrag 27: Start in D

Wende die Nearest-Neighbor-Heuristik noch einmal an, jetzt mit Start in D. Ist das Ergebnis optimal? Erkläre, an welcher Stelle die Heuristik „in eine Falle läuft“.

Deine Tabelle und deine Erklärung:

Lösung vergleichen
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 D A 20, B 25, C 30 A (20 km)
2 A B 10, C 15 B (10 km)
3 B C 35 C (35 km)
4 C alle besucht zurück nach D (30 km)

Rundreise: D → A → B → C → D. Länge: 20+10+35+30=9520 + 10 + 35 + 30 = 95 km. Das ist nicht optimal, denn die optimale Rundreise ist 80 km lang.

Die Falle: Die ersten beiden Schritte sind kurz (20 km und 10 km). Danach ist aber nur noch C übrig, und von B nach C muss die Heuristik die längste Strecke der ganzen Tabelle (35 km) nehmen. Weil sie nicht vorausschaut, merkt sie das zu spät. Was im Moment am besten aussah, führt später zu einer teuren Strecke.

Die Heuristik liefert also je nach Startort unterschiedlich gute Ergebnisse. Bei Start in A, B oder C kommt sie auf 80 km, bei Start in D auf 95 km. Im Graphen siehst du, woran es liegt: Die Rundreise vom Start D aus benutzt die teure Kante B–C.

Nearest Neighbor mit Start in D liefert D \to A \to B \to C \to D (rot) mit 20 + 10 + 35 + 30 = 95 km. Optimal wären 80 km
Merke

Heuristiken sind schneller als Brute-Force, liefern aber nicht immer die optimale Lösung – manchmal führt eine „im Moment beste“ Entscheidung in eine Sackgasse.

3.3.4Wie gut ist die Heuristik? Die Abweichung in Prozent

„95 km statt 80 km“ – ist das viel oder wenig? Um das zu beurteilen, rechnet man aus, um wie viel Prozent die Lösung der Heuristik schlechter ist als die optimale Lösung. Das kennst du aus Mathe als prozentuale Änderung:

Abweichung=Länge der Heuristik−optimale Längeoptimale Länge⋅100%\text{Abweichung} = \frac{\text{Länge der Heuristik} - \text{optimale Länge}}{\text{optimale Länge}} \cdot 100\,\%

Für den Start in D:

Abweichung=95−8080⋅100%=1580⋅100%=18,75%≈18,8%\text{Abweichung} = \frac{95 - 80}{80} \cdot 100\,\% = \frac{15}{80} \cdot 100\,\% = 18{,}75\,\% \approx 18{,}8\,\%

Die Rundreise der Heuristik ist also knapp 19 % länger als nötig. Bei einer Abweichung von 0 % hat die Heuristik die optimale Lösung getroffen.

Stolperstein

Teile immer durch die optimale Länge, nicht durch die Länge der Heuristik. 1595≈15,8%\frac{15}{95} \approx 15{,}8\,\% wäre falsch. Die Frage lautet ja: Um wie viel ist die Heuristik schlechter als das Optimum?

Arbeitsauftrag 28: Heuristik und Optimum

Nimm deine eigene Probleminstanz mit fünf Orten aus dem Auftrag Neue Probleminstanz mit fünf Orten (oder die dort vorgeschlagene Tabelle).

  1. Wende die Nearest-Neighbor-Heuristik mit Start in A an. Gib die Rundreise und ihre Länge an.
  2. Vergleiche mit der optimalen Rundreise, die du mit Brute-Force gefunden hast. Berechne die prozentuale Abweichung.

Deine Tabelle und deine Rechnung:

Lösung vergleichen

Lösung für die vorgeschlagene Tabelle (A bis D wie bisher, dazu E mit A–E 28, B–E 32, C–E 18, D–E 32):

Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 A B 10, C 15, D 20, E 28 B (10 km)
2 B C 35, D 25, E 32 D (25 km)
3 D C 30, E 32 C (30 km)
4 C E 18 E (18 km)
5 E alle besucht zurück nach A (28 km)

Rundreise: A → B → D → C → E → A. Länge: 10+25+30+18+28=11110 + 25 + 30 + 18 + 28 = 111 km.

Die optimale Rundreise ist A → B → D → E → C → A mit 100 km.

Abweichung=111−100100⋅100%=11%\text{Abweichung} = \frac{111 - 100}{100} \cdot 100\,\% = 11\,\%

Die Heuristik ist hier also 11 % schlechter als das Optimum. Sie hätte in D besser zuerst nach E (32 km) fahren sollen statt nach C (30 km): Dann wäre die teure Rückfahrt E–A (28 km) durch die kurze Rückfahrt C–A (15 km) ersetzt worden. Diese 2 km Umweg im Moment hätten am Ende 11 km gespart – aber so weit schaut Nearest Neighbor nicht voraus.

3.3.5Heuristik oder Brute-Force?

Warum benutzt man überhaupt Heuristiken, wenn sie nicht immer optimal sind? Weil sie viel weniger Arbeit machen. Zähle einmal, wie oft man bei Nearest Neighbor eine Entfernung ansehen muss: Bei vier Orten sind es im ersten Schritt 3 Entfernungen, im zweiten 2 und im dritten 1, zusammen also 6. Bei 10 Orten sind es 9+8+7+…+1=459 + 8 + 7 + \ldots + 1 = 45. Brute-Force müsste bei 10 Orten dagegen 9!=3628809! = 362\,880 Rundreisen durchrechnen.

Brute-Force Nearest Neighbor
Ergebnis garantiert optimal zulässig, meist gut, nicht immer optimal
Arbeit bei 4 Orten 6 Rundreisen berechnen 6 Entfernungen ansehen
Arbeit bei 10 Orten 362 880 Rundreisen berechnen 45 Entfernungen ansehen
geeignet für kleine Probleminstanzen auch große Probleminstanzen
So kannst du es sagen

So vergleichst du die beiden Ansätze in Fachsprache:

3.3.6Für Interessierte: Nearest Neighbor mit Python

Dieser Unterabschnitt ist freiwillig. Die Entfernungstabelle und die Funktionen laenge und als_text kennst du aus dem Abschnitt über Brute-Force. Neu ist die Funktion nearest_neighbor.

namen = ["A", "B", "C", "D"]
entfernung = [[0, 10, 15, 20],
              [10, 0, 35, 25],
              [15, 35, 0, 30],
              [20, 25, 30, 0]]

def laenge(reise):
    summe = 0
    for i in range(len(reise) - 1):
        summe += entfernung[reise[i]][reise[i + 1]]
    return summe

def als_text(reise):
    text = namen[reise[0]]
    for i in range(1, len(reise)):
        text = text + " -> " + namen[reise[i]]
    return text

def nearest_neighbor(start):
    reise = [start]
    aktuell = start
    while len(reise) < len(namen):
        naechster = -1
        kleinste = 1000000
        for ort in range(len(namen)):
            if ort not in reise:
                if entfernung[aktuell][ort] < kleinste:
                    kleinste = entfernung[aktuell][ort]
                    naechster = ort
        reise.append(naechster)
        aktuell = naechster
    reise.append(start)
    return reise

for start in range(len(namen)):
    reise = nearest_neighbor(start)
    print(als_text(reise), "Länge:", laenge(reise))
A -> B -> D -> C -> A Länge: 80
B -> A -> C -> D -> B Länge: 80
C -> A -> B -> D -> C Länge: 80
D -> A -> B -> C -> D Länge: 95

Beachte: in funktioniert bei Listen genauso wie bei Zeichenketten. 3 in [0, 1, 3] ist True.

Versuch: Ändere die Tabelle

Trage im Programm die Tabelle mit fünf Orten ein (eine fünfte Zeile, in jeder Zeile eine fünfte Zahl, und "E" in namen). Die Funktion nearest_neighbor musst du nicht ändern. Vergleiche die Ausgabe mit deiner Lösung zum Auftrag Heuristik und Optimum.

3.3.7Übungen

Arbeitsauftrag 29: Nearest Neighbor von allen Startorten

Wende die Nearest-Neighbor-Heuristik auf die vier Orte A, B, C und D mit Start in B an. Fasse danach die Ergebnisse für alle vier Startorte in einer Tabelle zusammen (Startort, Rundreise, Länge, Abweichung vom Optimum 80 km).

Deine Rechnung und deine Tabelle:

Lösung vergleichen

Start in B: Von B aus ist A am nächsten (10 km). Von A aus: C 15 km, D 20 km, also C. Von C aus bleibt D (30 km). Zurück nach B: 25 km. Länge: 10+15+30+25=8010 + 15 + 30 + 25 = 80 km.

Startort Rundreise Länge Abweichung
A A → B → D → C → A 80 km 0 %
B B → A → C → D → B 80 km 0 %
C C → A → B → D → C 80 km 0 %
D D → A → B → C → D 95 km 18,75 %

In drei von vier Fällen findet die Heuristik die optimale Rundreise. Ein einfacher Trick verbessert die Heuristik deshalb: Man führt sie von jedem Startort aus durch und nimmt die kürzeste Rundreise. Das ist immer noch viel weniger Arbeit als Brute-Force bei vielen Orten.

Arbeitsauftrag 30 (Zusatz): Was würdest du empfehlen?

Ein Lieferdienst muss jeden Tag 40 Kundinnen und Kunden beliefern. Die Disponentin überlegt, ob sie mit einem Computer die optimale Route per Brute-Force berechnen lassen soll oder ob die Nearest-Neighbor-Heuristik reicht. Beurteile die beiden Möglichkeiten und gib eine begründete Empfehlung.

Deine Beurteilung:

Lösung vergleichen

Mit dem Depot sind es 41 Orte. Brute-Force müsste 40!40! Rundreisen prüfen. Das ist eine Zahl mit 48 Stellen – selbst der schnellste Computer würde dafür viel länger brauchen, als das Universum alt ist. Brute-Force ist also gar keine echte Möglichkeit, obwohl es garantiert die beste Route liefern würde.

Die Nearest-Neighbor-Heuristik liefert dagegen in Sekundenbruchteilen eine zulässige Route. Sie ist vermutlich etwas länger als die optimale, aber sie steht rechtzeitig vor der Abfahrt fest. Empfehlung: die Heuristik verwenden – am besten von mehreren Startpunkten aus oder mit einem besseren Verfahren kombiniert.

Worauf es ankommt: Du wägst Qualität der Lösung (optimal oder nur gut) gegen den Aufwand (Rechenzeit) ab und begründest mit der Anzahl der Möglichkeiten.

3.3.8Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 31: Ausprobieren oder Faustregel? ●○○

Entscheide bei jeder Vorgehensweise, ob es sich um einen Brute-Force-Ansatz oder um eine Heuristik handelt. Gib bei den Heuristiken an, ob sie greedy sind, also in jedem Schritt das nehmen, was im Moment am besten aussieht.

Vorgehensweise Brute-Force oder Heuristik? greedy?
Ben hat die Zahl seines Zahlenschlosses vergessen und probiert alle Zahlen von 000 bis 999 der Reihe nach aus.
Beim Kartenspiel spielt Ida in jeder Runde ihre höchste Karte.
Elif schreibt alle Reihenfolgen auf, in denen sie ihre vier Hausaufgaben machen kann, und wählt die, die am wenigsten Zeit kostet.
Beim Wandern nimmt Paul an jeder Kreuzung den Weg, der am steilsten bergauf führt, um möglichst schnell zum Gipfel zu kommen.
Eine Kassiererin gibt Wechselgeld, indem sie immer die größte Münze nimmt, die noch passt.
Lösung vergleichen
Vorgehensweise Brute-Force oder Heuristik? greedy?
Zahlenschloss: alle Zahlen ausprobieren Brute-Force –
Kartenspiel: immer die höchste Karte Heuristik ja
Hausaufgaben: alle Reihenfolgen vergleichen Brute-Force –
Wandern: immer der steilste Weg Heuristik ja
Wechselgeld: immer die größte passende Münze Heuristik ja

Brute-Force erkennst du an „alle … ausprobieren“ oder „alle … vergleichen“. Die drei Heuristiken entscheiden Schritt für Schritt nach dem, was gerade am besten aussieht. Ob das am Ende wirklich die beste Lösung ist, prüfen sie nicht. Der steilste Weg kann zum Beispiel an einer Felswand enden.

Arbeitsauftrag 32: Nearest Neighbor beim Partyeinkauf ●○○

Mia startet zu Hause (Z) und fährt zur Bäckerei (B), zum Getränkemarkt (G) und zum Supermarkt (S). Die Entfernungen in km:

Z B G S
Z – 3 7 6
B 3 – 9 5
G 7 9 – 4
S 6 5 4 –

Wende die Nearest-Neighbor-Heuristik mit Start in Z an. Fülle die Tabelle aus und gib die Rundreise und ihre Länge an.

Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 Z
2
3
4 alle besucht

Rundreise und Länge:

Lösung vergleichen
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 Z B 3, G 7, S 6 B (3 km)
2 B G 9, S 5 S (5 km)
3 S G 4 G (4 km)
4 G alle besucht zurück nach Z (7 km)

Rundreise: Z → B → S → G → Z. Länge: 3+5+4+7=193 + 5 + 4 + 7 = 19 km. Das ist genau die optimale Rundreise, die du mit Brute-Force gefunden hast (Auftrag Brute-Force beim Partyeinkauf).

Arbeitsauftrag 33: Start in der Bäckerei ●○○

Mias Freundin Ela wohnt direkt neben der Bäckerei. Sie startet deshalb in B und fährt am Ende wieder nach B zurück. Wende die Nearest-Neighbor-Heuristik mit Start in B an (Tabelle aus dem Auftrag Nearest Neighbor beim Partyeinkauf). Vergleiche die Länge mit der optimalen Rundreise (19 km). Um wie viele km ist Elas Rundreise länger?

Deine Tabelle und dein Vergleich:

Lösung vergleichen
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 B Z 3, G 9, S 5 Z (3 km)
2 Z G 7, S 6 S (6 km)
3 S G 4 G (4 km)
4 G alle besucht zurück nach B (9 km)

Rundreise: B → Z → S → G → B. Länge: 3+6+4+9=223 + 6 + 4 + 9 = 22 km. Das sind 3 km mehr als die optimale Rundreise (19 km). Die optimale Rundreise Z → B → S → G → Z kann Ela auch in B beginnen: B → S → G → Z → B, ebenfalls 19 km. Die Heuristik findet sie aber nicht, weil sie am Ende die lange Strecke G–B (9 km) nehmen muss.

Arbeitsauftrag 34: Stimmt das? ●○○

Entscheide, ob die Aussage richtig oder falsch ist. Begründe kurz.

Aussage richtig oder falsch? Begründung
Eine Heuristik prüft alle Möglichkeiten.
Nearest Neighbor kann die optimale Rundreise finden.
Nearest Neighbor liefert immer eine zulässige Rundreise.
Eine Greedy-Heuristik ändert eine Entscheidung später noch, wenn sie sich als schlecht herausstellt.
Heuristiken sind meistens schneller als Brute-Force.
Lösung vergleichen
Aussage richtig oder falsch? Begründung
Eine Heuristik prüft alle Möglichkeiten. falsch Das macht Brute-Force. Eine Heuristik spart sich genau das.
Nearest Neighbor kann die optimale Rundreise finden. richtig Beim Partyeinkauf mit Start in Z findet sie die optimale Rundreise.
Nearest Neighbor liefert immer eine zulässige Rundreise. richtig Sie besucht jeden Ort genau einmal und fährt zum Start zurück.
Eine Greedy-Heuristik ändert eine Entscheidung später noch … falsch Eine Greedy-Entscheidung wird nie zurückgenommen.
Heuristiken sind meistens schneller als Brute-Force. richtig Sie prüfen viel weniger Möglichkeiten.
Arbeitsauftrag 35: Abweichung in Prozent ●●○
  1. Berechne für jede Zeile die prozentuale Abweichung der Heuristik vom Optimum. Runde auf eine Stelle nach dem Komma.
  2. Paul hat für die erste Zeile 22−1922⋅100%≈13,6%\frac{22 - 19}{22} \cdot 100\,\% \approx 13{,}6\,\% gerechnet. Erkläre seinen Fehler.
Länge der Heuristik optimale Länge Rechnung Abweichung
22 km 19 km
60 km 50 km
47 km 43 km
30 km 30 km

Pauls Fehler:

Lösung vergleichen
Länge der Heuristik optimale Länge Rechnung Abweichung
22 km 19 km 22−1919⋅100%\frac{22 - 19}{19} \cdot 100\,\% 15,8 %
60 km 50 km 60−5050⋅100%\frac{60 - 50}{50} \cdot 100\,\% 20,0 %
47 km 43 km 47−4343⋅100%\frac{47 - 43}{43} \cdot 100\,\% 9,3 %
30 km 30 km 30−3030⋅100%\frac{30 - 30}{30} \cdot 100\,\% 0,0 %

Paul hat durch die Länge der Heuristik (22) geteilt. Man muss aber durch die optimale Länge (19) teilen, denn die Frage lautet: Um wie viel Prozent ist die Heuristik schlechter als das Optimum? Bei 0 % hat die Heuristik die optimale Lösung getroffen.

Arbeitsauftrag 36: Fehler im Protokoll ●●○

Lina hat Nearest Neighbor für die Radtour mit fünf Zielen (Auftrag Radtour mit fünf Zielen im Abschnitt über Brute-Force) mit Start in J angewendet. Hier ist die Tabelle noch einmal:

J B S T W
J – 9 11 10 13
B 9 – 6 14 4
S 11 6 – 15 9
T 10 14 15 – 12
W 13 4 9 12 –

Linas Protokoll:

Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 J B 9, S 11, T 10, W 13 B (9 km)
2 B J 9, S 6, T 14, W 4 W (4 km)
3 W S 9, T 12 T (12 km), weil es danach zum See geht
4 T S 15 S (15 km)

Linas Ergebnis: J → B → W → T → S, Länge 9+4+12+15=409 + 4 + 12 + 15 = 40 km.

  1. Finde drei Fehler in Linas Protokoll und erkläre sie.
  2. Führe die Heuristik richtig durch. Vergleiche mit der optimalen Rundreise (43 km) und berechne die Abweichung.

Linas Fehler und deine richtige Lösung:

Lösung vergleichen
  1. Linas Fehler:
    • Schritt 2: J steht in der Liste der noch nicht besuchten Orte, obwohl J der Startort ist und schon besucht wurde. (Ihre Wahl W ist trotzdem richtig.)
    • Schritt 3: Von W aus ist S mit 9 km näher als T mit 12 km. Lina schaut voraus („danach …“). Das macht Nearest Neighbor nicht. Die Heuristik wählt immer den nächsten Ort.
    • Ende: Die Rückfahrt zur Jugendherberge fehlt.
  2. Richtig:
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 J B 9, S 11, T 10, W 13 B (9 km)
2 B S 6, T 14, W 4 W (4 km)
3 W S 9, T 12 S (9 km)
4 S T 15 T (15 km)
5 T alle besucht zurück nach J (10 km)

Rundreise: J → B → W → S → T → J. Länge: 9+4+9+15+10=479 + 4 + 9 + 15 + 10 = 47 km.

Abweichung: 47−4343⋅100%≈9,3%\frac{47 - 43}{43} \cdot 100\,\% \approx 9{,}3\,\%. Die Heuristik ist hier also etwa 9 % schlechter als das Optimum.

Arbeitsauftrag 37: Die Falle selbst bauen ●●●

In dieser Entfernungstabelle fehlt eine Zahl: Die Entfernung zwischen R und S heißt xx.

P Q R S
P – 4 6 8
Q 4 – 7 5
R 6 7 – xx
S 8 5 xx –
  1. Setze x=5x = 5 ein. Wende Nearest Neighbor mit Start in P an. Bestimme mit Brute-Force die optimale Rundreise (3 verschiedene Rundreisen genügen). Ist die Heuristik optimal?
  2. Setze x=20x = 20 ein und wiederhole beides. Berechne die Abweichung.
  3. Untersuche allgemein: Welche Rundreise wählt Nearest Neighbor, egal wie groß xx ist? Ab welchem Wert von xx ist sie nicht mehr optimal? Begründe.

Deine Rechnungen und deine Begründung:

Lösung vergleichen
  1. x=5x = 5: Von P aus ist Q am nächsten (4). Von Q aus: R 7, S 5, also S. Von S aus bleibt R (x=5x = 5). Zurück nach P: 6. Rundreise P → Q → S → R → P mit 4+5+5+6=204 + 5 + 5 + 6 = 20. Brute-Force: P → Q → R → S → P: 4+7+5+8=244 + 7 + 5 + 8 = 24. P → Q → S → R → P: 4+5+5+6=204 + 5 + 5 + 6 = 20. P → R → Q → S → P: 6+7+5+8=266 + 7 + 5 + 8 = 26. Optimal sind 20. Die Heuristik ist optimal.
  2. x=20x = 20: Nearest Neighbor wählt dieselben Schritte wie vorher (die Entscheidungen hängen nicht von xx ab). P → Q → S → R → P mit 4+5+20+6=354 + 5 + 20 + 6 = 35. Brute-Force: P → Q → R → S → P: 4+7+20+8=394 + 7 + 20 + 8 = 39. P → Q → S → R → P: 35. P → R → Q → S → P: 6+7+5+8=266 + 7 + 5 + 8 = 26. Optimal sind 26. Abweichung: 35−2626⋅100%≈34,6%\frac{35 - 26}{26} \cdot 100\,\% \approx 34{,}6\,\%.
  3. Nearest Neighbor wählt immer P → Q → S → R → P. Bei P ist Q am nächsten, bei Q ist S näher als R, danach bleibt nur R. Die Länge ist 4+5+x+6=15+x4 + 5 + x + 6 = 15 + x. Die Rundreise P → R → Q → S → P benutzt die Strecke R–S nicht und ist immer 26 lang. Die Heuristik ist also nicht mehr optimal, wenn 15+x>2615 + x > 26 ist, also ab x=12x = 12 (bei ganzen Zahlen). Bei x=11x = 11 sind beide gleich lang (26), dann ist die Heuristik noch optimal.

Die Falle: Nearest Neighbor muss am Ende die Strecke R–S nehmen, egal wie lang sie ist. Die ersten Schritte sehen gut aus, aber die Heuristik schaut nicht voraus.

3.3.9Das Wichtigste in Kürze

Selbstcheck

3.4Das Rucksackproblem: Brute-Force und Greedy im Vergleich DS26/27

Diesen Abschnitt als PDF (S. 56–77)

Das Jupyter-Notebook aus dem Unterricht: DS26_27_Rucksackproblem.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Du planst eine Wanderung mit Übernachtung. Zelt, Schlafsack, Kocher, Proviant und Erste-Hilfe-Set liegen bereit – aber alles zusammen ist zu schwer. Dein Rucksack soll höchstens 10 kg wiegen. Was nimmst du mit, damit der Rucksack möglichst nützlich gefüllt ist? Diese Frage heißt Rucksackproblem. Es ist ganz anders aufgebaut als das Problem des Handlungsreisenden: Hier gibt es keine Orte und keine Reihenfolge, sondern nur die Frage „mitnehmen oder nicht?“. Trotzdem helfen dieselben Werkzeuge: Brute-Force findet garantiert die beste Auswahl, eine Greedy-Heuristik findet schnell eine gute. In diesem Abschnitt wendest du beide Ansätze an und vergleichst sie.

Lernziele

Nach diesem Abschnitt kannst du

3.4.1Das Problem: Was kommt in den Rucksack?

Beim Rucksackproblem hat jeder Gegenstand zwei Eigenschaften: ein Gewicht und einen Wert. Der Wert gibt an, wie nützlich oder kostbar der Gegenstand ist. Hier messen wir ihn in Euro. Der Rucksack hat eine Tragkraft, also ein Höchstgewicht. Gesucht ist eine Auswahl, die möglichst viel wert ist und trotzdem nicht zu schwer.

Auf Englisch heißt das Problem Knapsack Problem (gesprochen „näpsäck“, knapsack ist ein altes Wort für Rucksack). Es steckt in vielen Alltagsfragen: Welche Pakete lädt man in einen Lieferwagen? Welche Projekte finanziert eine Firma mit ihrem Budget? Welche Fotos passen noch auf die Speicherkarte?

Merke

Beim Rucksackproblem (Knapsack Problem) stehen mehrere Gegenstände mit jeweils einem Gewicht und einem Wert zur Verfügung. Gesucht ist die Auswahl von Gegenständen mit maximalem Gesamtwert, deren Gesamtgewicht eine vorgegebene Tragkraft nicht übersteigt.

Beispiel: Problem und Probleminstanz

Problem: Gegeben sind beliebige Gegenstände mit Gewicht und Wert und ein Rucksack mit einer Tragkraft. Finde eine Auswahl der Gegenstände mit möglichst großem Gesamtwert, deren Gesamtgewicht die Tragkraft nicht übersteigt.

Probleminstanz: Tragkraft 10 kg und diese fünf Gegenstände:

Gegenstand Gewicht (kg) Wert (€)
Zelt 5 60
Schlafsack 4 40
Kocher 2 30
Proviant 3 25
Erste-Hilfe-Set 1 20

Die Probleminstanz ist als Liste abstrahiert dargestellt: Farbe, Marke oder Größe der Gegenstände spielen keine Rolle. Die Begriffe aus den letzten Abschnitten passen auch hier:

Beachte den Unterschied zum Handlungsreisenden: Dort war die kleinste Länge am besten, hier ist der größte Wert am besten. Beides sind Optimierungsprobleme – einmal wird etwas möglichst klein gemacht, einmal möglichst groß.

Arbeitsauftrag 38: Erste Kombinationen

Finde durch Ausprobieren mindestens zwei zulässige Kombinationen (Gesamtgewicht höchstens 10 kg) für die Probleminstanz oben. Berechne jeweils Gesamtgewicht und Gesamtwert. Welche deiner Kombinationen ist die beste?

Kombination Gesamtgewicht (kg) Gesamtwert (€)

Meine beste Kombination:

Lösung vergleichen

Es gibt viele richtige Antworten. Einige Beispiele:

Kombination Gesamtgewicht (kg) Gesamtwert (€)
Zelt, Schlafsack 5+4=95 + 4 = 9 60+40=10060 + 40 = 100
Zelt, Kocher, Proviant 5+2+3=105 + 2 + 3 = 10 60+30+25=11560 + 30 + 25 = 115
Schlafsack, Kocher, Proviant, Erste-Hilfe-Set 4+2+3+1=104 + 2 + 3 + 1 = 10 40+30+25+20=11540 + 30 + 25 + 20 = 115
Zelt, Kocher, Erste-Hilfe-Set 5+2+1=85 + 2 + 1 = 8 60+30+20=11060 + 30 + 20 = 110

Nicht zulässig wäre zum Beispiel Zelt, Schlafsack und Kocher: 5+4+2=115 + 4 + 2 = 11 kg ist zu schwer. Ob deine beste Kombination auch die optimale ist, kannst du durch Ausprobieren allein nicht wissen. Dafür brauchst du den Brute-Force-Ansatz.

3.4.2Brute-Force: alle Auswahlen ausprobieren

Wie viele verschiedene Auswahlen gibt es überhaupt? Gehe die Gegenstände der Reihe nach durch. Bei jedem Gegenstand gibt es genau zwei Möglichkeiten: Er kommt mit, oder er bleibt da. Bei drei Gegenständen kannst du das als Baum zeichnen:

Bei drei Gegenständen (Z = Zelt, S = Schlafsack, K = Kocher) gibt es 2 \cdot 2 \cdot 2 = 8 Möglichkeiten. Jeder Weg von oben nach unten ist eine Auswahl

Mit jedem weiteren Gegenstand verdoppelt sich die Anzahl der Wege: Jeder bisherige Weg teilt sich in „mit“ und „ohne“. Bei vier Gegenständen sind es 2⋅2⋅2⋅2=24=162 \cdot 2 \cdot 2 \cdot 2 = 2^4 = 16, bei fünf Gegenständen 25=322^5 = 32 Auswahlen.

Eine Auswahl von Gegenständen nennt man in der Mathematik eine Teilmenge. Dazu zählen auch die leere Auswahl (nichts einpacken) und die volle Auswahl (alles einpacken).

Definition: Teilmenge

Eine Teilmenge einer Menge von Gegenständen ist eine beliebige Auswahl dieser Gegenstände. Auch die leere Auswahl und die Auswahl aller Gegenstände sind Teilmengen. Eine Menge mit nn Gegenständen hat 2n2^n Teilmengen.

Merke

Brute-Force-Ansatz beim Rucksackproblem: Alle möglichen Teilmengen der Gegenstände werden gebildet und bewertet – bei nn Gegenständen gibt es 2n2^n Teilmengen (exponentieller Aufwand).

Exponentiell heißt: Die Anzahl der Gegenstände steht im Exponenten. Jeder zusätzliche Gegenstand verdoppelt die Arbeit. Bei 10 Gegenständen sind es schon 210=10242^{10} = 1024 Teilmengen.

Teilmengen systematisch aufschreiben

Damit keine Teilmenge fehlt, schreibst du jede Auswahl als Folge von Nullen und Einsen. Die Stellen gehören der Reihe nach zu Zelt (Z), Schlafsack (S), Kocher (K), Proviant (P) und Erste-Hilfe-Set (E). Eine 1 bedeutet „kommt mit“, eine 0 bedeutet „bleibt da“.

Zum Beispiel bedeutet 1 1 0 0 1: Zelt, Schlafsack und Erste-Hilfe-Set kommen mit. Gewicht: 5+4+1=105 + 4 + 1 = 10 kg, Wert: 60+40+20=12060 + 40 + 20 = 120 €.

Vielleicht erkennst du das Muster wieder: Es sind genau die fünfstelligen Binärzahlen aus dem Kapitel über Schaltungen. Wenn du von 1 1 1 1 1 rückwärts bis 0 0 0 0 0 zählst, bekommst du jede Teilmenge genau einmal.

Tipp

Du sparst Arbeit, wenn du zuerst das Gewicht berechnest. Liegt es über 10 kg, ist die Auswahl nicht zulässig. Dann musst du den Wert nicht mehr ausrechnen – trage einfach ✗ ein.

Arbeitsauftrag 39: Brute-Force von Hand

Führe den Brute-Force-Ansatz für die Probleminstanz mit der Tragkraft 10 kg durch.

  1. Berechne für jede der 32 Teilmengen das Gesamtgewicht. Entscheide, ob sie zulässig ist (✓) oder nicht (✗).
  2. Berechne für die zulässigen Teilmengen den Gesamtwert.
  3. Markiere die optimale Lösung.

Teilmengen mit Zelt:

Nr. Z S K P E Gewicht (kg) Wert (€) zulässig?
1 1 1 1 1 1
2 1 1 1 1 0
3 1 1 1 0 1
4 1 1 1 0 0
5 1 1 0 1 1
6 1 1 0 1 0
7 1 1 0 0 1
8 1 1 0 0 0
9 1 0 1 1 1
10 1 0 1 1 0
11 1 0 1 0 1
12 1 0 1 0 0
13 1 0 0 1 1
14 1 0 0 1 0
15 1 0 0 0 1
16 1 0 0 0 0

Teilmengen ohne Zelt:

Nr. Z S K P E Gewicht (kg) Wert (€) zulässig?
17 0 1 1 1 1
18 0 1 1 1 0
19 0 1 1 0 1
20 0 1 1 0 0
21 0 1 0 1 1
22 0 1 0 1 0
23 0 1 0 0 1
24 0 1 0 0 0
25 0 0 1 1 1
26 0 0 1 1 0
27 0 0 1 0 1
28 0 0 1 0 0
29 0 0 0 1 1
30 0 0 0 1 0
31 0 0 0 0 1
32 0 0 0 0 0

Optimale Auswahl, Gesamtgewicht und Gesamtwert:

Lösung vergleichen
Nr. Z S K P E Gewicht (kg) Wert (€) zulässig?
1 1 1 1 1 1 15 175 ✗
2 1 1 1 1 0 14 155 ✗
3 1 1 1 0 1 12 150 ✗
4 1 1 1 0 0 11 130 ✗
5 1 1 0 1 1 13 145 ✗
6 1 1 0 1 0 12 125 ✗
7 1 1 0 0 1 10 120 ✓
8 1 1 0 0 0 9 100 ✓
9 1 0 1 1 1 11 135 ✗
10 1 0 1 1 0 10 115 ✓
11 1 0 1 0 1 8 110 ✓
12 1 0 1 0 0 7 90 ✓
13 1 0 0 1 1 9 105 ✓
14 1 0 0 1 0 8 85 ✓
15 1 0 0 0 1 6 80 ✓
16 1 0 0 0 0 5 60 ✓
Nr. Z S K P E Gewicht (kg) Wert (€) zulässig?
17 0 1 1 1 1 10 115 ✓
18 0 1 1 1 0 9 95 ✓
19 0 1 1 0 1 7 90 ✓
20 0 1 1 0 0 6 70 ✓
21 0 1 0 1 1 8 85 ✓
22 0 1 0 1 0 7 65 ✓
23 0 1 0 0 1 5 60 ✓
24 0 1 0 0 0 4 40 ✓
25 0 0 1 1 1 6 75 ✓
26 0 0 1 1 0 5 55 ✓
27 0 0 1 0 1 3 50 ✓
28 0 0 1 0 0 2 30 ✓
29 0 0 0 1 1 4 45 ✓
30 0 0 0 1 0 3 25 ✓
31 0 0 0 0 1 1 20 ✓
32 0 0 0 0 0 0 0 ✓

Die optimale Lösung ist Nr. 7: Zelt, Schlafsack und Erste-Hilfe-Set mit 10 kg und 120 €. Sie ist die einzige zulässige Teilmenge mit diesem Wert. Am nächsten kommen Nr. 10 und Nr. 17 mit je 115 €. Die Teilmengen 1 bis 6 und 9 sind zu schwer. Ihre Werte stehen nur zur Kontrolle in der Tabelle.

Arbeitsauftrag 40: Anzahl der Teilmengen
  1. Wie viele Teilmengen musstest du im Auftrag Brute-Force von Hand insgesamt prüfen? Berechne die Anzahl zuerst mit der Formel 2n2^n. Überprüfe sie dann durch Abzählen in deiner Tabelle.
  2. Wie viele davon waren zulässig?
  3. Wie viele Teilmengen müsstest du prüfen, wenn noch eine Trinkflasche als sechster Gegenstand dazukäme?

Deine Antworten:

Lösung vergleichen
  1. Bei n=5n = 5 Gegenständen gibt es 25=2⋅2⋅2⋅2⋅2=322^5 = 2 \cdot 2 \cdot 2 \cdot 2 \cdot 2 = 32 Teilmengen. Die Tabelle hat genau 32 Zeilen (16 mit Zelt, 16 ohne Zelt).
  2. 25 Teilmengen sind zulässig, 7 sind zu schwer (Nr. 1 bis 6 und Nr. 9).
  3. Mit sechs Gegenständen wären es 26=642^6 = 64 Teilmengen – doppelt so viele. Für jede der 32 bisherigen Teilmengen gibt es dann eine Variante mit und eine ohne Trinkflasche.

Brute-Force muss alle Teilmengen prüfen, auch die unzulässigen. Erst nach dem Prüfen weiß man ja, dass eine Teilmenge zu schwer ist.

Mit Brute-Force weißt du jetzt sicher: Die optimale Lösung ist Zelt, Schlafsack und Erste-Hilfe-Set mit 10 kg und 120 €. Keine andere zulässige Auswahl ist so viel wert.

Für Interessierte: Brute-Force mit Python

Dieser Unterabschnitt ist freiwillig. Die 32 Teilmengen erzeugst du im Programm genauso wie die Zeilen einer Wahrheitstabelle: mit fünf ineinander geschachtelten Schleifen über [0, 1].

namen = ["Zelt", "Schlafsack", "Kocher", "Proviant", "Erste-Hilfe-Set"]
gewichte = [5, 4, 2, 3, 1]
werte = [60, 40, 30, 25, 20]
tragkraft = 10

def gesamt(auswahl, zahlen):
    summe = 0
    for i in range(len(auswahl)):
        if auswahl[i] == 1:
            summe += zahlen[i]
    return summe

anzahl = 0
bester_wert = 0
beste_auswahl = []
for z in [0, 1]:
    for s in [0, 1]:
        for k in [0, 1]:
            for p in [0, 1]:
                for e in [0, 1]:
                    auswahl = [z, s, k, p, e]
                    anzahl += 1
                    gewicht = gesamt(auswahl, gewichte)
                    wert = gesamt(auswahl, werte)
                    if gewicht <= tragkraft and wert > bester_wert:
                        bester_wert = wert
                        beste_auswahl = auswahl

print("Geprüfte Teilmengen:", anzahl)
print("Bester Wert:", bester_wert, "Euro")
print("Gewicht:", gesamt(beste_auswahl, gewichte), "kg")
for i in range(len(namen)):
    if beste_auswahl[i] == 1:
        print("-", namen[i])
Geprüfte Teilmengen: 32
Bester Wert: 120 Euro
Gewicht: 10 kg
- Zelt
- Schlafsack
- Erste-Hilfe-Set

3.4.3Greedy: Was ist pro Kilogramm am meisten wert?

Brute-Force ist bei fünf Gegenständen noch machbar. Bei 30 Gegenständen wären es aber 2302^{30}, also über eine Milliarde Teilmengen. Gibt es eine schnelle Faustregel?

Eine naheliegende Idee: Pack zuerst den wertvollsten Gegenstand ein. Das ist aber nicht schlau, wenn er sehr schwer ist. Besser ist die Frage: Wie viel Wert bekomme ich pro Kilogramm? Das kennst du vom Einkaufen. Auf jedem Preisschild im Supermarkt steht neben dem Preis auch der Grundpreis, zum Beispiel „1 kg = 4,20 €“. Damit kann man Packungen verschiedener Größe vergleichen.

Definition: Wert-Gewicht-Verhältnis

Das Wert-Gewicht-Verhältnis eines Gegenstands ist sein Wert geteilt durch sein Gewicht. Es gibt an, wie viel Wert ein Kilogramm dieses Gegenstands bringt.

Für das Zelt ist es zum Beispiel 60:5=1260 : 5 = 12, also 12 € pro kg. Je größer das Verhältnis, desto „lohnender“ ist der Gegenstand pro Kilogramm.

Die Greedy-Heuristik für das Rucksackproblem geht so vor:

  1. Berechne für jeden Gegenstand das Wert-Gewicht-Verhältnis.
  2. Sortiere die Gegenstände nach diesem Verhältnis, den größten Wert zuerst. Haben zwei Gegenstände dasselbe Verhältnis, kommt der zuerst, der in der Liste weiter oben steht.
  3. Gehe die sortierte Liste von oben nach unten durch. Passt der Gegenstand noch in den Rucksack, pack ihn ein. Passt er nicht mehr, lass ihn weg und mach mit dem nächsten weiter.

Das ist eine Greedy-Heuristik: Sie nimmt in jedem Schritt den Gegenstand, der im Moment am lohnendsten aussieht. Eine Entscheidung wird nie zurückgenommen.

Merke

Greedy-Heuristik beim Rucksackproblem: Die Gegenstände werden nach ihrem Wert-Gewicht-Verhältnis (Wert : Gewicht) sortiert und der Reihe nach eingepackt, solange sie noch hineinpassen – bis kein weiterer Gegenstand mehr hineinpasst.

Beispiel: Greedy beim Tagesausflug

Für einen Tagesausflug darf die Tasche höchstens 4 kg wiegen. Zur Auswahl stehen:

Gegenstand Gewicht (kg) Wert (€) Verhältnis (€ pro kg)
Fernglas 2 30 30:2=1530 : 2 = 15
Kamera 3 36 36:3=1236 : 3 = 12
Trinkflasche 1 10 10:1=1010 : 1 = 10
Regenjacke 1 8 8:1=88 : 1 = 8

Die Liste ist schon nach dem Verhältnis sortiert. Jetzt wird gepackt:

Gegenstand bisheriges Gewicht passt? Gewicht danach Wert danach
Fernglas 0 kg ja: 0+2=2≤40 + 2 = 2 \le 4 2 kg 30 €
Kamera 2 kg nein: 2+3=5>42 + 3 = 5 > 4 2 kg 30 €
Trinkflasche 2 kg ja: 2+1=3≤42 + 1 = 3 \le 4 3 kg 40 €
Regenjacke 3 kg ja: 3+1=4≤43 + 1 = 4 \le 4 4 kg 48 €

Ergebnis: Fernglas, Trinkflasche und Regenjacke, 4 kg, 48 €.

Ein Vergleich mit Brute-Force (bei vier Gegenständen gibt es nur 24=162^4 = 16 Teilmengen) zeigt: 48 € ist hier tatsächlich der größte mögliche Wert. Die Heuristik hat also die optimale Lösung gefunden.

Stolperstein

Hör nicht beim ersten Gegenstand auf, der nicht mehr passt! Im Beispiel passt die Kamera nicht, aber die leichteren Gegenstände danach schon. Wer bei der Kamera aufhört, hat nur 30 € statt 48 € im Rucksack. Gehe die Liste immer bis zum Ende durch.

Arbeitsauftrag 41: Greedy-Heuristik von Hand

Wende die Greedy-Heuristik auf die Probleminstanz mit Zelt, Schlafsack, Kocher, Proviant und Erste-Hilfe-Set (Tragkraft 10 kg) an.

  1. Berechne für jeden Gegenstand das Wert-Gewicht-Verhältnis und sortiere die Gegenstände absteigend danach.
  2. Packe nach der Greedy-Regel ein. Lege dazu eine Tabelle an wie im Beispiel Greedy beim Tagesausflug.
  3. Vergleiche das Ergebnis mit der optimalen Lösung aus dem Brute-Force-Ansatz.
Gegenstand Gewicht (kg) Wert (€) Verhältnis (€ pro kg)
Zelt 5 60
Schlafsack 4 40
Kocher 2 30
Proviant 3 25
Erste-Hilfe-Set 1 20

Sortierte Liste, Packtabelle und Vergleich:

Lösung vergleichen
Gegenstand Gewicht (kg) Wert (€) Verhältnis (€ pro kg)
Zelt 5 60 12
Schlafsack 4 40 10
Kocher 2 30 15
Proviant 3 25 25:3≈8,3325 : 3 \approx 8{,}33
Erste-Hilfe-Set 1 20 20

Sortiert: Erste-Hilfe-Set (20), Kocher (15), Zelt (12), Schlafsack (10), Proviant (8,33).

Gegenstand bisheriges Gewicht passt? Gewicht danach Wert danach
Erste-Hilfe-Set 0 kg ja: 0+1=10 + 1 = 1 1 kg 20 €
Kocher 1 kg ja: 1+2=31 + 2 = 3 3 kg 50 €
Zelt 3 kg ja: 3+5=83 + 5 = 8 8 kg 110 €
Schlafsack 8 kg nein: 8+4=12>108 + 4 = 12 > 10 8 kg 110 €
Proviant 8 kg nein: 8+3=11>108 + 3 = 11 > 10 8 kg 110 €

Greedy-Ergebnis: Erste-Hilfe-Set, Kocher und Zelt mit 8 kg und 110 €.

Die optimale Lösung (Brute-Force) ist Zelt, Schlafsack und Erste-Hilfe-Set mit 120 €. Die Greedy-Heuristik findet hier also nicht die optimale Lösung. Sie liegt 10 € darunter.

Warum findet Greedy hier nicht das Optimum?

Schau dir die beiden Ergebnisse genau an:

Greedy-Heuristik optimale Lösung
Auswahl Erste-Hilfe-Set, Kocher, Zelt Zelt, Schlafsack, Erste-Hilfe-Set
Gesamtgewicht 8 kg 10 kg
Gesamtwert 110 € 120 €

Die Greedy-Heuristik nimmt den Kocher, weil er pro Kilogramm sehr lohnend ist. Danach bleiben aber nur noch 2 kg frei, und dafür gibt es keinen passenden Gegenstand mehr. 2 kg Tragkraft bleiben ungenutzt. Die optimale Lösung lässt den Kocher weg und nutzt die 10 kg mit dem Schlafsack vollständig aus. Die Heuristik betrachtet jeden Gegenstand einzeln. Wie gut die Gegenstände zusammen den Rucksack füllen, sieht sie nicht.

Wie groß ist die Abweichung? Beim Rucksack ist ein größerer Wert besser. Deshalb rechnet man hier „optimaler Wert minus Wert der Heuristik“:

Abweichung=optimaler Wert−Wert der Heuristikoptimaler Wert⋅100%=120−110120⋅100%≈8,3%\text{Abweichung} = \frac{\text{optimaler Wert} - \text{Wert der Heuristik}}{\text{optimaler Wert}} \cdot 100\,\% = \frac{120 - 110}{120} \cdot 100\,\% \approx 8{,}3\,\%

Die Greedy-Lösung ist also etwa 8,3 % weniger wert als die optimale. Dafür musste die Heuristik nur fünf Verhältnisse berechnen, sie sortieren und fünfmal prüfen, ob etwas passt – statt 32 Teilmengen durchzurechnen.

So kannst du es sagen

So beschreibst du das Ergebnis in Fachsprache:

3.4.4Grenzen der Heuristik

Im Beispiel mit dem Tagesausflug war die Greedy-Lösung optimal, bei der Wanderung nicht. Um zu zeigen, dass eine Heuristik nicht immer die optimale Lösung findet, genügt ein einziges Beispiel, bei dem sie danebenliegt. So ein Beispiel heißt Gegenbeispiel.

Merke

Um zu zeigen, dass eine Heuristik nicht immer optimal ist, genügt ein Gegenbeispiel: eine Probleminstanz, bei der die Heuristik eine schlechtere als die optimale Lösung liefert.

Arbeitsauftrag 42: Ein Gegenbeispiel konstruieren

Denke dir eine eigene Probleminstanz mit drei Gegenständen aus, bei der die Greedy-Heuristik nicht die optimale Lösung findet. Teste deine Instanz mit beiden Ansätzen: Wende die Greedy-Heuristik an, und bestimme die optimale Lösung mit Brute-Force (bei drei Gegenständen gibt es 23=82^3 = 8 Teilmengen).

Tipp: Sorge dafür, dass der Gegenstand mit dem besten Verhältnis so schwer ist, dass danach nichts anderes mehr passt.

Deine Probleminstanz und deine Tests:

Lösung vergleichen

Ein mögliches Gegenbeispiel: Tragkraft 6 kg.

Gegenstand Gewicht (kg) Wert (€) Verhältnis
G1 4 24 6
G2 3 15 5
G3 3 15 5

Greedy: G1 hat das beste Verhältnis und wird eingepackt (4 kg). G2 passt nicht mehr (4+3=7>64 + 3 = 7 > 6), G3 auch nicht. Ergebnis: 24 €.

Brute-Force:

Auswahl Gewicht Wert zulässig?
keine 0 0 ✓
G1 4 24 ✓
G2 3 15 ✓
G3 3 15 ✓
G1, G2 7 39 ✗
G1, G3 7 39 ✗
G2, G3 6 30 ✓
G1, G2, G3 10 54 ✗

Optimal sind G2 und G3 mit 30 €. Die Greedy-Lösung ist um 30−2430⋅100%=20%\frac{30 - 24}{30} \cdot 100\,\% = 20\,\% schlechter.

Noch extremer: Tragkraft 10 kg, Gegenstand X mit 1 kg und 3 € (Verhältnis 3), Gegenstand Y mit 10 kg und 20 € (Verhältnis 2). Greedy nimmt X, danach passt Y nicht mehr: 3 €. Optimal ist Y allein mit 20 €.

Worauf es ankommt: Deine Instanz ist ein Gegenbeispiel, wenn der Wert der Greedy-Lösung kleiner ist als der Wert der optimalen Lösung.

Arbeitsauftrag 43: Brute-Force oder Greedy?

Vergleiche den Brute-Force-Ansatz und die Greedy-Heuristik für das Rucksackproblem. Ergänze die Tabelle und beurteile anschließend: Wann würdest du welchen Ansatz verwenden?

Brute-Force Greedy-Heuristik
Ist das Ergebnis immer optimal?
Was muss man rechnen?
Anzahl Prüfungen bei 5 Gegenständen
Anzahl Prüfungen bei 30 Gegenständen

Deine Beurteilung:

Lösung vergleichen
Brute-Force Greedy-Heuristik
Ist das Ergebnis immer optimal? ja nein (z. B. 110 € statt 120 €)
Was muss man rechnen? für jede Teilmenge Gewicht und Wert für jeden Gegenstand das Verhältnis; sortieren; einmal die Liste durchgehen
Anzahl Prüfungen bei 5 Gegenständen 25=322^5 = 32 Teilmengen 5 Gegenstände prüfen (plus Sortieren)
Anzahl Prüfungen bei 30 Gegenständen 230=10737418242^{30} = 1\,073\,741\,824 Teilmengen 30 Gegenstände prüfen (plus Sortieren)

Beurteilung: Bei wenigen Gegenständen lohnt sich Brute-Force, weil man dann sicher die optimale Lösung bekommt und der Aufwand noch klein ist. Bei vielen Gegenständen ist Brute-Force viel zu aufwendig. Dann ist die Greedy-Heuristik besser: Sie ist schnell und liefert meist eine gute, wenn auch nicht immer optimale Lösung. Wenn es auf jeden Euro ankommt und die Instanz klein ist, nimmt man Brute-Force. Wenn eine schnelle, gute Lösung genügt, nimmt man die Heuristik.

3.4.5Für Interessierte: die Greedy-Heuristik mit Python

Dieser Unterabschnitt ist freiwillig. Statt die Liste zu sortieren, sucht das Programm in jeder Runde den Gegenstand mit dem besten Verhältnis, der noch nicht geprüft wurde. Das ergibt dieselbe Reihenfolge wie das Sortieren.

namen = ["Zelt", "Schlafsack", "Kocher", "Proviant", "Erste-Hilfe-Set"]
gewichte = [5, 4, 2, 3, 1]
werte = [60, 40, 30, 25, 20]
tragkraft = 10

def verhaeltnis(i):
    return werte[i] / gewichte[i]

geprueft = []
gewicht = 0
wert = 0
for runde in range(len(namen)):
    bester = -1
    for i in range(len(namen)):
        if i not in geprueft:
            if bester == -1 or verhaeltnis(i) > verhaeltnis(bester):
                bester = i
    geprueft.append(bester)
    if gewicht + gewichte[bester] <= tragkraft:
        gewicht += gewichte[bester]
        wert += werte[bester]
        print("eingepackt:", namen[bester])
    else:
        print("passt nicht mehr:", namen[bester])

print("Gesamtgewicht:", gewicht, "kg")
print("Gesamtwert:", wert, "Euro")
eingepackt: Erste-Hilfe-Set
eingepackt: Kocher
eingepackt: Zelt
passt nicht mehr: Schlafsack
passt nicht mehr: Proviant
Gesamtgewicht: 8 kg
Gesamtwert: 110 Euro
Versuch: Teste dein Gegenbeispiel

Ändere die Listen im Programm so, dass sie dein Gegenbeispiel aus dem Auftrag Ein Gegenbeispiel konstruieren enthalten, und ändere die Tragkraft. Liefert das Programm denselben Wert wie deine Handrechnung? Lass dann auch das Brute-Force-Programm mit deiner Instanz laufen. Dort musst du die Anzahl der Schleifen an die Anzahl der Gegenstände anpassen.

3.4.6Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

In mehreren Aufträgen geht es um diese Probleminstanz: Ben will auf dem Flohmarkt verkaufen. In seinen Fahrradanhänger passen höchstens 7 kg. Er schätzt, wie viel er für jede Sache bekommt.

Gegenstand Gewicht (kg) Wert (€)
Comics (C) 1 11
Bücherkiste (K) 4 32
Inline-Skates (I) 2 18
Lautsprecherbox (L) 5 50
Arbeitsauftrag 44: Ein Rucksackproblem im Alltag ●○○

Tim will Videos auf einen USB-Stick kopieren, um sie bei einem Filmabend zu zeigen. Auf den Stick passen 16 GB. Jedes Video hat eine Dateigröße (in GB) und eine Zahl von Likes. Tim möchte Videos mit möglichst vielen Likes zusammen mitnehmen. Seine Liste: „Skate-Tricks“ (4 GB, 120 Likes, 12 Minuten), „Klassenfahrt“ (7 GB, 300 Likes, 25 Minuten), „Katzenvideo“ (2 GB, 90 Likes, 3 Minuten), „Konzert“ (9 GB, 350 Likes, 40 Minuten).

  1. Erkläre, was in Tims Situation den Gegenständen, dem Gewicht, dem Wert und der Tragkraft entspricht.
  2. Stelle die Probleminstanz abstrahiert als Liste dar. Welche Angabe lässt du weg?
  3. Handelt es sich um ein Problem oder eine Probleminstanz? Begründe.

Deine Antworten:

Lösung vergleichen
  1. Gegenstände: die Videos. Gewicht: die Dateigröße in GB. Wert: die Zahl der Likes. Tragkraft: der Speicherplatz des Sticks (16 GB).
  2. Abstrahierte Liste, Tragkraft 16 GB:
Video Größe (GB) Likes
Skate-Tricks 4 120
Klassenfahrt 7 300
Katzenvideo 2 90
Konzert 9 350

Die Länge in Minuten lässt man weg. Sie spielt für die Frage keine Rolle (es kommt nur auf Speicherplatz und Likes an).

  1. Es ist eine Probleminstanz: Speicherplatz und Videos sind fest vorgegeben. Das zugehörige Problem ist das Rucksackproblem.
Arbeitsauftrag 45: Was passt in den Anhänger? ●○○

Prüfe für Bens Flohmarkt-Instanz jede Auswahl: Berechne das Gesamtgewicht und entscheide, ob sie zulässig ist. Berechne für die zulässigen Auswahlen auch den Gesamtwert.

Auswahl Gesamtgewicht (kg) zulässig? Gesamtwert (€)
Comics, Bücherkiste, Inline-Skates
Bücherkiste, Lautsprecherbox
Inline-Skates, Lautsprecherbox
Comics, Inline-Skates, Lautsprecherbox
Comics, Lautsprecherbox
Lösung vergleichen
Auswahl Gesamtgewicht (kg) zulässig? Gesamtwert (€)
Comics, Bücherkiste, Inline-Skates 1+4+2=71 + 4 + 2 = 7 ✓ 11+32+18=6111 + 32 + 18 = 61
Bücherkiste, Lautsprecherbox 4+5=94 + 5 = 9 ✗ –
Inline-Skates, Lautsprecherbox 2+5=72 + 5 = 7 ✓ 18+50=6818 + 50 = 68
Comics, Inline-Skates, Lautsprecherbox 1+2+5=81 + 2 + 5 = 8 ✗ –
Comics, Lautsprecherbox 1+5=61 + 5 = 6 ✓ 11+50=6111 + 50 = 61

Genau 7 kg ist noch zulässig, denn die Tragkraft darf nicht überschritten werden. Erst ab 8 kg ist der Anhänger zu schwer.

Arbeitsauftrag 46: Wert pro Kilogramm ●○○
  1. Berechne für jeden Gegenstand aus Bens Flohmarkt-Instanz das Wert-Gewicht-Verhältnis.
  2. Sortiere die Gegenstände absteigend nach diesem Verhältnis.
Gegenstand Gewicht (kg) Wert (€) Verhältnis (€ pro kg)
Comics 1 11
Bücherkiste 4 32
Inline-Skates 2 18
Lautsprecherbox 5 50

Sortierte Reihenfolge:

Lösung vergleichen
Gegenstand Gewicht (kg) Wert (€) Verhältnis (€ pro kg)
Comics 1 11 11:1=1111 : 1 = 11
Bücherkiste 4 32 32:4=832 : 4 = 8
Inline-Skates 2 18 18:2=918 : 2 = 9
Lautsprecherbox 5 50 50:5=1050 : 5 = 10

Sortiert: Comics (11), Lautsprecherbox (10), Inline-Skates (9), Bücherkiste (8).

Typischer Fehler: Gewicht durch Wert teilen (1:111 : 11). Dann wird die Reihenfolge genau umgedreht. Merke: Wert durch Gewicht, also „Euro pro Kilogramm“.

Arbeitsauftrag 47: Teilmengen zählen ●○○
  1. Lea darf für den Schulausflug drei Dinge einpacken oder weglassen: Apfel (A), Buch (B) und Cap (C). Schreibe alle möglichen Auswahlen auf. Vergiss die leere Auswahl nicht.
  2. Ergänze die Tabelle.
  3. Erkläre, warum sich die Anzahl verdoppelt, wenn ein Gegenstand dazukommt.
Gegenstände nn 1 2 3 4 6 8
Teilmengen 2n2^n

Deine Auswahlen und deine Erklärung:

Lösung vergleichen
  1. Die 8 Auswahlen: keine; A; B; C; A und B; A und C; B und C; A, B und C.
  2. Tabelle:
Gegenstände nn 1 2 3 4 6 8
Teilmengen 2n2^n 2 4 8 16 64 256
  1. Jede bisherige Auswahl gibt es mit dem neuen Gegenstand und ohne ihn. Aus jeder Auswahl werden also zwei. Bei 3 Gegenständen sind es 23=82^3 = 8 Auswahlen, wie in Teil 1.
Arbeitsauftrag 48: Brute-Force am Flohmarkt ●●○

Bestimme mit dem Brute-Force-Ansatz die optimale Auswahl für Bens Anhänger (Tragkraft 7 kg). Die Buchstaben stehen für Comics (C), Bücherkiste (K), Inline-Skates (I) und Lautsprecherbox (L).

  1. Wie viele Teilmengen musst du prüfen?
  2. Fülle die Tabelle aus. Berechne zuerst das Gewicht. Ist eine Teilmenge zu schwer, trage ✗ ein und lass den Wert weg.
  3. Markiere die optimale Lösung.
Nr. Auswahl Gewicht (kg) zulässig? Wert (€)
1 keine
2 L
3 I
4 I, L
5 K
6 K, L
7 K, I
8 K, I, L
9 C
10 C, L
11 C, I
12 C, I, L
13 C, K
14 C, K, L
15 C, K, I
16 C, K, I, L

Anzahl der Teilmengen und optimale Lösung:

Lösung vergleichen
  1. Bei 4 Gegenständen gibt es 24=162^4 = 16 Teilmengen.
  2. Tabelle:
Nr. Auswahl Gewicht (kg) zulässig? Wert (€)
1 keine 0 ✓ 0
2 L 5 ✓ 50
3 I 2 ✓ 18
4 I, L 7 ✓ 68
5 K 4 ✓ 32
6 K, L 9 ✗ –
7 K, I 6 ✓ 50
8 K, I, L 11 ✗ –
9 C 1 ✓ 11
10 C, L 6 ✓ 61
11 C, I 3 ✓ 29
12 C, I, L 8 ✗ –
13 C, K 5 ✓ 43
14 C, K, L 10 ✗ –
15 C, K, I 7 ✓ 61
16 C, K, I, L 12 ✗ –
  1. Optimal ist Nr. 4: Inline-Skates und Lautsprecherbox mit 7 kg und 68 €. 11 der 16 Teilmengen sind zulässig.
Arbeitsauftrag 49: Greedy am Flohmarkt ●●○
  1. Wende die Greedy-Heuristik auf Bens Flohmarkt-Instanz an. Die sortierte Reihenfolge kennst du aus dem Auftrag Wert pro Kilogramm. Lege eine Packtabelle an wie im Beispiel Greedy beim Tagesausflug.
  2. Vergleiche mit der optimalen Lösung aus dem Auftrag Brute-Force am Flohmarkt.
  3. Erkläre, warum die Heuristik hier nicht die optimale Lösung findet.
Gegenstand bisheriges Gewicht passt? Gewicht danach Wert danach

Dein Vergleich und deine Erklärung:

Lösung vergleichen
Gegenstand bisheriges Gewicht passt? Gewicht danach Wert danach
Comics 0 kg ja: 0+1=1≤70 + 1 = 1 \le 7 1 kg 11 €
Lautsprecherbox 1 kg ja: 1+5=6≤71 + 5 = 6 \le 7 6 kg 61 €
Inline-Skates 6 kg nein: 6+2=8>76 + 2 = 8 > 7 6 kg 61 €
Bücherkiste 6 kg nein: 6+4=10>76 + 4 = 10 > 7 6 kg 61 €

Greedy-Ergebnis: Comics und Lautsprecherbox, 6 kg, 61 €. Optimal sind Inline-Skates und Lautsprecherbox mit 68 €, also 7 € mehr.

Die Heuristik packt zuerst die Comics ein, weil sie pro Kilogramm am meisten bringen. Danach ist für die Inline-Skates 1 kg zu wenig Platz. 1 kg Tragkraft bleibt ungenutzt. Die optimale Lösung verzichtet auf die Comics und nutzt die 7 kg ganz aus.

Arbeitsauftrag 50: Fehler beim Packen ●●○

Für den Schulbasar transportiert Elif Gebäck in einem Bollerwagen, der höchstens 9 kg trägt:

Gebäck Gewicht (kg) Wert (€)
Waffeln 2 16
Muffins 4 28
Torte 5 30
Kekse 2 10
Limonade 1 4

Elif wendet die Greedy-Heuristik so an:

  1. Finde Elifs zwei Fehler und erkläre sie.
  2. Wende die Heuristik richtig an. Gib Auswahl, Gesamtgewicht und Gesamtwert an.

Elifs Fehler und deine richtige Lösung:

Lösung vergleichen
  1. Elifs Fehler:
    • Bei den Keksen hat sie Gewicht durch Wert gerechnet. Richtig ist 10:2=510 : 2 = 5. Die Kekse gehören also vor die Limonade.
    • Sie hört auf, sobald die Torte nicht passt. Die Heuristik geht die Liste aber bis zum Ende durch, denn leichtere Gegenstände können noch passen.
  2. Richtige Reihenfolge: Waffeln (8), Muffins (7), Torte (6), Kekse (5), Limonade (4). Waffeln: 0+2=20 + 2 = 2 ✓. Muffins: 2+4=62 + 4 = 6 ✓. Torte: 6+5=11>96 + 5 = 11 > 9 ✗. Kekse: 6+2=86 + 2 = 8 ✓. Limonade: 8+1=98 + 1 = 9 ✓. Ergebnis: Waffeln, Muffins, Kekse und Limonade mit 9 kg und 16+28+10+4=5816 + 28 + 10 + 4 = 58 €. Das sind 14 € mehr als bei Elif.
Arbeitsauftrag 51: Gegenbeispiel oder nicht? ●●●

Drei Personen behaupten, ein Gegenbeispiel für die Greedy-Heuristik gefunden zu haben. Prüfe jede Behauptung: Wende die Greedy-Heuristik an und bestimme mit Brute-Force die optimale Lösung (8 Teilmengen). Entscheide dann, ob wirklich ein Gegenbeispiel vorliegt.

Person Tragkraft Gegenstand X Gegenstand Y Gegenstand Z
Emma 5 kg 3 kg, 15 € 2 kg, 8 € 2 kg, 7 €
Noah 6 kg 4 kg, 20 € 3 kg, 13 € 3 kg, 12 €
Lea 4 kg 1 kg, 6 € 4 kg, 20 € 3 kg, 12 €

Deine Prüfung:

Lösung vergleichen

Die Verhältnisse sind bei allen drei Instanzen in der Reihenfolge X, Y, Z absteigend sortiert: Emma 5; 4; 3,5. Noah 5; 4,33; 4. Lea 6; 5; 4.

Emma (Tragkraft 5 kg): Greedy nimmt X (3 kg) und Y (3+2=53 + 2 = 5). Z passt nicht mehr (5+2=7>55 + 2 = 7 > 5). Greedy: 23 €. Brute-Force: Zulässig sind keine (0 €), X (15 €), Y (8 €), Z (7 €), X und Y (23 €), X und Z (22 €), Y und Z (15 €). X, Y und Z ist mit 7 kg zu schwer. Optimal: 23 €. Kein Gegenbeispiel, die Heuristik ist hier optimal.

Noah (Tragkraft 6 kg): Greedy nimmt X (4 kg). Y passt nicht (4+3=7>64 + 3 = 7 > 6), Z auch nicht. Greedy: 20 €. Brute-Force: Zulässig sind keine, X (20 €), Y (13 €), Z (12 €), Y und Z (6 kg, 25 €). Alle Teilmengen mit X und einem weiteren Gegenstand sind zu schwer. Optimal: 25 € (Y und Z). Gegenbeispiel.

Lea (Tragkraft 4 kg): Greedy nimmt X (1 kg). Y passt nicht (1+4=5>41 + 4 = 5 > 4). Z passt (1+3=41 + 3 = 4). Greedy: 18 €. Brute-Force: Zulässig sind keine, X (6 €), Y (20 €), Z (12 €), X und Z (18 €). Alle anderen sind zu schwer. Optimal: 20 € (Y allein). Gegenbeispiel.

Eine Instanz ist nur dann ein Gegenbeispiel, wenn der Greedy-Wert kleiner ist als der optimale Wert. Dafür musst du beide Ansätze wirklich durchrechnen.

3.4.7Das Wichtigste in Kürze

Selbstcheck

3.5Aufwand: Wie lange dauert das Ausprobieren? DS28

Diesen Abschnitt als PDF (S. 78–90)

Das Jupyter-Notebook aus dem Unterricht: DS28_Aufwandsvergleich.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Eine alte Legende erzählt vom Erfinder des Schachspiels. Als Belohnung wünschte er sich Reis: ein Korn auf das erste Feld des Schachbretts, zwei auf das zweite, vier auf das dritte – auf jedes Feld doppelt so viele wie auf das vorige. Der König hielt das für einen bescheidenen Wunsch. Doch allein auf dem letzten Feld müssten 2632^{63}, also über 9 Trillionen Körner liegen. Das ist mehr Reis, als heute auf der ganzen Welt in hundert Jahren geerntet wird. Genauso überraschend wächst die Anzahl der Möglichkeiten, die Brute-Force ausprobieren muss. In diesem Abschnitt rechnest du nach, wie schnell sie wächst, und vergleichst den Aufwand von Brute-Force und Heuristik.

Lernziele

Nach diesem Abschnitt kannst du

3.5.1Was ist Aufwand?

Wenn du ein Zimmer aufräumst, kannst du den Aufwand auf zwei Arten angeben: „Ich musste 40 Dinge wegräumen“ oder „Ich habe 25 Minuten gebraucht“. Die erste Angabe hängt nur vom Zimmer ab. Die zweite hängt auch davon ab, wie schnell du bist.

In der Informatik ist es ähnlich. Den Aufwand eines Lösungsansatzes beschreibt man anschaulich so:

Die Rechenzeit hängt vom Computer ab: Ein neuer Rechner ist schneller als ein alter. Die Anzahl der Möglichkeiten hängt dagegen nur von der Probleminstanz und vom Lösungsansatz ab. Deshalb rechnen wir in diesem Abschnitt vor allem mit ihr.

Definition: Aufwand

Der Aufwand eines Lösungsansatzes gibt an, wie viel Arbeit nötig ist, um eine Probleminstanz zu lösen. Anschaulich misst man ihn als Anzahl der zu prüfenden Möglichkeiten oder als Rechenzeit.

Merke

Der Aufwand eines Lösungsansatzes lässt sich anschaulich als Anzahl der zu prüfenden Möglichkeiten oder als tatsächlich gemessene Rechenzeit beschreiben.

3.5.2Brute-Force beim Handlungsreisenden: faktorielles Wachstum

Ein Programm hat alle Rundreisen für 2 bis 8 Orte erzeugt und gezählt (Startort fest, ohne Berücksichtigung der Symmetrie). Das ist das Ergebnis:

Orte nn Anzahl der Rundreisen
2 1
3 2
4 6
5 24
6 120
7 720
8 5 040

Das sind genau die Werte von (n−1)!(n-1)!, die du im Abschnitt über Brute-Force hergeleitet hast. Bei 8 Orten ist es zum Beispiel 7!=7⋅6⋅5⋅4⋅3⋅2⋅1=50407! = 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 5040.

Merke

Beim Problem des Handlungsreisenden (Brute-Force) wächst der Aufwand faktoriell mit der Anzahl der Städte: (n−1)!(n-1)!

Wie lange braucht ein Computer dafür? Nehmen wir einen sehr schnellen Computer an, der eine Milliarde (10000000001\,000\,000\,000) Rundreisen pro Sekunde prüfen kann. Das ist sehr großzügig gerechnet. Dann gilt:

Zeit in Sekunden=Anzahl der Rundreisen1000000000\text{Zeit in Sekunden} = \frac{\text{Anzahl der Rundreisen}}{1\,000\,000\,000}

Bei 8 Orten sind das 5040:1000000000=0,000005045040 : 1\,000\,000\,000 = 0{,}000\,005\,04 Sekunden – nur ein paar Millionstel Sekunden. Kein Grund zur Sorge also? Rechne selbst weiter.

Arbeitsauftrag 52: Tabelle interpretieren

Betrachte die Tabelle mit den Anzahlen der Rundreisen für 2 bis 8 Orte.

  1. Um welchen Faktor wächst die Anzahl der Rundreisen jeweils von nn zu n+1n + 1 Orten? Beschreibe das Muster.
  2. Schätze anhand des Musters (ohne die Fakultät direkt auszurechnen), wie viele Rundreisen es bei 12 Orten gibt. Wie lange würde der Computer mit einer Milliarde Rundreisen pro Sekunde dafür brauchen?
  3. Und bei 20 Orten? Berechne die Anzahl mit dem Taschenrechner (Taste x!x!) und die Zeit in Jahren. Ein Jahr hat 365⋅24⋅60⋅60=31536000365 \cdot 24 \cdot 60 \cdot 60 = 31\,536\,000 Sekunden.

Deine Antworten:

Lösung vergleichen
  1. Von 2 auf 3 Orte verdoppelt sich die Anzahl, von 3 auf 4 verdreifacht sie sich, von 4 auf 5 vervierfacht sie sich und so weiter. Von nn auf n+1n + 1 Orte wächst die Anzahl um den Faktor nn. Der Grund: Der neue Ort kann an jeder der nn möglichen Stellen in eine bisherige Rundreise eingefügt werden. Der Faktor wird also selbst immer größer.
  2. Ausgehend von 8 Orten: 5040⋅8=403205040 \cdot 8 = 40\,320 (9 Orte), ⋅9=362880\cdot\, 9 = 362\,880 (10 Orte), ⋅10=3628800\cdot\, 10 = 3\,628\,800 (11 Orte), ⋅11=39916800\cdot\, 11 = 39\,916\,800 (12 Orte). Das ist genau 11!11!. Zeit: 39916800:1000000000≈0,0439\,916\,800 : 1\,000\,000\,000 \approx 0{,}04 Sekunden. Das ist noch kein Problem.
  3. Bei 20 Orten sind es 19!=12164510040883200019! = 121\,645\,100\,408\,832\,000 Rundreisen, also etwa 1,2⋅10171{,}2 \cdot 10^{17}. Zeit: 121645100408832000:1000000000≈121645100121\,645\,100\,408\,832\,000 : 1\,000\,000\,000 \approx 121\,645\,100 Sekunden. Geteilt durch 3153600031\,536\,000 Sekunden pro Jahr ergibt das etwa 3,9 Jahre.

Von 12 auf 20 Orte steigt die Zeit also von einem Wimpernschlag auf fast vier Jahre.

Die folgende Tabelle setzt die Rechnung fort. Die Zeiten gelten für den Computer mit einer Milliarde Rundreisen pro Sekunde.

Orte nn Rundreisen (n−1)!(n-1)! Rechenzeit
10 362 880 weniger als eine Tausendstelsekunde
12 39 916 800 etwa 0,04 Sekunden
15 87 178 291 200 etwa 87 Sekunden (knapp 1,5 Minuten)
18 355 687 428 096 000 etwa 4,1 Tage
20 121 645 100 408 832 000 etwa 3,9 Jahre
25 620 448 401 733 239 439 360 000 etwa 20 Millionen Jahre

Und die Symmetrie? Sie halbiert die Anzahl der Rundreisen, die man wirklich prüfen muss. Bei 25 Orten wären es dann „nur“ noch etwa 10 Millionen Jahre. Das ändert am Ergebnis nichts: Brute-Force ist für 25 Orte hoffnungslos – dabei hat ein Paketdienst oft über 100 Adressen am Tag.

Stolperstein

Ein doppelt so schneller Computer hilft kaum. Er schafft in derselben Zeit doppelt so viele Rundreisen. Aber schon ein zusätzlicher Ort vervielfacht die Anzahl: Von 20 auf 21 Orte wächst sie auf das Zwanzigfache. Schnellere Computer verschieben die Grenze nur um wenige Orte.

3.5.3Brute-Force beim Rucksack: exponentielles Wachstum

Beim Rucksackproblem verdoppelt jeder zusätzliche Gegenstand die Anzahl der Teilmengen. Bei nn Gegenständen sind es 2n2^n. Das ist das Muster aus der Schachbrett-Legende.

Merke

Beim Rucksackproblem (Brute-Force) wächst der Aufwand exponentiell mit der Anzahl der Gegenstände: 2n2^n

Arbeitsauftrag 53: Brute-Force und Greedy beim Rucksack
  1. Berechne für eine wachsende Anzahl von Gegenständen die Anzahl der Teilmengen, die Brute-Force prüfen muss, und trage sie in die Tabelle ein.
  2. Vergleiche gedanklich mit dem Aufwand der Greedy-Heuristik: Wie viele Gegenstände muss sie jeweils prüfen, nachdem die Liste sortiert ist?
Gegenstände nn Teilmengen 2n2^n (Brute-Force) Prüfungen der Greedy-Heuristik
5
10
15
18

Dein Vergleich:

Lösung vergleichen
Gegenstände nn Teilmengen 2n2^n (Brute-Force) Prüfungen der Greedy-Heuristik
5 32 5
10 1 024 10
15 32 768 15
18 262 144 18

Brute-Force muss bei 18 Gegenständen schon über eine Viertelmillion Teilmengen prüfen. Die Greedy-Heuristik geht die sortierte Liste nur einmal durch: 18 Prüfungen. Dazu kommen noch das Berechnen der 18 Verhältnisse und das Sortieren. Auch zusammen sind das nur wenige hundert Schritte. Jeder weitere Gegenstand verdoppelt den Aufwand von Brute-Force, bei Greedy kommt nur ein bisschen Arbeit dazu.

Auch hier lohnt sich ein Blick auf größere Instanzen. Wieder gilt: eine Milliarde Teilmengen pro Sekunde.

Gegenstände nn Teilmengen 2n2^n Rechenzeit
20 1 048 576 etwa eine Tausendstelsekunde
30 1 073 741 824 etwa 1 Sekunde
40 1 099 511 627 776 etwa 18 Minuten
50 1 125 899 906 842 624 etwa 13 Tage
60 1 152 921 504 606 846 976 etwa 37 Jahre

Merkst du das Muster? Zehn Gegenstände mehr bedeuten jeweils etwa das Tausendfache, denn 210=10242^{10} = 1024.

Faktoriell oder exponentiell – was wächst schneller?

Vergleiche die beiden Wachstumsarten für kleine Werte von nn:

nn 1 2 3 4 5 6 7 8 9 10
(n−1)!(n-1)! 1 1 2 6 24 120 720 5 040 40 320 362 880
2n2^n 2 4 8 16 32 64 128 256 512 1 024

Bei n=1n = 1 steht in der Tabelle (1−1)!=0!=1(1-1)! = 0! = 1 (zur Erinnerung: 0!=10! = 1 ist so festgelegt). Bis n=5n = 5 ist 2n2^n größer. Ab n=6n = 6 überholt (n−1)!(n-1)! und lässt 2n2^n weit hinter sich. Der Grund: Bei 2n2^n wird bei jedem Schritt mit 2 multipliziert, bei der Fakultät mit einer immer größeren Zahl. Beide Wachstumsarten sind aber so schnell, dass Brute-Force schon bei mittelgroßen Instanzen unbrauchbar wird.

3.5.4Und die Heuristiken?

Wie viel Arbeit macht die Nearest-Neighbor-Heuristik? Bei nn Orten muss sie im ersten Schritt n−1n - 1 Entfernungen ansehen, im zweiten n−2n - 2 und so weiter bis 1. Bei 20 Orten sind das

19+18+17+…+2+1=19019 + 18 + 17 + \ldots + 2 + 1 = 190

Entfernungen. Brute-Force bräuchte dagegen 19!19!, also etwa 1,2⋅10171{,}2 \cdot 10^{17} Rundreisen.

Bei der Greedy-Heuristik für den Rucksack mit 20 Gegenständen: 20 Verhältnisse berechnen, die Liste sortieren und 20-mal prüfen, ob ein Gegenstand passt. Auch mit einem einfachen Sortierverfahren sind das nur wenige hundert Schritte statt über einer Million Teilmengen.

bei n=20n = 20 Brute-Force Greedy-Heuristik
Handlungsreisender 19!≈1,2⋅101719! \approx 1{,}2 \cdot 10^{17} Rundreisen 190 Entfernungen (Nearest Neighbor)
Rucksack 220=10485762^{20} = 1\,048\,576 Teilmengen wenige hundert Schritte (Wert-Gewicht-Verhältnis)
Merke

Deshalb setzt man in der Praxis bei großen Probleminstanzen fast immer Heuristiken ein. Man nimmt in Kauf, dass die Lösung vielleicht nicht optimal ist – dafür bekommt man überhaupt eine Lösung, und zwar rechtzeitig.

So kannst du es sagen

So vergleichst du den Aufwand in Fachsprache:

3.5.5Wachstum im Diagramm

Die Zahlen werden so schnell so groß, dass sie in ein normales Diagramm nicht hineinpassen. Wenn die Hochachse bis 400 000 reicht, verschwinden alle Werte bis 1000 als Punkte auf der Rechtsachse. Man benutzt deshalb eine besondere Einteilung.

Werkzeug

Bei einer logarithmischen Skala bedeutet jeder Schritt auf der Hochachse das Zehnfache: Auf 1 folgt 10, dann 100, 1000 und so weiter. Die dünnen Linien dazwischen stehen für 2, 3, …, 9 (bzw. 20, 30, …, 90 usw.). Sie liegen nicht gleichmäßig, sondern rücken nach oben immer enger zusammen. Ein Wert wie 24 liegt also zwischen der Linie für 20 und der für 30, etwas näher an 20. So passen sehr kleine und sehr große Zahlen in ein Diagramm.

Arbeitsauftrag 54 (Zusatz): Diagramm zum Wachstum

Stelle das faktorielle Wachstum (Handlungsreisender, (n−1)!(n-1)!) und das exponentielle Wachstum (Rucksack, 2n2^n) für n=1n = 1 bis 1010 in dem Diagramm mit logarithmischer Skala gegenüber. Nimm die Werte aus der Tabelle im Abschnitt Faktoriell oder exponentiell. Zeichne die Punkte ein, verbinde sie und kennzeichne die beiden Kurven. Beschreibe, was du erkennst.

Leeres Diagramm mit logarithmischer Hochachse

Das erkenne ich:

Lösung vergleichen
Rot: Rundreisen (n-1)! beim Handlungsreisenden. Blau: Teilmengen 2^n beim Rucksack. Hochachse logarithmisch

Die Punkte von 2n2^n liegen auf einer Geraden: Bei einer logarithmischen Skala erkennt man exponentielles Wachstum genau daran, denn bei jedem Schritt wird mit demselben Faktor 2 multipliziert. Die Kurve von (n−1)!(n-1)! wird dagegen immer steiler, weil der Faktor bei jedem Schritt größer wird. Zwischen n=5n = 5 und n=6n = 6 kreuzen sich die Kurven: Ab 6 ist (n−1)!(n-1)! größer als 2n2^n.

3.5.6Für Interessierte: Die Tabelle mit Python berechnen

Dieser Unterabschnitt ist freiwillig. Python kann mit beliebig großen ganzen Zahlen rechnen. Die Fakultät berechnest du, indem du bei jedem Schritt mit der nächsten Zahl multiplizierst – genau wie im Auftrag Tabelle interpretieren.

rundreisen = 1
for n in range(2, 13):
    if n > 2:
        rundreisen = rundreisen * (n - 1)
    print(n, rundreisen, 2 ** n)
2 1 4
3 2 8
4 6 16
5 24 32
6 120 64
7 720 128
8 5040 256
9 40320 512
10 362880 1024
11 3628800 2048
12 39916800 4096
Versuch: Weiter rechnen

Ändere range(2, 13) in range(2, 26). Vergleiche die letzte Zeile mit der Tabelle im Abschnitt über das faktorielle Wachstum. Ergänze dann eine Ausgabe der Rechenzeit in Sekunden: rundreisen / 1000000000. Python schreibt sehr kleine Kommazahlen in einer Kurzform: 1e-09 bedeutet 1⋅10−91 \cdot 10^{-9}, also eine Milliardstel.

3.5.7Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 55: Sätze zum Aufwand ●○○

Ergänze die Sätze.

Satzanfang Ergänzung
Den Aufwand eines Lösungsansatzes kann man angeben als Anzahl der …
… oder als gemessene …
Beim Handlungsreisenden prüft Brute-Force bei nn Orten so viele Rundreisen: …
Dieses Wachstum nennt man …
Beim Rucksackproblem prüft Brute-Force bei nn Gegenständen so viele Teilmengen: …
Dieses Wachstum nennt man …
Eine Greedy-Heuristik prüft im Vergleich zu Brute-Force …
Lösung vergleichen
Satzanfang Ergänzung
Den Aufwand eines Lösungsansatzes kann man angeben als Anzahl der … zu prüfenden Möglichkeiten,
… oder als gemessene … Rechenzeit.
Beim Handlungsreisenden prüft Brute-Force bei nn Orten so viele Rundreisen: … (n−1)!(n-1)!
Dieses Wachstum nennt man … faktoriell.
Beim Rucksackproblem prüft Brute-Force bei nn Gegenständen so viele Teilmengen: … 2n2^n
Dieses Wachstum nennt man … exponentiell.
Eine Greedy-Heuristik prüft im Vergleich zu Brute-Force … wesentlich weniger Möglichkeiten.
Arbeitsauftrag 56: Zweierpotenzen ●○○
  1. Ergänze die Tabelle. Tipp: Jede Zahl ist doppelt so groß wie die davor.
  2. Wie viele Teilmengen muss Brute-Force bei 12 Gegenständen prüfen, wie viele bei 13?
nn 5 6 7 8 9 10 11 12
2n2^n 32

Deine Antwort zu 2:

Lösung vergleichen
nn 5 6 7 8 9 10 11 12
2n2^n 32 64 128 256 512 1 024 2 048 4 096

Bei 12 Gegenständen sind es 212=40962^{12} = 4096 Teilmengen, bei 13 Gegenständen doppelt so viele: 213=81922^{13} = 8192.

Arbeitsauftrag 57: Rundreisen oder Teilmengen? ●○○

Entscheide bei jeder Situation, ob sie zum Problem des Handlungsreisenden oder zum Rucksackproblem passt. Gib an, wie viele Möglichkeiten Brute-Force prüfen muss, und ob das Wachstum faktoriell oder exponentiell ist.

Situation Problem Anzahl der Möglichkeiten Wachstum
Ein Bäcker beliefert morgens 6 Cafés und kehrt zur Backstube zurück (7 Orte).
Für eine Wanderung stehen 7 Gegenstände zur Auswahl, der Rucksack hat eine Tragkraft.
Auf dem Handy ist Speicher frei. Von 10 Apps soll Lina einige installieren, die zusammen möglichst nützlich sind.
Ein Schulbus holt Kinder an 9 Haltestellen ab und fährt zur Schule zurück, von der er gestartet ist (10 Orte).
Lösung vergleichen
Situation Problem Anzahl der Möglichkeiten Wachstum
Bäcker, 7 Orte Handlungsreisender (7−1)!=6!=720(7-1)! = 6! = 720 faktoriell
Wanderung, 7 Gegenstände Rucksack 27=1282^7 = 128 exponentiell
Apps, 10 Stück Rucksack 210=10242^{10} = 1024 exponentiell
Schulbus, 10 Orte Handlungsreisender (10−1)!=9!=362880(10-1)! = 9! = 362\,880 faktoriell

Bei den Apps entspricht der Speicherplatz der Tragkraft: Jede App wird installiert oder nicht. Beim Schulbus zählt die Schule als Ort mit, deshalb ist n=10n = 10.

Arbeitsauftrag 58: Wer muss mehr prüfen? ●○○

Vergleiche den Aufwand von Brute-Force beim Handlungsreisenden mit nn Orten und beim Rucksack mit nn Gegenständen. Ergänze die Tabelle und gib an, bei welchem Problem Brute-Force mehr prüfen muss.

nn Rundreisen (n−1)!(n-1)! Teilmengen 2n2^n mehr muss prüfen …
4
5
6
8

Das fällt mir auf:

Lösung vergleichen
nn Rundreisen (n−1)!(n-1)! Teilmengen 2n2^n mehr muss prüfen …
4 6 16 Rucksack
5 24 32 Rucksack
6 120 64 Handlungsreisender
8 5 040 256 Handlungsreisender

Bei kleinen Zahlen hat der Rucksack mehr Möglichkeiten. Ab 6 überholt der Handlungsreisende, und der Abstand wird schnell riesig: Beim Handlungsreisenden wird mit einer immer größeren Zahl multipliziert, beim Rucksack immer nur mit 2.

Arbeitsauftrag 59: Wie lange rechnet der Computer? ●●○

Ein Laptop prüft eine Million Rundreisen pro Sekunde.

  1. Wie lange braucht er für Brute-Force bei 10, 12 und 14 Orten? Nutze die Werte 9!=3628809! = 362\,880, 11!=3991680011! = 39\,916\,800 und 13!=622702080013! = 6\,227\,020\,800.
  2. Eine Lieferfirma muss ihre Route jeden Morgen in höchstens 5 Minuten berechnen. Für wie viele Orte reicht Brute-Force auf diesem Laptop? Begründe.

Deine Rechnungen:

Lösung vergleichen
  1. Zeit = Anzahl : 1 000 000.
    • 10 Orte: 362880:1000000≈0,36362\,880 : 1\,000\,000 \approx 0{,}36 Sekunden.
    • 12 Orte: 39916800:1000000≈4039\,916\,800 : 1\,000\,000 \approx 40 Sekunden.
    • 14 Orte: 6227020800:1000000≈62276\,227\,020\,800 : 1\,000\,000 \approx 6227 Sekunden, das sind etwa 104 Minuten, also gut 1,7 Stunden.
  2. 5 Minuten sind 300 Sekunden, also 300 Millionen Rundreisen. Bei 12 Orten sind es knapp 40 Millionen (40 Sekunden). Bei 13 Orten sind es 12!=12⋅11!=47900160012! = 12 \cdot 11! = 479\,001\,600, also etwa 479 Millionen. Das dauert etwa 479 Sekunden, also rund 8 Minuten – zu lange. Brute-Force reicht deshalb nur bis 12 Orte.
Arbeitsauftrag 60: Wie viele Gegenstände schafft der Laptop? ●●○

Derselbe Laptop prüft eine Million Teilmengen pro Sekunde.

  1. Wie lange braucht er bei 20, 30 und 40 Gegenständen? Nutze 220=10485762^{20} = 1\,048\,576, 230=10737418242^{30} = 1\,073\,741\,824 und 240=10995116277762^{40} = 1\,099\,511\,627\,776.
  2. Der Laptop darf eine Stunde rechnen. Das sind 3 600 000 000 Teilmengen. Wie viele Gegenstände kann er höchstens untersuchen? Tipp: Beginne bei 2302^{30} und verdopple.

Deine Rechnungen:

Lösung vergleichen
  1. Zeit = Anzahl : 1 000 000.
    • 20 Gegenstände: etwa 1 Sekunde.
    • 30 Gegenstände: etwa 10741074 Sekunden, also knapp 18 Minuten.
    • 40 Gegenstände: etwa 10995121\,099\,512 Sekunden. Geteilt durch 8640086\,400 Sekunden pro Tag sind das fast 13 Tage.
  2. 230≈1,072^{30} \approx 1{,}07 Milliarden, 231≈2,152^{31} \approx 2{,}15 Milliarden, 232≈4,292^{32} \approx 4{,}29 Milliarden. In einer Stunde schafft der Laptop 3,6 Milliarden. 2312^{31} passt noch, 2322^{32} nicht mehr. Er schafft also höchstens 31 Gegenstände.
Arbeitsauftrag 61: Ein zehnmal schnellerer Computer ●●●

Der Laptop aus den letzten beiden Aufträgen braucht für Brute-Force beim Handlungsreisenden mit 12 Orten etwa 40 Sekunden und beim Rucksack mit 20 Gegenständen etwa 1 Sekunde. Ein neuer Computer ist zehnmal so schnell.

  1. Wie viele Orte kann der neue Computer in 40 Sekunden untersuchen? Begründe mit dem Faktor, um den die Anzahl der Rundreisen wächst.
  2. Wie viele Gegenstände kann er in 1 Sekunde untersuchen? Begründe ebenso.
  3. Was folgt daraus: Lässt sich das Problem des großen Aufwands mit schnelleren Computern lösen?

Deine Antworten:

Lösung vergleichen
  1. Der neue Computer schafft in derselben Zeit zehnmal so viele Rundreisen. Von 12 auf 13 Orte wächst die Anzahl aber um den Faktor 12 (12!=12⋅11!12! = 12 \cdot 11!). Das ist mehr als 10. Der neue Computer schafft in 40 Sekunden also immer noch nur 12 Orte – nicht einmal einen Ort mehr.
  2. Beim Rucksack verdoppelt jeder Gegenstand die Anzahl. Drei Gegenstände mehr bedeuten das 2⋅2⋅2=82 \cdot 2 \cdot 2 = 8-Fache, vier mehr das 16-Fache. Das 8-Fache schafft der zehnmal schnellere Computer, das 16-Fache nicht. Er kommt also auf 23 Gegenstände statt 20.
  3. Nein. Ein zehnmal schnellerer Computer verschiebt die Grenze nur um wenige Gegenstände und beim Handlungsreisenden um gar keinen Ort. Der Aufwand von Brute-Force wächst so schnell, dass schnellere Computer kaum helfen. Für große Probleminstanzen braucht man Heuristiken.

3.5.8Das Wichtigste in Kürze

Selbstcheck

3.6Heuristiken bewerten und Rückblick DS29

Diesen Abschnitt als PDF (S. 91–107)

Das Jupyter-Notebook aus dem Unterricht: DS29_Bewertung_Heuristiken_Abschluss.ipynb. Herunterladen und in VS Code oder Jupyter öffnen.

Leitidee

Du hast gesehen: Die Nearest-Neighbor-Heuristik findet bei den vier Orten manchmal die optimale Rundreise und manchmal nicht. Die Greedy-Heuristik für den Rucksack war beim Tagesausflug optimal, bei der Wanderung nicht. Wie gut ist eine Heuristik denn nun? Mit einem einzigen Test kann man das nicht sagen – so wie man ein Navigationsgerät nicht nach einer einzigen Fahrt beurteilt. In diesem Abschnitt lernst du, wie man Heuristiken an vielen Probleminstanzen prüft und das Ergebnis in Zahlen fasst. Zum Schluss blickst du auf das ganze Kapitel zurück und bereitest dich auf einen möglichen Test vor.

Lernziele

Nach diesem Abschnitt kannst du

3.6.1Die Abweichung als Maßstab

Um eine Heuristik zu bewerten, vergleicht man ihre Lösung mit der optimalen Lösung. Dafür muss die optimale Lösung bekannt sein. Bei kleinen Probleminstanzen kann man sie mit Brute-Force berechnen. Üblich ist es, den Unterschied in Prozent anzugeben. So kann man auch Instanzen mit ganz unterschiedlichen Zahlen vergleichen: 10 km Umweg sind bei einer 50-km-Tour viel, bei einer 500-km-Tour wenig.

Du kennst schon zwei Formeln. Beim Handlungsreisenden ist eine kleinere Länge besser:

Abweichung=Länge der Heuristik−optimale Längeoptimale Länge⋅100%\text{Abweichung} = \frac{\text{Länge der Heuristik} - \text{optimale Länge}}{\text{optimale Länge}} \cdot 100\,\%

Beim Rucksackproblem ist ein größerer Wert besser:

Abweichung=optimaler Wert−Wert der Heuristikoptimaler Wert⋅100%\text{Abweichung} = \frac{\text{optimaler Wert} - \text{Wert der Heuristik}}{\text{optimaler Wert}} \cdot 100\,\%

In beiden Fällen gilt: Man teilt durch das Optimum, und das Ergebnis ist nie negativ. 0 % bedeutet, dass die Heuristik die optimale Lösung getroffen hat. Je größer die Abweichung, desto schlechter.

Merke

Um eine Heuristik zu bewerten, vergleicht man ihre Lösung mit der optimalen Lösung (sofern diese bekannt bzw. berechenbar ist). Üblich ist die prozentuale Abweichung.

3.6.2Eine Heuristik, viele Probleminstanzen

Ein einziger Test sagt wenig. Vielleicht hatte die Heuristik Glück, vielleicht Pech. Das hast du schon bei den vier Orten A, B, C und D erlebt: Mit Start in A war Nearest Neighbor optimal, mit Start in D um 18,75 % zu lang.

Merke

Den Durchschnitt (das arithmetische Mittel) kennst du aus Mathe: Man addiert alle Werte und teilt durch ihre Anzahl.

Beispiel: Nearest Neighbor mit allen Startorten

Für die vier Orte A, B, C, D (optimal: 80 km) und die fünf Orte A bis E (optimal: 100 km) wurde Nearest Neighbor von jedem Startort aus durchgeführt:

Startort A B C D E Durchschnitt
vier Orte: Länge 80 80 80 95 –
vier Orte: Abweichung 0 % 0 % 0 % 18,75 % – 4,7 %
fünf Orte: Länge 111 100 100 110 100
fünf Orte: Abweichung 11 % 0 % 0 % 10 % 0 % 4,2 %

Rechnung für vier Orte: (0+0+0+18,75):4≈4,7(0 + 0 + 0 + 18{,}75) : 4 \approx 4{,}7 (in Prozent). Für fünf Orte: (11+0+0+10+0):5=4,2(11 + 0 + 0 + 10 + 0) : 5 = 4{,}2 (in Prozent).

Im Durchschnitt liegt die Heuristik also weniger als 5 % über dem Optimum. Im ungünstigsten Fall waren es aber fast 19 %. Beides gehört zu einer ehrlichen Bewertung: der Durchschnitt und der schlechteste Fall.

3.6.3Ein Computerexperiment

Mit vier oder fünf Orten kann man nicht viel über eine Heuristik lernen. Für ein aussagekräftigeres Ergebnis hat ein Computer das folgende Experiment durchgeführt:

Instanz optimal (km) Nearest Neighbor (km) Abweichung
1 119 119 0,0 %
2 92 92 0,0 %
3 79 79 0,0 %
4 122 124 1,6 %
5 81 81 0,0 %
6 113 113 0,0 %
7 78 109 39,7 %
8 67 75 11,9 %
9 83 87 4,8 %
10 114 135 18,4 %
Durchschnitt 7,7 %

Du kannst einzelne Zeilen nachrechnen. Für Instanz 4 zum Beispiel: 124−122122⋅100%≈1,6%\frac{124 - 122}{122} \cdot 100\,\% \approx 1{,}6\,\%.

Arbeitsauftrag 62: Auswertung des Experiments

Beantworte anhand der Tabelle:

  1. Gab es Instanzen, bei denen die Heuristik die optimale Lösung getroffen hat (Abweichung 0 %)? Wie viele?
  2. Wie groß war die größte beobachtete Abweichung, und bei welcher Instanz trat sie auf?
  3. Ist die Nearest-Neighbor-Heuristik deiner Einschätzung nach für den praktischen Einsatz geeignet? Begründe.

Deine Antworten:

Lösung vergleichen
  1. Ja. Bei 5 von 10 Instanzen (Nr. 1, 2, 3, 5 und 6) hat die Heuristik die optimale Lösung gefunden.
  2. Die größte Abweichung war 39,7 % bei Instanz 7: 109 km statt 78 km, also 31 km Umweg.
  3. Eine mögliche begründete Einschätzung:
    • Dafür: Im Durchschnitt ist die Heuristik nur 7,7 % schlechter als das Optimum, und in der Hälfte der Fälle ist sie sogar optimal. Sie ist außerdem sehr schnell. Bei großen Instanzen, bei denen Brute-Force unmöglich ist, liefert sie überhaupt erst eine Lösung.
    • Dagegen: Einzelne Ausreißer sind deutlich schlechter (fast 40 %). Wer jeden Tag fährt, verschenkt dann viel Zeit und Kraftstoff.
    • Fazit: Für den praktischen Einsatz ist die Heuristik geeignet, wenn eine schnelle, meist gute Lösung genügt. Man sollte sie aber verbessern, zum Beispiel indem man sie von jedem Startort aus durchführt und die kürzeste Rundreise nimmt. Bei kleinen Instanzen kann man das Optimum mit Brute-Force berechnen.

Worauf es ankommt: Deine Einschätzung muss sich auf die Zahlen stützen (Durchschnitt und schlechtester Fall) und den geringen Aufwand der Heuristik berücksichtigen.

Stolperstein

Der Durchschnitt allein kann täuschen. 7,7 % klingt harmlos, aber bei Instanz 7 waren es fast 40 %. Nenne bei einer Bewertung deshalb immer auch den schlechtesten Fall. Und: Zehn Instanzen sind schon besser als eine, aber für eine wirklich sichere Aussage testet man viel mehr – und auch größere Instanzen.

3.6.4Die Ausreißer-Instanz genauer untersucht

Warum hat Nearest Neighbor bei Instanz 7 so schlecht abgeschnitten? Das kannst du selbst herausfinden. Die Orte heißen hier A bis F.

Arbeitsauftrag 63: Instanz 7 von Hand

Hier ist die Entfernungstabelle von Instanz 7 (in km):

A B C D E F
A – 41 10 36 21 7
B 41 – 5 14 47 42
C 10 5 – 35 28 25
D 36 14 35 – 6 22
E 21 47 28 6 – 36
F 7 42 25 22 36 –
  1. Wende die Nearest-Neighbor-Heuristik mit Start in A an. Gib die Rundreise und ihre Länge an.
  2. Der Computer hat als optimale Rundreise A → C → B → D → E → F → A gefunden. Berechne ihre Länge.
  3. Berechne die Abweichung. Erkläre, an welcher Stelle die Heuristik „in die Falle läuft“.
  4. Wende Nearest Neighbor noch einmal an, diesmal mit Start in C. Was stellst du fest?

Deine Tabellen und Rechnungen:

Lösung vergleichen
  1. Start in A:
Schritt aktueller Ort noch nicht besucht (Entfernung) Wahl
1 A B 41, C 10, D 36, E 21, F 7 F (7 km)
2 F B 42, C 25, D 22, E 36 D (22 km)
3 D B 14, C 35, E 6 E (6 km)
4 E B 47, C 28 C (28 km)
5 C B 5 B (5 km)
6 B alle besucht zurück nach A (41 km)

Rundreise A → F → D → E → C → B → A, Länge 7+22+6+28+5+41=1097 + 22 + 6 + 28 + 5 + 41 = 109 km.

  1. Optimale Rundreise: 10+5+14+6+36+7=7810 + 5 + 14 + 6 + 36 + 7 = 78 km.

  2. Abweichung: 109−7878⋅100%=3178⋅100%≈39,7%\frac{109 - 78}{78} \cdot 100\,\% = \frac{31}{78} \cdot 100\,\% \approx 39{,}7\,\%. Die Falle schnappt am Ende zu: B wird als letzter Ort besucht, und die Rückfahrt von B nach A ist mit 41 km sehr lang. Die Heuristik hat am Anfang die kurzen Strecken zu F und D genommen und sich so den Weg über C und B „verbaut“, solange er noch günstig gewesen wäre.

  3. Start in C: C → B (5) → D (14) → E (6) → A (21) → F (7) → zurück nach C (25). Länge: 5+14+6+21+7+25=785 + 14 + 6 + 21 + 7 + 25 = 78 km. Mit Start in C ist die Heuristik also optimal! Diese Rundreise ist eine andere als die vom Computer angegebene, aber genauso kurz – es gibt hier zwei verschiedene optimale Rundreisen. Der Startort entscheidet bei dieser Instanz über 0 % oder fast 40 % Abweichung.

Instanz 7. Links: Nearest Neighbor mit Start in A (109 km). Rechts: eine optimale Rundreise (78 km). Gezeichnet sind nur die benutzten Kanten

3.6.5Auch die Rucksack-Heuristik auf dem Prüfstand

Dieselbe Bewertungsmethode funktioniert für jede Heuristik. Eine einfache Art, mehrere Probleminstanzen zu bekommen: Man nimmt dieselben Gegenstände, ändert aber die Tragkraft. Jede Tragkraft ergibt eine neue Probleminstanz.

Arbeitsauftrag 64: Greedy bei verschiedenen Tragkräften

Nimm die Gegenstände der Wanderung (Zelt 5 kg/60 €, Schlafsack 4 kg/40 €, Kocher 2 kg/30 €, Proviant 3 kg/25 €, Erste-Hilfe-Set 1 kg/20 €). Die sortierte Reihenfolge nach dem Wert-Gewicht-Verhältnis kennst du schon: Erste-Hilfe-Set, Kocher, Zelt, Schlafsack, Proviant.

  1. Wende die Greedy-Heuristik für die Tragkräfte 6 kg, 8 kg und 12 kg an. (Für 10 kg kennst du das Ergebnis schon.)
  2. Ein Computer hat mit Brute-Force die optimalen Werte berechnet. Trage die Abweichungen ein und berechne die durchschnittliche Abweichung.
  3. Beurteile kurz, wie gut die Greedy-Heuristik bei diesen Instanzen funktioniert.
Tragkraft optimaler Wert Greedy-Auswahl Greedy-Wert Abweichung
6 kg 80 €
8 kg 110 €
10 kg 120 € Erste-Hilfe-Set, Kocher, Zelt 110 €
12 kg 150 €

Durchschnitt und Beurteilung:

Lösung vergleichen
Tragkraft optimaler Wert Greedy-Auswahl Greedy-Wert Abweichung
6 kg 80 € Erste-Hilfe-Set, Kocher, Proviant 75 € 6,25 %
8 kg 110 € Erste-Hilfe-Set, Kocher, Zelt 110 € 0 %
10 kg 120 € Erste-Hilfe-Set, Kocher, Zelt 110 € 8,3 %
12 kg 150 € Erste-Hilfe-Set, Kocher, Zelt, Schlafsack 150 € 0 %

Bei 6 kg: Erste-Hilfe-Set und Kocher passen (zusammen 3 kg), das Zelt nicht (3+5=83 + 5 = 8), der Schlafsack nicht (3+4=73 + 4 = 7), der Proviant schon (3+3=63 + 3 = 6). Optimal wären Zelt und Erste-Hilfe-Set mit 80 €. Abweichung: 80−7580⋅100%=6,25%\frac{80 - 75}{80} \cdot 100\,\% = 6{,}25\,\%.

Bei 12 kg passt nach Erste-Hilfe-Set, Kocher und Zelt (8 kg) auch noch der Schlafsack (8+4=128 + 4 = 12). Der Proviant passt nicht mehr.

Durchschnittliche Abweichung: (6,25+0+8,33+0):4≈3,6(6{,}25 + 0 + 8{,}33 + 0) : 4 \approx 3{,}6 (in Prozent).

Beurteilung: Die Greedy-Heuristik schneidet bei diesen Instanzen gut ab: zweimal optimal, im Durchschnitt nur 3,6 % unter dem Optimum, im schlechtesten Fall 8,3 %. Allerdings sind es nur vier Instanzen mit denselben Gegenständen. Dass die Heuristik auch viel schlechter sein kann, zeigt das Gegenbeispiel aus dem Abschnitt über das Rucksackproblem (20 % Abweichung).

So kannst du es sagen

So formulierst du eine Bewertung in Fachsprache:

3.6.6Rückblick: das Kapitel im Überblick

Zum Abschluss lohnt sich ein Blick auf das ganze Kapitel. Eine Übersicht über alle Fachbegriffe mit Beispielen findest du im Rückblick am Ende des Kapitels. Wenn du bei einem Begriff unsicher bist, lies im passenden Abschnitt nach.

Arbeitsauftrag 65: Zusammenfassung des Kapitels

Beantworte in eigenen Worten. Die Fragen sind eine gute Vorbereitung auf einen Test.

  1. Was ist der Unterschied zwischen einem Problem und einer Probleminstanz?
  2. Wann liefert ein Brute-Force-Ansatz garantiert die optimale Lösung, und wo liegt sein Nachteil?
  3. Was zeichnet eine Greedy-Heuristik aus, und welches Risiko birgt sie?
  4. Nenne je ein Beispiel für ein Problem mit faktoriellem und eines mit exponentiellem Brute-Force-Aufwand.

Deine Antworten:

Lösung vergleichen
  1. Ein Problem ist eine allgemeine Fragestellung mit Leerstellen, zum Beispiel „Finde die kürzeste Rundreise durch beliebige Orte“. Eine Probleminstanz ist ein konkreter Fall dieses Problems, bei dem alle Werte feststehen, zum Beispiel die vier Orte A, B, C, D mit ihren Entfernungen. Zu einem Problem gibt es viele Instanzen.
  2. Brute-Force liefert garantiert die optimale Lösung, weil er alle zulässigen Lösungen erzeugt und bewertet – eine bessere kann es also nicht geben. (Voraussetzung: Die Anzahl der Lösungen ist endlich, und man kann sie alle systematisch erzeugen.) Der Nachteil ist der Aufwand: Die Anzahl der Möglichkeiten wächst so schnell, dass Brute-Force schon bei mittelgroßen Instanzen (etwa 20 Orte) viel zu lange dauert.
  3. Eine Greedy-Heuristik baut die Lösung Schritt für Schritt auf und wählt in jedem Schritt das, was im Moment am besten aussieht. Sie ist schnell und einfach. Das Risiko: Weil sie nicht vorausschaut und Entscheidungen nie zurücknimmt, kann sie in eine Sackgasse geraten und eine Lösung liefern, die deutlich schlechter ist als die optimale (z. B. 39,7 % bei Instanz 7).
  4. Faktoriell: das Problem des Handlungsreisenden, (n−1)!(n-1)! Rundreisen bei nn Orten. Exponentiell: das Rucksackproblem, 2n2^n Teilmengen bei nn Gegenständen.

3.6.7Ausblick: weitere Probleme und warum Optimieren nachhaltig ist

Das Problem des Handlungsreisenden und das Rucksackproblem sind nur zwei Beispiele. Mit denselben Werkzeugen untersucht man viele weitere Probleme:

Optimieren spart nicht nur Zeit, sondern auch Ressourcen. Kürzere Touren von Paketdiensten und Müllfahrzeugen sparen Kraftstoff und vermeiden CO₂-Ausstoß. Gut gepackte Lieferwagen und Container bedeuten weniger Fahrten. Ein guter Plan für Busse oder Maschinen spart Energie. Auch die Rechenzeit selbst verbraucht Strom: Eine Heuristik, die in Sekunden eine gute Lösung findet, kann sinnvoller sein als eine Rechnung, die tagelang einen Großrechner beschäftigt. Optimierungsprobleme sind deshalb ein wichtiges Werkzeug für nachhaltiges Ressourcenmanagement.

Arbeitsauftrag 66 (Zusatz): Kisten packen mit First Fit

Kisten tragen höchstens 10 kg. Fünf Pakete wiegen 6 kg, 5 kg, 4 kg, 3 kg und 2 kg. Lege jedes Paket der Reihe nach in die erste Kiste, in die es noch passt. Passt es in keine, öffne eine neue Kiste.

  1. Wende First Fit in der Reihenfolge 6, 5, 4, 3, 2 an. Wie viele Kisten brauchst du?
  2. Wende First Fit in der Reihenfolge 2, 3, 4, 5, 6 an. Wie viele Kisten brauchst du jetzt?
  3. Wie viele Kisten braucht man mindestens? Begründe. Was folgt daraus für die Heuristik?

Deine Kisten und deine Begründung:

Lösung vergleichen
  1. Reihenfolge 6, 5, 4, 3, 2: 6 kg → Kiste 1. 5 kg passt nicht in Kiste 1 (6+5=116 + 5 = 11) → Kiste 2. 4 kg → Kiste 1 (6+4=106 + 4 = 10). 3 kg → Kiste 2 (5+3=85 + 3 = 8). 2 kg passt nicht mehr in Kiste 1, aber in Kiste 2 (8+2=108 + 2 = 10). Ergebnis: 2 Kisten (Kiste 1: 6 + 4, Kiste 2: 5 + 3 + 2).
  2. Reihenfolge 2, 3, 4, 5, 6: 2, 3 und 4 kg kommen in Kiste 1 (9 kg). 5 kg passt nicht (9+5=149 + 5 = 14) → Kiste 2. 6 kg passt weder in Kiste 1 (9+6=159 + 6 = 15) noch in Kiste 2 (5+6=115 + 6 = 11) → Kiste 3. Ergebnis: 3 Kisten.
  3. Alle Pakete wiegen zusammen 6+5+4+3+2=206 + 5 + 4 + 3 + 2 = 20 kg. Eine Kiste trägt 10 kg, also braucht man mindestens 2 Kisten. Mit der ersten Reihenfolge ist First Fit optimal, mit der zweiten nicht (50 % mehr Kisten). Das Ergebnis der Heuristik hängt also von der Reihenfolge ab. Eine bewährte Verbesserung: die Pakete vorher absteigend nach Gewicht sortieren – wie beim Rucksack nach dem Wert-Gewicht-Verhältnis.

3.6.8Weitere Übungen

Hier kannst du das Gelernte weiter üben. Die Punkte im Titel zeigen, wie schwer eine Aufgabe ist: ●○○ leicht, ●●○ mittel, ●●● knifflig. Fang mit den leichten an.

Arbeitsauftrag 67: Abweichungen berechnen ●○○

Eine Heuristik für das Problem des Handlungsreisenden wurde an fünf Probleminstanzen getestet. Berechne jeweils die prozentuale Abweichung vom Optimum. Runde auf eine Stelle nach dem Komma.

Instanz Länge der Heuristik optimale Länge Abweichung
1 36 km 30 km
2 44 km 40 km
3 25 km 20 km
4 58 km 58 km
5 52 km 48 km
Lösung vergleichen
Instanz Länge der Heuristik optimale Länge Abweichung
1 36 km 30 km 630⋅100%=20,0%\frac{6}{30} \cdot 100\,\% = 20{,}0\,\%
2 44 km 40 km 440⋅100%=10,0%\frac{4}{40} \cdot 100\,\% = 10{,}0\,\%
3 25 km 20 km 520⋅100%=25,0%\frac{5}{20} \cdot 100\,\% = 25{,}0\,\%
4 58 km 58 km 058⋅100%=0,0%\frac{0}{58} \cdot 100\,\% = 0{,}0\,\%
5 52 km 48 km 448⋅100%≈8,3%\frac{4}{48} \cdot 100\,\% \approx 8{,}3\,\%

Bei Instanz 4 hat die Heuristik die optimale Lösung getroffen. Denk daran: Geteilt wird immer durch die optimale Länge.

Arbeitsauftrag 68: Durchschnitt und schlechtester Fall ●○○

Eine Heuristik wurde an fünf Instanzen getestet. Die Abweichungen vom Optimum waren: 0 %, 5 %, 12 %, 0 %, 3 %.

  1. Berechne die durchschnittliche Abweichung.
  2. Nenne den schlechtesten Fall.
  3. Bei wie vielen Instanzen war die Heuristik optimal?

Deine Antworten:

Lösung vergleichen
  1. (0+5+12+0+3):5=20:5=4(0 + 5 + 12 + 0 + 3) : 5 = 20 : 5 = 4. Die durchschnittliche Abweichung beträgt 4 %.
  2. Der schlechteste Fall ist eine Abweichung von 12 %.
  3. Bei 2 der 5 Instanzen (Abweichung 0 %) war die Heuristik optimal.
Arbeitsauftrag 69: Richtig bewertet? ●○○

Entscheide, ob die Aussage richtig oder falsch ist. Begründe kurz.

Aussage richtig oder falsch? Begründung
Um eine Heuristik zu bewerten, vergleicht man ihre Lösung mit der optimalen Lösung.
Hat eine Heuristik bei einer Instanz 0 % Abweichung, ist sie immer optimal.
Man sollte eine Heuristik an möglichst unterschiedlichen Instanzen testen.
Eine Abweichung von 0 % bedeutet, dass die Heuristik die optimale Lösung gefunden hat.
Die Abweichung berechnet man, indem man durch die Länge der Heuristik teilt.
Lösung vergleichen
Aussage richtig oder falsch? Begründung
Vergleich mit der optimalen Lösung richtig Nur so weiß man, wie weit die Heuristik vom Bestmöglichen entfernt ist.
0 % bei einer Instanz heißt: immer optimal falsch Bei einer anderen Instanz kann die Heuristik deutlich schlechter sein. Ein einzelner Test reicht nicht.
möglichst unterschiedliche Instanzen testen richtig Sonst hat man vielleicht nur Instanzen erwischt, bei denen die Heuristik zufällig gut ist.
0 % bedeutet optimal (bei dieser Instanz) richtig Die Lösung der Heuristik ist dann genauso gut wie das Optimum.
durch die Länge der Heuristik teilen falsch Man teilt durch die optimale Länge.
Arbeitsauftrag 70: Zwei Navi-Apps im Test ●●○

Zwei Apps berechnen Lieferrouten mit unterschiedlichen Heuristiken. Beide wurden an denselben fünf Probleminstanzen getestet. Die optimalen Längen wurden mit Brute-Force bestimmt.

Instanz optimal App X App Y
1 50 km 55 km 50 km
2 40 km 40 km 40 km
3 80 km 84 km 80 km
4 20 km 21 km 20 km
5 100 km 110 km 130 km
  1. Berechne für beide Apps die Abweichung bei jeder Instanz.
  2. Berechne für beide Apps die durchschnittliche Abweichung und nenne den schlechtesten Fall.
  3. Welche App würdest du einer Lieferfirma empfehlen? Begründe.

Deine Rechnungen und deine Empfehlung:

Lösung vergleichen
  1. Abweichungen:
Instanz App X App Y
1 550⋅100%=10%\frac{5}{50} \cdot 100\,\% = 10\,\% 0 %
2 0 % 0 %
3 480⋅100%=5%\frac{4}{80} \cdot 100\,\% = 5\,\% 0 %
4 120⋅100%=5%\frac{1}{20} \cdot 100\,\% = 5\,\% 0 %
5 10100⋅100%=10%\frac{10}{100} \cdot 100\,\% = 10\,\% 30100⋅100%=30%\frac{30}{100} \cdot 100\,\% = 30\,\%
  1. App X: Durchschnitt (10+0+5+5+10):5=6%(10 + 0 + 5 + 5 + 10) : 5 = 6\,\%, schlechtester Fall 10 %. App Y: Durchschnitt (0+0+0+0+30):5=6%(0 + 0 + 0 + 0 + 30) : 5 = 6\,\%, schlechtester Fall 30 %.
  2. Beide Apps haben denselben Durchschnitt. Der Durchschnitt allein entscheidet also nicht. App Y ist meistens optimal, liegt aber einmal sehr weit daneben. App X ist nur bei Instanz 2 optimal, aber nie mehr als 10 % schlechter. Eine Lieferfirma, die jeden Tag fährt, wird eher App X wählen, weil sie verlässlicher ist. Eine andere begründete Antwort ist auch möglich, zum Beispiel App Y, wenn große Instanzen wie Nr. 5 selten vorkommen.
Arbeitsauftrag 71: Die Rucksack-Heuristik bewerten ●●○

Die Greedy-Heuristik für das Rucksackproblem wurde an vier Instanzen aus diesem Kapitel getestet: an der Wanderung, an Bens Flohmarkt (Auftrag Greedy am Flohmarkt) und an zwei Instanzen aus dem Auftrag Gegenbeispiel oder nicht?. Beim Rucksack ist ein größerer Wert besser.

Instanz optimaler Wert Greedy-Wert Abweichung
Wanderung 120 € 110 €
Flohmarkt 68 € 61 €
Noahs Gegenbeispiel 25 € 20 €
Leas Gegenbeispiel 20 € 18 €
  1. Berechne die Abweichungen und ihren Durchschnitt. Runde auf eine Stelle nach dem Komma.
  2. Mira sagt: „Die Greedy-Heuristik ist im Durchschnitt 12 % schlechter als das Optimum.“ Beurteile diese Aussage. Achte darauf, wie die vier Instanzen ausgewählt wurden.

Deine Rechnungen und deine Beurteilung:

Lösung vergleichen
  1. Abweichungen (optimaler Wert minus Greedy-Wert, geteilt durch den optimalen Wert):
Instanz optimaler Wert Greedy-Wert Abweichung
Wanderung 120 € 110 € 10120⋅100%≈8,3%\frac{10}{120} \cdot 100\,\% \approx 8{,}3\,\%
Flohmarkt 68 € 61 € 768⋅100%≈10,3%\frac{7}{68} \cdot 100\,\% \approx 10{,}3\,\%
Noahs Gegenbeispiel 25 € 20 € 525⋅100%=20,0%\frac{5}{25} \cdot 100\,\% = 20{,}0\,\%
Leas Gegenbeispiel 20 € 18 € 220⋅100%=10,0%\frac{2}{20} \cdot 100\,\% = 10{,}0\,\%

Durchschnitt: (8,3+10,3+20,0+10,0):4≈12,2%(8{,}3 + 10{,}3 + 20{,}0 + 10{,}0) : 4 \approx 12{,}2\,\%.

  1. Die Rechnung stimmt, die Aussage ist aber nicht aussagekräftig. Alle vier Instanzen sind Fälle, bei denen die Heuristik versagt – zwei davon wurden sogar extra als Gegenbeispiele gebaut. Instanzen, bei denen Greedy optimal ist (zum Beispiel der Tagesausflug), fehlen. Für eine verlässliche Bewertung braucht man viele, möglichst unterschiedliche Instanzen, die nicht danach ausgesucht sind, wie gut die Heuristik abschneidet.
Arbeitsauftrag 72: Ein Test von Hand ●●●

Teste die Nearest-Neighbor-Heuristik selbst an drei Probleminstanzen mit je vier Orten A, B, C, D (Entfernungen in km).

Instanz 1 A B C D
A – 10 4 6
B 10 – 8 4
C 4 8 – 10
D 6 4 10 –
Instanz 2 A B C D
A – 4 12 8
B 4 – 9 8
C 12 9 – 9
D 8 8 9 –
Instanz 3 A B C D
A – 4 2 9
B 4 – 6 7
C 2 6 – 7
D 9 7 7 –
  1. Wende bei jeder Instanz Nearest Neighbor mit Start in A an.
  2. Bestimme bei jeder Instanz mit Brute-Force die optimale Länge. Wegen der Symmetrie genügen die drei Rundreisen A → B → C → D → A, A → B → D → C → A und A → C → B → D → A.
  3. Berechne die Abweichungen, ihren Durchschnitt und nenne den schlechtesten Fall.
  4. Beurteile: Reichen drei Instanzen aus, um die Heuristik zu bewerten?

Deine Rechnungen und deine Beurteilung:

Lösung vergleichen
  1. Nearest Neighbor mit Start in A:
    • Instanz 1: A → C (4), C → B (8, denn D ist 10), B → D (4), zurück D → A (6). Länge 4+8+4+6=224 + 8 + 4 + 6 = 22 km.
    • Instanz 2: A → B (4), B → D (8, denn C ist 9), D → C (9), zurück C → A (12). Länge 4+8+9+12=334 + 8 + 9 + 12 = 33 km.
    • Instanz 3: A → C (2), C → B (6, denn D ist 7), B → D (7), zurück D → A (9). Länge 2+6+7+9=242 + 6 + 7 + 9 = 24 km.
  2. Brute-Force:
Rundreise Instanz 1 Instanz 2 Instanz 3
A → B → C → D → A 10+8+10+6=3410 + 8 + 10 + 6 = 34 4+9+9+8=𝟑𝟎4 + 9 + 9 + 8 = \mathbf{30} 4+6+7+9=264 + 6 + 7 + 9 = 26
A → B → D → C → A 10+4+10+4=2810 + 4 + 10 + 4 = 28 4+8+9+12=334 + 8 + 9 + 12 = 33 4+7+7+2=𝟐𝟎4 + 7 + 7 + 2 = \mathbf{20}
A → C → B → D → A 4+8+4+6=𝟐𝟐4 + 8 + 4 + 6 = \mathbf{22} 12+9+8+8=3712 + 9 + 8 + 8 = 37 2+6+7+9=242 + 6 + 7 + 9 = 24
  1. Abweichungen:
    • Instanz 1: 22−2222⋅100%=0%\frac{22 - 22}{22} \cdot 100\,\% = 0\,\%.
    • Instanz 2: 33−3030⋅100%=10%\frac{33 - 30}{30} \cdot 100\,\% = 10\,\%.
    • Instanz 3: 24−2020⋅100%=20%\frac{24 - 20}{20} \cdot 100\,\% = 20\,\%.
    Durchschnitt: (0+10+20):3=10%(0 + 10 + 20) : 3 = 10\,\%. Schlechtester Fall: 20 % (Instanz 3).
  2. Drei Instanzen reichen nicht für eine verlässliche Bewertung. Schon diese drei zeigen, wie unterschiedlich die Ergebnisse sein können: von 0 % bis 20 %. Mit weiteren Instanzen könnte der Durchschnitt deutlich anders ausfallen. Außerdem haben alle Instanzen nur vier Orte. Für eine sichere Aussage testet man viel mehr und auch größere Instanzen – das erledigt man am besten mit dem Computer.

3.6.9Das Wichtigste in Kürze

Selbstcheck

3.7Kapitel 3 kompakt: der Lernzettel

Diesen Abschnitt als PDF (S. 108–110)

Leitidee

Dieser Lernzettel fasst das Kapitel auf wenigen Seiten zusammen. Nutze ihn zum Wiederholen vor einem Test. Ausführliche Erklärungen, Beispiele und Übungen findest du in den einzelnen Abschnitten.

3.7.1Problem, Probleminstanz, Darstellung (Abschnitt 3.1)

A B C D
A – 10 15 20
B 10 – 35 25
C 15 35 – 30
D 20 25 30 –

Lesen: Zeile B, Spalte D → 25 km. Jede Zahl steht zweimal (symmetrisch).

Typische Fehler: die gezeichnete Länge einer Kante statt des Kantengewichts verwenden; Symmetrie annehmen, obwohl Hin- und Rückweg verschieden sind (z. B. Fahrzeiten bergauf und bergab).

3.7.2Optimale Lösung und Brute-Force (Abschnitt 3.2)

Typische Fehler: Rückfahrt vergessen; eine Rundreise doppelt zählen, eine andere vergessen; bei Brute-Force zu früh aufhören; (n−1)!(n-1)! ohne Klammer rechnen.

3.7.3Heuristiken und Greedy (Abschnitt 3.3)

Schritt aktueller Ort noch nicht besucht Wahl
1 A B 10, C 15, D 20 B (10)
2 B C 35, D 25 D (25)
3 D C 30 C (30)
4 C – zurück nach A (15)

Ergebnis: 80 km, hier optimal. Mit Start in D: 95 km, nicht optimal. Das Ergebnis kann vom Startort abhängen.

Typische Fehler: einen schon besuchten Ort wählen; „vorausschauen“ (das macht Nearest Neighbor nicht); durch die Länge der Heuristik statt durch das Optimum teilen.

3.7.4Das Rucksackproblem (Abschnitt 3.4)

Typische Fehler: Gewicht : Wert statt Wert : Gewicht; beim ersten Gegenstand, der nicht passt, aufhören; nach dem Wert statt nach dem Verhältnis sortieren; die leere Teilmenge beim Zählen vergessen.

3.7.5Aufwand (Abschnitt 3.5)

nn 4 5 6 8 10 12 20
(n−1)!(n-1)! 6 24 120 5 040 362 880 39 916 800 ≈1,2⋅1017\approx 1{,}2 \cdot 10^{17}
2n2^n 16 32 64 256 1 024 4 096 1 048 576

Typische Fehler: faktoriell und exponentiell verwechseln (Rundreisen → Fakultät, Teilmengen → Zweierpotenz); bei Zeitabschätzungen die Einheiten (Sekunden, Minuten, Tage) durcheinanderbringen.

3.7.6Heuristiken bewerten (Abschnitt 3.6)

Typische Fehler: nur den Durchschnitt nennen (ein großer Ausreißer geht unter); nur Instanzen testen, bei denen die Heuristik gut oder nur schlecht abschneidet.

So kannst du es sagen

3.8Rückblick auf Kapitel 3

Diesen Abschnitt als PDF (S. 111–112)

Leitidee

Am Ende des Kapitels lohnt sich ein Blick zurück: Welche Fachbegriffe kennst du jetzt? Was kannst du schon sicher, was solltest du noch einmal üben?

3.8.1Die Basisbegriffe

Diese Begriffe solltest du mit eigenen Worten erklären und an einem Beispiel aus dem Kapitel zeigen können.

Begriff Bedeutung Beispiel
Problem allgemeine Fragestellung mit Leerstellen kürzeste Rundreise durch beliebige Orte
Probleminstanz konkreter Fall mit festen Werten die vier Orte A, B, C, D mit ihrer Entfernungstabelle
abstrahierte Darstellung nur das Wichtige, als Tabelle, Graph oder Liste Graph mit Knoten, Kanten, Kantengewichten
zulässige Lösung erfüllt alle Bedingungen jede Rundreise; jede Auswahl bis 10 kg
optimale Lösung beste zulässige Lösung bezüglich eines Kriteriums A → B → D → C → A (80 km); Zelt, Schlafsack, Erste-Hilfe-Set (120 €)
Brute-Force-Ansatz alle zulässigen Lösungen erzeugen, bewerten und die beste auswählen alle (n−1)!(n-1)! Rundreisen; alle 2n2^n Teilmengen
Heuristik schnelle Lösungsstrategie, liefert meist eine gute, aber nicht garantiert optimale Lösung Faustregel „immer zum nächsten Ort“
Greedy-Heuristik wählt in jedem Schritt das, was im Moment am besten aussieht Nearest Neighbor; Wert-Gewicht-Verhältnis
Aufwand Anzahl der Möglichkeiten oder Rechenzeit faktoriell beim Handlungsreisenden, exponentiell beim Rucksack
Bewertung Abweichung vom Optimum über viele Instanzen Durchschnitt 7,7 %, schlechtester Fall 39,7 %

3.8.2Kompetenz-Check

Ich kann … sicher teilweise noch nicht
zwischen einem Problem und einer Probleminstanz unterscheiden.
kleine Probleminstanzen als Tabelle, Graph oder Liste darstellen und untersuchen.
strukturelle Eigenschaften eines Problems erkennen (z. B. Symmetrie).
definieren, was eine optimale Lösung ist.
einen Brute-Force-Ansatz beschreiben und an kleinen Instanzen durchführen.
den Begriff Heuristik definieren.
eine Heuristik beschreiben und auf Probleminstanzen anwenden.
den Aufwand verschiedener Lösungsansätze vergleichen.
beurteilen, wie gut eine Heuristik bei verschiedenen Instanzen funktioniert.
Informatik 10 | Informatisches ProblemlösenDruckfassung (PDF)