Türchen 4

4. Dezember: Kinder-Special

Mit dem heutigen Spiel können Sie zusammen mit Ihrem Kind spielerisch etwas über strategische Problemlösungen und Optimierung lernen – ein Prinzip der Informatik, das sich ganz ohne Computer verstehen lässt. Wir wünschen Ihnen viel Spaß beim Ausprobieren und Rätseln!

Das Wegeproblem

Vorbereitung:

Sie können das Spiel als PDF herunterladen (opens in new tab) und ausdrucken. Die Pflastersteine farbig auszumalen hilft dabei, den Überblick zu behalten. Wenn Sie keinen Drucker haben, können Sie den Spielplan auch einfach abzeichnen.


Los geht’s:

Auf derm folgenden Bild sieht man die Stadt Darmstadt mit vielen Gebäuden der Technischen Universität Darmstadt. Es sind allerdings keine gepflasterten Straßen dazwischen. Wenn es regnet, müssen die Studierenden und Mitarbeiter*innen der Universität auf matschigen Wegen laufen. Davon bekommen die Leute schmutzige Schuhe, und oft bleiben Fahrräder im Schlamm stecken. Die Präsidentin der TU will das Problem lösen, und plant einige der Wege zu befestigen.

Es gibt nur zwei Spielregeln:

1. Alle TU-Gebäude müssen auf befestigten Wegen erreicht werden können.

2. Es müssen so wenig Pflastersteine wie möglich benutzt werden.

Welche Wege müssen befestigt werden um beide Ziele zu erreichen?


Die Auflösung finden Sie unten auf dieser Seite.

Warum ist Optimierung eines Problems in der Informatik wichtig? Optimierungsprozesse finden in der Informatik ständig statt, zum Beispiel beim Programmieren. Ein Programmcode sollte immer auf möglichst direktem Weg zum Ziel führen, um Rechenzeit zu sparen und somit den Energieverbrauch zu senken. Im großen Maßstab schützen Optimierungsprozesse und effizientes Programmieren daher sogar das Klima.
Optimierungsprobleme gibt es aber auch bei der Linienplanung des öffentlichen Nahverkehrs oder bei Navigationsgeräten im Auto. Dafür programmieren Informatiker*innen sogenannte Algorithmen, die das Wegeproblem dann für sie lösen.

Außerdem stärken Optimierungsaufgaben das logische Denken Ihres Kindes.

Eine mögliche Lösung unseres Wegeproblems

Zunächst einmal muss Ihr Kind herausfinden, wie viele Wege benötigt werden.

Wie viele Straßen oder Verbindungen werden benötigt, wenn es n Häuser in der Stadt gibt? Es stellt sich heraus, dass eine optimale Lösung immer genau n–1 Verbindungen hat, da dies immer ausreicht, um die n Häuser zu verbinden. Einen weiteren Weg hinzuzufügen, würde unnötige alternative Wege zwischen den Häusern schaffen.
In unserem Fall werden also 9 Wege benötigt, um die 10 Häuser zu verbinden.

Um das Wegeproblem zu lösen und herauszufinden, was die kürzeste Strecke ist, gibt es verschiedene Strategien:

  • Alle Möglichkeiten ausprobieren (Sie können Ihr Kind nach einer Weile unterstützen und darauf hinweisen, dass es effizientere Strategien gibt).
  • Eine andere Strategie besteht darin, mit allen gepflasterten Wegen zu beginnen und dann die Wege zu entfernen, die man nicht braucht. Dies ist jedoch auch nicht besonders effizient.
  • Eine einfache Methode, die eine optimale Lösung liefert, besteht darin, mit einer leeren Karte zu beginnen und nach und nach Wege hinzuzufügen, bis alle Häuser verbunden sind. Dabei müssen die Wege in aufsteigender Reihenfolge nach der Anzahl der benötigten Pflastersteine benutzt werden.

Zum Weiterspielen

Für Kinder: Direkt weiter-optimieren mit Farben und Flächen kann man im Browserspiel “Fabios Flächen” bei meine-forscherwelt.de (opens in new tab). Viel Spaß!

Für Erwachsene: Das Wegeproblem ist ähnlich dem “Problem des Handlungsreisenden”, ein Optimierungsproblem, in dem versucht werden muss die kürzeste Route zu finden, die jeden Punkt im Netzwerk besucht. Selbst ausprobieren kann man das in einem Online-Spiel der TU München (opens in new tab).


Unser heutiges Spiel basiert auf den frei verfügbaren Materialien des Haus der kleinen Forscher (S. 24) (opens in new tab) und CSunplugged (S. 88-92) (opens in new tab).

Tägliche Erinnerung an den CROSSING Adventskalender