i

Problemlösestrategien

Imperative Problemlöseverfahren

Imperative Problemlöseverfahren beschreiben möglichst genau, wie man zu einer Lösung gelangt.

Im Fall des Graphenproblems "Suche nach einem Weg" ist genau zu beschreiben, wie man einen Weg zwischen einem Start- und einen Zielknoten findet.

ALGORITHMUS: Wegsuche in gerichteten Graphen
Eingabe: gerichteter Graph, Startknoten, Zielknoten
Markiere den Startknoten.
Füge den Startknoten in eine leere Liste ein.
Solange die Liste nicht leer ist und den Zielknoten nicht enthält:
    Wähle einen Knoten aus der Liste aus.
	Für alle Nachbarknoten des gewählten Knotens:
	    Falls der Nachbarknoten noch nicht markiert ist:
            Markiere ihn,
            vermerke als Herkunft den gewählten Knoten und ..
            füge ihn in die Liste ein.	
    Entferne den gewählten Knoten aus der Liste.
Starte mit einem "leeren Weg". 
Wenn die Liste den Zielknoten enthält:
    Aktueller Knoten ist der Zielknoten.
    Solange der Startknoten nicht erreicht ist:
        Der Weg wird um die Verbindung zwischen dem aktuellen Knoten ..
        und dem vermerkten Herkunftsknoten erweitert.
        Aktueller Knoten ist der vermerkte Herkunftsknoten ..
        des bisherigen aktuellen Knotens.
Ausgabe: Weg

Ein System zur Verarbeitung imperativer Problemlöseverfahren muss in der Lage sein, eine imperative Lösungsbeschreibung Schritt für Schritt auszuführen.

Deklarative Problemlöseverfahren

Deklarative Problemlöseverfahren beschreiben möglichst genau, was das Problem ausmacht.

Im Fall des Graphenproblems "Suche nach einem Weg" ist genau zu beschreiben, was ein Weg zwischen einem Start- und einen Zielknoten ist.

Regel 1: 
Ein Weg zwischen einem Startknoten und einem Zielknoten besteht aus der 
Verbindung Startknoten - Zielknoten, 
wenn der Zielknoten ein Nachbarknoten des Startknotens ist.
Regel 2: 
Ein Weg zwischen einem Startknoten und einem Zielknoten besteht 
(für einen bestimmten Nachbarknoten des Startknotens) aus 
der Verbindung Startknoten - Nachbarknoten und 
einem Weg zwischen dem Nachbarknoten und dem Zielknoten.

Ein System zur Verarbeitung deklarativer Problemlöseverfahren muss in der Lage sein, aus einer deklarativen Problembeschreibung eine Lösung zu erzeugen.

Vorschreiben und Beschreiben

Hier noch einmal der Unterschied zwischen imperativen und deklarativen Verfahren:

Imperative Problemlöseverfahren schreiben vor, wie man zu einer Lösung gelangt.

Deklarative Problemlöseverfahren beschreiben, was das Problem ausmacht.

Suche

v
10.2.4.2
www.inf-schule.de/deklarativ/logischeprogrammierung/deklarativeprogrammierung/station_loesestrategien

Rückmeldung geben