|
Es gibt Probleme, für die es kein geradliniges Lösungsverfahren gibt. So läßt sich zB kein Algorithmus und keine Formel finden, mit deren Hilfe man Schach spielen und gewinnen könnte. Es wird also ein andrer Lösungsweg gesucht -> Ausprobieren.
Tiefensuche (depth-first-search)
Bei der Tiefensuche wird ein Baum in die Tiefe gehend durchsucht. Das heiß, der Algorithmus untersucht zuerst einen Teilast bis zum Ende. Ist das Ziel nicht erreicht, erfolgt ein Rückziehen zum letzten besuchten Knoten, und der nächste von dort abzweigende Teilast wird untersucht.
Breitensuche (breadth-first-search)
Es werden zuerst alle Knoten der Rekursionstiefe 1 (Startknoten) überprüft, danach alle Knoten der Tiefe 2, dann Tiefe 3,...
Bestensuche
Die Bestensuche ist ein Spezialfall der Breitensuche. Bei ihr wird zuerst immer der Weg untersucht, der die geringsten \"Kosten\" verursacht; bei Labyrinthen ist das der jeweils kürzeste Weg. Die Bestensuche findet so immer eine optimalen Weg.
Bergsteigen (hill-climbing)
Das Bergsteigen kann angewandt werden, wenn es sich um ein Problem handelt, bei dem man einem Knoten eine Bewertung zuordnen kann, bei Labyrinthen etwa die Luftlinienentfernung zum Ziel. Es beruht auf dem Prinzip, daß jeder Knoten eine bestimmte Wertigkeit hat und man immer den Knoten mit der höchsten Wertigkeit als ersten aufruft, danach den mit der zweithöchsten Wertigkeit,...
Graphsuch-Algorithmen (graph-search)
Graphsuch-Algorithmen sind eine Verbesserung von Tiefensuche und Breitensuche. Diese Algorithmen haben den Vorteil, daß sie Wege, die einmal ausprobiert wurden und nicht zum Ziel geführt haben, nicht vergessen werden.
Heuristische Suchverfahren
Heuristisches Suchen grenzt das sogenannte uninformative Suchen von anderen Suchmethoden ab. Uninformiert soll hier bedeuten, daß dem Algorithmus keine Angaben über die Lage des Zielknotens vorliegen und somit nicht direkt in Richtung Ziel gegangen werden kann. Heuristische Verfahren arbeiten häufig mit Schätzfunktionen. Dadurch ähneln sie in ihrem Ablauf, der Art und Weise, in der auch ein Mensch beim Problemlösen vorgeht. Heuristische Verfahren setzen voraus, daß die Knoten eines Baumes bewertet werden können.
Versuch/Irrtum (Backtracking)
Ähnlich dem heuristischen Suchverfahren. Beim Durchsuchen des Baumes muß man in einer bestimmten Reihenfolge vergehen. Zuerst probiert man es rechts. Sollte dieser Weg fehlschlagen, so versucht man es links. Ist dieser Weg auch nicht erfolgreich, so geht man so lange rückwärts, bis man zur letzten Abzweigung kommt. Dieser Vorgang heißt Backtracking.
|
