Wie groß wird der Suchbaum?
Wie groß wird der Suchbaum?
Für kleine Graphen ist Brute Force schnell erledigt. Aber wie sieht es bei größeren Graphen aus? Wir testen das an einem Gittergraphen wie einem Stadtplan mit Straßen im Schachbrettmuster: Gesucht ist der kürzeste Weg von links oben nach rechts unten. Der Rechner probiert alle einfachen Wege aus.
Werkzeug: Brute Force im Gitter
Stelle die Größe ein und starte die Suche. Beobachte mit dem Tempo „Weg für Weg“ zuerst, wie der Rechner vorgeht.
Gesucht ist der kürzeste Weg von links oben nach rechts unten. Grün hinterlegt: ein kürzester Weg zum Vergleich; orange: der Weg, den der Rechner gerade untersucht; lila gestrichelt: der beste Weg, den er bisher gefunden hat. Nach spätestens 10 Sekunden bricht die Suche ab.
- Mögliche Wege insgesamt
- –
- Untersuchte Wege
- –
- Anteil untersucht
- –
- Benötigte Zeit
- –
- Bester bisher gefundener Weg
- –
- Länge des kürzesten Wegs
- –
- Zeit für alle Wege bei diesem Tempo
- –
Aufgabe 1: Lass die Suche für verschiedene Größen laufen (Tempo „so schnell wie möglich“) und trage deine Beobachtungen ein.
| Größe | mögliche Wege | Anteil nach höchstens 10 s | Zeit für alle Wege |
|---|---|---|---|
| 3 × 3 | |||
| 5 × 5 | |||
| 6 × 6 | |||
| 7 × 7 | |||
| 9 × 9 | |||
Aufgabe 2: Ein neuer Rechner ist doppelt so schnell. Wie viel größer darf das Gitter werden, damit er in derselben Zeit alle Wege untersucht?
Aufgabe 3: Eignet sich Brute Force für ein Navi im Saarland mit vielen tausend Kreuzungen? Begründe mit deinen Beobachtungen.
Merke
Der Aufwand eines Verfahrens beschreibt, wie viel Arbeit (z. B. Zahl der Rechenschritte, benötigte Zeit) es abhängig von der Größe der Eingabe braucht. Bei Brute Force für kürzeste Wege wächst er so schnell, dass schon mittelgroße Graphen praktisch nicht mehr lösbar sind – daran ändert auch ein schnellerer Rechner wenig.