Exkurs - Algorithmisches Problemlösen

Orientierung

Es ist manchmal gar nicht so einfach, einen Algorithmus zur Lösung eines Problems zu entwickeln - insbesondere dann, wenn das Problem komplizierter ist. Am Beispiel Kleeblatt suchen sollen die wesentlichen Schritte im Folgenden noch einmal kurz zusammengestellt werden.

Das Problem: Kleeblatt suchen

Hier noch einmal eine Beschreibung des zu lösenden Problems.

Kara ist auf der Suche nach einem Kleeblatt. Kara soll hierzu geradeaus weiterlaufen, bis sie/er ein Kleeblatt gefunden hat. Aber, es befinden sich manchmal Baumstümpfe im Weg. Kara muss diese Hindernisse dann umlaufen.

Die folgenden Abbildungen verdeutlichen das Problem mit einer vorher-nachher-Beschreibung der Kara-Welt.

Kara-Welt vorher / nachher

Ideen suchen

Algorithmen bzw. Programme kann man oft nicht gleich hinschreiben. Zunächst muss man nach geeigneten Ideen suchen.

Eine Möglichkeit besteht darin, selbst Kara zu spielen und mögliche Aktionsfolgen von Kara durchzuspielen.

Wenn man Ideen zur Lösung des Problems gefunden hat, dann sollte man sie direkt aufschreiben. Das macht man am besten in der normalen Umgangssprache. Eventuell kann man hierbei schon erste Strukturierungsbegriffe (wie z.B. SOLANGE) benutzen und sie besonders hervorheben.

Kleeblatt suchen:
SOLANGE man nicht auf einem Kleeblatt steht, macht man Folgendes:
    WENN man vor einem Baum steht, dann
        muss man den Baum / die Baumreihe umlaufen
    SONST
        kann man einen Schritt weitergehen
zuletzt muss man das Kleeblatt aufheben

Diese erste Version muss noch verfeinert werden. In der vorliegenden Beschreibung ist noch nicht genau festgelegt, wie man einen Baum / eine Baumreihe umläuft.

Baumreihe umlaufen:
links drehen
Schritt weitergehen
rechts drehen
Schritt weitergehen
SOLANGE man rechts einen Baum ertastet, macht man Folgendes:
    Schritt weitergehen
rechts drehen
Schritt weitergehen
links drehen

Algorithmus entwickeln und formulieren

Bei der Entwicklung eines Algorithmus ist es günstig, auf vorgegebene Bausteine zurückzugreifen. Insbesondere hat es sich bewährt, Struktogramm-Bausteine zur präzisen Darstellung von Algorithmen zu verwenden.

Passend zur informellen Ideenbeschreibung kann man so das folgende Struktogramm entwickeln.

Algorithmus implementieren

Der letzte Schritt zur Entwicklung einer lauffähigen Problemlösung besteht darin, den Algorithmus in eine vom Ausführsystem vorgegebene Sprache zu übersetzen. In unserem Kara-System ist das die Programmiersprache Python.

while not kara.onLeaf():
    if kara.treeFront():
        kara.turnLeft()
        kara.move()
        kara.turnRight()
        kara.move()
        while kara.treeRight():
            kara.move()
        kara.turnRight()
        kara.move()
        kara.turnLeft()
    else:
        kara.move()
kara.removeLeaf()

Hierbei muss man dann natürlich die Besonderheiten der vorgegebenen Sprache beachten.