vorige nächste

Bewertung des Ergebnisses


Sucht man mit dem vorgestellten Programm einen Lösungsweg in unserem Labyrinth mit den vielen möglichen Zyklen, dann erhält man zwar nicht einen optimalen Weg, aber keinen mit einer Wiederholung von Knoten.

Dass man aber bei der Suche eventuell dennoch mehrfach denselben Knoten besucht, hat seine Ursache darin, dass wir schon besuchte Knoten bei einem Rücksprung in der Rekursion wieder aus der besucht - Liste entfernen. Dabei verlieren wir allerdings die Inforamtion, dass wir von dort aus schon versucht haben, die Lösung zu finden und sie nicht gefunden haben. Daher kann es sein, dass ein solcher Knoten auf einem anderen Weg erneut aufgesucht und voll untersucht wird, wie das Beispiel des folgenden Labyrinthes zeigt:

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

Hier kann die Suche von der 1 über 2, 3, 6 zur 5 führen, bei der man nun feststellt, dass 2 schon in der besucht - Liste enthalten ist, keine weitere Alternative vorhanden ist und nun umkehrt. Man kommt dann aber wieder zurück zu Knoten 2 und versucht dort noch die Alternative 5, obwohl inzwischen klar ist, dass von dort aus die Lösung nicht erreicht werden kann.

Es ist eine sinnvolle Aufgabe herauszufinden, wie das verhindert werden kann -->Aufgabe (Stichworte: OPEN - Liste und CLOSED - Liste)