f.fritze

Stell dir vor, du planst eine Reise durch mehrere Städte und möchtest die kürzeste Route finden, um jede Stadt genau einmal zu besuchen. Was im ersten Moment wie eine einfache Aufgabe klingt, ist in Wahrheit eine der berühmtesten Knobelaufgaben der Informatik: das Travelling Salesman Problem.

Aber keine Sorge, du musst kein Mathe-Genie sein, um dich dieser legendären Herausforderung zu stellen. Im Gegenteil! Wir schnappen uns unsere bunten Blöcke in Scratch und zeigen, wie man dieses komplexe Problem spielerisch und kreativ lösen kann.

In diesem Beitrag nehmen wir die Challenge an und tüfteln gemeinsam an einer Lösung. Bist du bereit, dem Handlungsreisenden den effizientesten Weg zu weisen und dabei tief in die Welt der Algorithmen einzutauchen? Dann lass uns loslegen

Das Problem verstehen – ganz ohne Algorithmus

Bevor wir uns an eine automatische Lösung wagen, wollen wir das Problem erst einmal selbst in die Hand nehmen. Dafür habe ich ein kleines Scratch-Projekt vorbereitet, in dem du die Challenge manuell lösen kannst.

Die Aufgabe ist simpel: Eine Eule muss alle Mäuse auf dem Bildschirm fressen. Sie startet bei der ersten Maus (mit der Nummer 1) und muss auch dorthin zurückkehren.

So funktioniert’s:

1. Starte das Projekt mit der grünen Flagge.
2. Klicke nacheinander auf die Mäuse in der Reihenfolge, die du für die kürzeste hältst.
3. Die Eule folgt deiner gewählten Route, und die zurückgelegte Gesamtstrecke wird berechnet und angezeigt.

Probier es doch gleich mal aus!

zeige den

Code

Du wirst schnell merken: Schon bei wenigen Mäusen ist es gar nicht so einfach, den kürzesten Weg zu finden. Aber wie könnte die Eule das Problem automatisch lösen? Genau hier kommst du als Tüftler ins Spiel! Versuch doch mal, einen eigenen Algorithmus zu implementieren. Als Startpunkt für deine Experimente kannst du den Block Wenn diese Figur angeklickt wird bei der Eule nutzen. Ein Klick auf die Eule startet dann deinen Code.

Der Holzhammer-Ansatz: Die Brute-Force-Methode

Nachdem wir uns manuell versucht haben, wollen wir der Eule nun ihre erste eigene Strategie beibringen. Wir starten mit der direktesten, aber auch stursten Methode, die es gibt: Brute Force (zu Deutsch: rohe Gewalt).

Die Idee: Einfach alles ausprobieren!

Die Logik hinter Brute Force ist bestechend einfach: Wir lassen den Computer systematisch jede einzelne mögliche Route durchgehen und merken uns am Ende einfach die kürzeste.

Stell es dir wie ein Zahlenschloss vor: Anstatt clever zu überlegen, probierst du einfach stur bei 0-0-0 an und gehst jede einzelne Kombination durch, bis das Schloss aufspringt. Genau das machen wir hier auch:

1. Der Algorithmus erzeugt und testet nach und nach jede mögliche Reihenfolge der Mäuse. Es wird also keine riesige Liste im Voraus erstellt, sondern eine Kombination nach der anderen abgearbeitet.
2. Für jede einzelne Reihenfolge wird die Gesamtdistanz der Reise berechnet.
3. Wir führen eine „Bestenliste“ und speichern immer nur die kürzeste bisher gefundene Strecke und die dazugehörige Route.

Eine kleine Optimierung gönnen wir uns aber: Die Route 1 -> 2 -> 3 -> 4 -> 1 ist exakt genauso lang wie die umgekehrte Route 1 -> 4 -> 3 -> 2 -> 1. Wir können also die Hälfte aller Fälle ignorieren und sparen damit Rechenzeit.

Brute Force in Aktion mit Scratch

Genug der Theorie! In diesem Scratch-Projekt ist der Brute-Force-Algorithmus implementiert. Klicke nach dem Start auf die Eule, um die automatische Suche zu beginnen.

zeige den

Code

Du wirst feststellen, dass die Eule nicht sofort losfliegt. Stattdessen läuft im Hintergrund die Berechnung. Um Zeit zu sparen, werden die unzähligen Wege nicht visualisiert. Achte stattdessen auf den Sekundenzähler: Er zeigt dir live, wie lange der Computer braucht, um alle Optionen durchzurechnen.

Sobald der Algorithmus fertig ist, stoppt der Zähler, und die Eule fliegt nur noch die eine, absolut kürzeste Route ab. Bei den wenigen Mäusen im Beispiel ist die Berechnung in einem Wimpernschlag erledigt. Aber was passiert, wenn wir mehr Ziele hinzufügen?

Die Grenzen der rohen Gewalt

Brute Force hat einen riesigen Vorteil: Die Methode garantiert, dass wir immer die absolut kürzeste Route finden. Der Nachteil ist jedoch gewaltig und macht den Ansatz für die Praxis oft unbrauchbar: die sogenannte kombinatorische Explosion.

Schauen wir uns das an einem Rechenbeispiel an:

• Bei 5 Mäusen gibt es (5-1)! / 2 = 12 einzigartige Routen. Ein Klacks für jeden Rechner.
• Bei 10 Mäusen sind es schon (10-1)! / 2 = 181.440 Routen. Immer noch machbar, aber der Sekundenzähler in Scratch wird schon deutlich zucken.
• Bei 15 Mäusen explodiert die Zahl auf (15-1)! / 2 = 43.589.145.600 – also über 43,5 Milliarden Routen!

Selbst wenn ein moderner Rechner eine Million Routen pro Sekunde prüfen könnte, würde er für nur 15 Mäuse bereits über 12 Stunden benötigen. Bei 20 Mäusen wären wir schon bei einer Rechenzeit von über 1.900 Jahren.

Fazit: Brute Force ist ein treuer, aber extrem langsamer Arbeitsochse. Für reale Anwendungen (wie die Routenplanung eines Paketdienstes mit hunderten Zielen) ist diese Methode absolut ungeeignet. Wir brauchen also cleverere Ansätze! Und genau die schauen wir uns im nächsten Abschnitt an.

Cleverer statt stärker: Der Weg der Heuristiken

Wir haben gesehen: Die Brute-Force-Methode ist zwar gründlich, aber für alles, was über eine Handvoll Ziele hinausgeht, hoffnungslos langsam. In der echten Welt können wir nicht Jahre auf eine Routenplanung warten. Wir brauchen also eine Abkürzung. Und genau hier kommen Heuristiken ins Spiel.

Eine Heuristik ist im Grunde eine schlaue Faustregel oder eine Abkürzung, die uns hilft, eine gute Lösung in kurzer Zeit zu finden. Der entscheidende Punkt ist: Eine Heuristik garantiert nicht die absolut beste, perfekte, optimale Lösung. Stattdessen liefert sie uns eine Lösung, die „gut genug“ für die Praxis ist – und das blitzschnell.

Wir opfern also die Garantie der Perfektion für einen gewaltigen Geschwindigkeitsvorteil.

Der Gierige Algorithmus (Greedy Algorithm)

Die wohl einfachste und bekannteste Heuristik ist der Gierige Algorithmus. Der Name ist Programm, denn seine Strategie ist extrem kurzsichtig und, nun ja, gierig.

Die Idee: Wähle von deinem aktuellen Standpunkt aus immer die Maus, die am dichtesten dran ist und die du noch nicht besucht hast.

Stell es dir wie am Buffet vor: Du nimmst dir nicht das, was strategisch am besten zu deinem gesamten Menü passt, sondern einfach das, was direkt vor deiner Nase steht und am leckersten aussieht. Du wiederholst das, bis dein Teller voll ist.

Der Greedy-Ansatz in Scratch

Auch diesen Ansatz habe ich in Scratch umgesetzt. Klicke wieder auf die Eule, um den Algorithmus zu starten.

zeige den

Code

Du wirst sofort einen riesigen Unterschied zur Brute-Force-Methode bemerken: Die Berechnung ist sofort abgeschlossen. Die Eule fliegt ohne jede Verzögerung los. Aber ist dieser Weg auch der beste? Vergleiche die gefundene Distanz mal mit der perfekten Lösung aus dem Brute-Force-Beispiel.

Die Tücke der Gier

Der Greedy-Algorithmus ist zwar pfeilschnell, aber seine Kurzsichtigkeit kann ihm zum Verhängnis werden. Eine lokal gute Entscheidung (der nächste Schritt ist kurz) kann global zu einer schlechten Gesamtlösung führen. Wenn die Eule zum Beispiel einer nahen Maus in eine „Sackgasse“ folgt, muss sie von dort aus einen sehr weiten Weg zur nächsten Maus zurücklegen – ein Umweg, den ein klügerer Algorithmus vermieden hätte.

Fazit: Der Greedy-Algorithmus ist ein fantastischer Einstieg, um schnell eine brauchbare Route zu finden, aber optimal ist sie selten.

Ein Ausblick: Was gibt es noch für schlaue Füchse?

Die Welt der Heuristiken ist riesig und faszinierend. Der Greedy-Ansatz ist nur der Anfang. Hier sind ein paar weitere, oft genutzte Verfahren, die noch bessere Ergebnisse liefern:

• 2-Opt-Heuristik: Man startet mit einer beliebigen Route (z.B. der vom Greedy-Algorithmus) und versucht dann systematisch, die Route zu verbessern, indem man immer zwei Kanten „über Kreuz“ legt und schaut, ob der Weg dadurch kürzer wird.

• Simulated Annealing („Simulierte Abkühlung“): Ein spannender Ansatz, der aus der Metallurgie kommt. Der Algorithmus erlaubt am Anfang auch mal „schlechtere“ Züge, um nicht in einer lokalen Sackgasse stecken zu bleiben. Mit der Zeit wird er „kälter“ und akzeptiert nur noch Verbesserungen.
• Ameisenalgorithmen (Ant Colony Optimization): Hierbei wird das Verhalten von Ameisen simuliert, die auf der Suche nach Futter Duftspuren (Pheromone) hinterlassen. Routen, die von vielen „Ameisen“ genutzt werden, bekommen eine stärkere Duftspur und werden so wahrscheinlicher für die nächste Ameise.

Vielleicht schauen wir uns einen dieser „schicken“ Algorithmen ja in einem zukünftigen Beitrag genauer an. Fürs Erste haben wir aber gesehen, dass es oft cleverer ist, eine gute Abkürzung zu nehmen, als stur jeden denkbaren Weg auszuprobieren.

NP-vollständig: Die Königsklasse der schweren Probleme

Warum ist dieses Problem, das so einfach klingt, eine der härtesten Nüsse, die die Informatik zu knacken hat? Die Antwort liegt in seiner Komplexitätsklasse: Das Travelling Salesman Problem ist NP-vollständig.

Aber was bedeutet das? Lass es uns einfach aufschlüsseln:

1. NP (Nichtdeterministisch-polynomiell): Das klingt kompliziert, meint aber etwas Simples: Wenn dir jemand eine Lösung vorschlägt (z.B. „Hier, nimm diese Route!“), kannst du sehr schnell überprüfen, ob die Lösung gültig ist und eine bestimmte Länge nicht überschreitet. Das Nachrechnen einer gegebenen Route ist also einfach.
2. Vollständig: Das ist der entscheidende Teil. NP-vollständige Probleme sind die „Endgegner“ in der Welt der NP-Probleme. Sie sind die allerschwersten unter ihnen. Das Besondere ist: Sie sind alle miteinander verwandt. Wenn jemand einen schnellen Algorithmus finden würde, um nur ein einziges dieser Probleme (wie das TSP) effizient zu lösen, könnte man mit diesem Trick alle anderen tausenden NP-vollständigen Probleme ebenfalls schnell lösen. Das wäre eine wissenschaftliche Sensation und würde die Welt verändern (und dem Entdecker ein Preisgeld von 1 Million Dollar einbringen).

Was heißt das für unsere Eule?

Es bedeutet, dass es bis heute keinen bekannten Algorithmus gibt, der garantiert die beste Lösung in einer realistischen Zeit findet, sobald die Anzahl der Mäuse wächst. Die Rechenzeit explodiert – genau das haben wir bei der Brute-Force-Methode gesehen.

Deshalb sind wir gezwungen, auf clevere Tricks und Näherungslösungen (Heuristiken) auszuweichen, anstatt auf die perfekte, aber unerreichbare Lösung zu warten.

Das große Finale: Dein eigenes Algorithmen-Labor

Theorie ist gut, aber selbst ausprobieren ist besser! Nachdem wir uns nun verschiedene Lösungsansätze angesehen haben, ist es an der Zeit, dass du selbst zum Forscher wirst. Dafür habe ich alle Ideen in einem finalen Scratch-Projekt zusammengefasst, einer Art Algorithmen-Spielwiese.

zeige den

Code

In diesem Labor hast du die volle Kontrolle und kannst die Algorithmen gegeneinander antreten lassen.

Das ist neu:

• Wähle deinen Algorithmus: Über einen Button am unteren Rand kannst du entscheiden, welche Methode die Eule nutzen soll: die manuelle Steuerung, den schnellen Greedy-Algorithmus oder die langsame, aber perfekte Brute-Force-Methode.
• Werde zum Level-Designer: Das Beste zum Schluss: Du bist nicht mehr an meine Vorgaben gebunden! Klicke auf den „draw mice“-Button und platziere die Mäuse mit einem Klick genau dort, wo du sie haben möchtest.
• Vergleiche die Routen: Die Pfade der verschiedenen Algorithmen bleiben sichtbar, sodass du die Effizienz direkt vergleichen kannst. Mit „clean“ schaffst du wieder Ordnung.

Deine Mission, falls du sie annimmst

Dieses Labor ist perfekt, um ein Gefühl für die Stärken und Schwächen der Algorithmen zu bekommen. Hier sind ein paar Ideen für deine ersten Experimente:

1. Die Greedy-Falle: Kannst du eine Anordnung von Mäusen zeichnen, bei der der Greedy-Algorithmus eine sichtlich schlechtere Route wählt als die Brute-Force-Methode? (Tipp: Versuche, die Eule mit einer nahen Maus in eine „Sackgasse“ zu locken).
2. Der Idealfall: Finde eine Anordnung, bei der der Greedy-Algorithmus zufällig die perfekte Lösung findet. Wie sieht eine solche Anordnung aus?
3. Die Brute-Force-Grenze: Wie viele Mäuse kannst du platzieren, bevor die Rechenzeit der Brute-Force-Methode spürbar ansteigt? Finde den Punkt, an dem du dir denkst: „Okay, das dauert mir jetzt zu lange.“

Ich bin gespannt, was du herausfindest!

Am Ende zeigt das Travelling Salesman Problem wunderschön, dass es in der Informatik oft nicht darum geht, stur die eine, perfekte Antwort zu finden. Viel wichtiger ist es, das Problem zu verstehen und dann das richtige, clevere Werkzeug für die jeweilige Aufgabe zu wählen. Manchmal ist „gut genug“ eben unendlich viel besser als „perfekt, aber in tausend Jahren“.