• Uninformierte Heuristiken/Algorithmen

– Trial and error

– Tiefensuche

• probiere in jedem Zustand Operatoren nach präferierter Reihenfolge, wende präferierten Operator an

• bei Sackgasse: gehe einen Schritt zurück

• merke dir den Zustand und Operator, der in die Sackgasse geführt hat und meide ihn künftig

– Breitensuche

• Generiere von jedem Zustand aus alle möglichen Folgezustände und prüfe, ob einer der Zielzustand ist

• Probleme:

– universell einsetzbar, aber bei großen Problemräumen mit unrealistischem Zeit- und/oder Speicherbedarf (exponentielles Wachstum bei größeren Problemräumen)

• Informierte Heuristiken

– Unterschiedsreduktion (“hill-climbing”)

• Wende den Operator an, der den nächsten Zustand dem Zielzustand “ähnlicher” macht.

• Probleme:

• Definition der Ähnlichkeit

• Möglichkeit von Sackgassen (“lokale Maxima”, s. Hobbits und Orcs)

– Mittel-Ziel-Analyse

• Bilde vom Ziel ausgehend Zwischenziele, die durch Operatoranwendung erreichbar sind.

Evidenz für Unterschiedsreduktion:

Hobbits & Orcs Problem: 3 Hobbits, 3 Orcs, 1 Fluss, 1 Boot mit Kapazität von jeweils 2

→ wie bekommt man 3 auf jede Seite? → ein entscheidender Schritt, der augenscheinlich vom Ziel weg führt, fällt besonders schwer, ist allerdings notwendig für Lösung (wenn Unterschiedsreduktion angewendet wird)