Kategorien
Uncategorized

Algorithmus und Heuristik

In diesem Blog wird viel von Algorithmen und Heuristiken die Rede sein. Dabei zeigt ein Blick in die Literatur, dass nicht alle unter diesen Begriffen das Gleiche verstehen. Wie so häufig entwickelt man zwar schnell ein Gefühl dafür, was gemeint ist, die formalen Definitionen unterscheiden sich aber teilweise in wichtigen Punkten. Daher versuche ich mich hier gleich zu Beginn an einer Klarstellung, was ich im Rahmen dieses Blogs mit diesen Begriffen meine.

Zunächst einmal geht es immer darum, ein Problem zu lösen. Ein solches Problem kann dabei darin bestehen, eine Schachpartie zu gewinnen, eine Rechenaufgabe zu lösen, den Blumenladen in der Innenstadt zu finden oder mit den mir gegebenen Mitteln stinkend reich zu werden. Immer soll dabei eine Ausgangssituation in eine Zielsituation verwandelt werden oder zumindest in etwas, was diesem Ziel möglichst nahe kommt.

Algorithmus und Heuristik sind nun Vorgehensweisen, mit denen ein solches Problem mehr oder weniger gut gelöst wird. Ein Algorithmus ist dabei eine schrittweise Handlungsanweisung, wobei die Schritte so eindeutig definiert sein müssen, dass keine Missverständnisse aufkommen können. So ist die Handlungsanweisung „Beschwöre einen Djinn und bitte ihn um eine Tonne Gold“ kein Algorithmus für das Problem „Wie werde ich stinkend reich?“, weil der Schritt „Beschwöre einen Djinn“ nicht gut genug definiert ist.

Ein klassisches Beispiel für einen Algorithmus ist dagegen ein Kochrezept, mit dem wir eine Ausgangssituation (einen Stapel Zutaten) in eine Zielsituation (ein schmackhaftes Essen) verwandeln, wobei wir eine Reihe wohldefinierter Anweisungen (eine Zwiebel fein würfeln, 5 Minuten in heißer Butter dünsten,…) abarbeiten. Aber auch die Anweisungsfolge, mit der uns das Navi an unser Ziel bringt („In 200 Metern links abbiegen!“), oder die Rechenvorschrift, mit der wir zwei ganze Zahlen multiplizieren, sind Algorithmen.

Algorithmen müssen übrigens keinesfalls immer deterministisch sein, d.h. bei gleicher Ausgangssituation die gleiche Folge von Schritten ausführen und somit zum gleichen Ergebnis kommen. Es gibt nämlich auch randomisierte Algorithmen, bei denen Ablauf und Ergebnis vom Zufall beeinflusst werden. Ein einfaches Beispiel ist eine Partie „Schere, Stein, Papier“: wenn man dieses Spiel immer nach dem gleichen Verfahren gegen einen intelligenten Gegner spielt, wird dieser früher oder später hinter unseren Algorithmus kommen und dieses Wissen dann gegen uns verwenden. Aber auch in der Mathematik gibt es überraschenderweise Probleme, die sich leichter lösen lassen, wenn man dabei den Zufall mitspielen lässt.

Was aber sind nun Heuristiken? Im Grunde handelt es sich ebenfalls um Algorithmen, allerdings mit den folgenden Besonderheiten:

  • Sie sind ohne großen Aufwand (Zeit, Energieverbrauch,… ) durchführbar.
  • Sie führen auch bei gleicher Ausgangssituation nicht zwingend zum gleichen Ergebnis.
  • Das Ergebnis ist nicht notwendigerweise perfekt.

Manche Heuristiken können sogar dann ausgeführt werden, wenn die Ausgangssituation gar nicht vollständig bekannt ist, andere ignorieren ganz bewusst Teile dessen, was sie eigentlich wissen könnten, um so schneller zu Ergebnissen zu gelangen. Wenn wir beispielsweise einem Auto ausweichen müssen, wäre es wenig sinnvoll, bei unserer Reaktion auch die Farben der Blumen am Straßenrand oder den Redeschwall unseres Beifahrers mit einzubeziehen. Um so schnell wie möglich handeln zu können, beschränken wir uns auf die beiden Autos und einige wenige Hindernisse, mit denen wir absolut nicht kollidieren wollen. Alles andere wird ausgeblendet – ob zu Recht oder zu Unrecht, merken wir dann erst hinterher.

In der Informatik verwendet man Heuristiken, wenn ein Problem zu schwierig ist, um exakt gelöst zu werden. Das menschliche Gehirn dagegen verwendet Heuristiken für so gut wie alle Probleme. Die genaue Vorgehensweise ist uns dabei für gewöhnlich nicht bewusst, weshalb manche Forscher argumentieren, dass es sich bei Heuristiken gar nicht um Algorithmen handelt – schließlich können wir häufig nicht Schritt für Schritt angeben, wie wir es geschafft haben, das Problem zu lösen. Andererseits gelingt es der Kognitionspsychologie immer wieder, explizite Beschreibungen für solche unbewussten Heuristiken zu finden, und dabei handelt es sich (bisher jedenfalls) dann eben doch um ein Vorgehen, das man als (randomisierten) Algorithmus beschreiben kann.

Aus diesem Grund werde ich im Folgenden unter einer Heuristik stets eine Art „Quick-and-Dirty“-Algorithmus verstehen: effizient, unter Umständen etwas händewedelnd, meist aber mit passablen Ergebnissen. Wenn dagegen Algorithmen gemeint sind, die immer die gleiche Schrittfolge ausführen und dabei zum optimalen Ergebnis kommen, dann werde ich diese ausdrücklich als klassische Algorithmen bezeichnen.

Zwei Arten von Algorithmen

P.S.: Und ja, mir ist bewusst, dass es noch zahlreiche weitere Möglichkeiten gibt, Algorithmen zu unterteilen und dass es allein zwischen den Extrempunkten „klassischer Algorithmus“ und „Heuristik“ noch viele Zwischenstufen gibt. Aber solange wir hier (noch) nicht in die Feinheiten der theoretischen Informatik eintauchen, lasse ich diese vorerst noch außen vor.

Nachtrag (8.3.2021): Inzwischen habe ich zu dem Thema einen neuen Beitrag geschrieben, in dem die Aussage, dass Heuristiken ein Spezialfall eines Algorithmus sind, korrigiert wird.

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert