vorige nächste

Das Kriterium bei der Breitensuche


Zunächst einmal aber: Was bedeutet eigentlich Breitensuche ?

Strategie bei der Breitensuche
Wähle als nächsten zu expandierenden Knoten einen beliebigen unter denen mit minimaler Pfadlänge (Tiefe) aus.
Und man könnte hier hinzufügen: ... und stelle das Expandieren der dem jetzigen Pfad nachfolgenden solange zurück, bis alle Knoten der zuletzt expandierten Ebene sich als nicht erfolgreich erwiesen haben.

Unser Beispiellabyrinth soll wieder die folgende Form haben:

1 -- 2 -- 3
I       I
4 -- 5   6
I   I   I
7   8   9

Wir gehen dabei wieder zunächst einmal von einem einfachen gerichteten Graphen aus, also einem Baum. Als Startknoten wählen wir wieder den Wurzel - Knoten 1 und als Zielknoten den Knoten 8.

Verfolgen Sie einmal -unabhängig von einer Lösung im Programm- die Schritte der Expansion des Graphen auf der Grundlage der o.a. Forderung !

[Zur Datenstruktur siehe bei der Tiefensuche.]