Einer der bekanntesten Algorithmen zum Lösen von (formalisierten) Problemen, der in keiner Grundlagenvorlesung zur Künstlichen Intelligenz oder Informatik fehlen darf, ist die Tiefe - Zuerst - Suche. Vielleicht weniger bekannt ist, daß dieser Algorithmus zu prähistorischer Zeit (ungefähr 2000 v.u.Z.) von einer Frau, nämlich Ariadne, erfunden worden ist, die damit mit Fug und Recht als Begründerin eines wichtigen Teilgebiets der Informatik (des Algorithmenentwurfs) gelten kann. Da dieser Aspekt der Sage von Ariadne in der Literatur (z.B. in den "Sagen des klassischen Altertums" von Gustav Schwab) meist zu wenig gewürdigt wird, sei sie hier - ergänzt um einige weitergehende Interpretationen, für die der Verfasser dieses Artikels die volle Verantwortung trägt - noch einmal etwas ausführlicher erzählt.
![]() |
Die Athener, deren König Ägäus (Aigeos) war, hatten an den König Minos von Kreta alle neun Jahre einen schrecklichen Tribut zu entrichten, nämlich 7 junge Frauen und 7 junge Männer, die dann dem Minotaurus zum Fraße vorgeworfen wurden. Der Minotaurus war ein Zwitterwesen, unten Mensch und oben Stier, das im Labyrinth von Knossos, der damaligen Hauptstadt von Kreta hauste. Die Opfer wurden in das Labyrinth geführt, das so kompliziert war, daß man sich (ohne einen geeigneten Suchalgorithmus) nicht mehr zum Eingang zurückfinden konnte. Sie wurden hier entweder vom Minotaurus gefressen oder mußten elend verschmachten, weil das Labyrinth so kompliziert war, daß sie in endlicher Zeit nicht mehr hinausfinden konnten. Der Minotaurus kannte sich natürlich aus, er hatte sich durch jahrzehntelanges Routenlernen längst einen Überblick über das Labyrinth verschafft, also "Überblickswissen" erworben, wie wir heute gelehrt sagen würden. Dieses ermöglichte es ihm, ohne expontiell aufwendige Suche und in linearer Zeit von einer Stelle des Labyrinths zu einer beliebigen anderen Stelle zu laufen.
Nun war inzwischen Theseus, der Sohn des Königs Ägäus zum Jüngling herangewachsen und nach Athen gekommen. Da er ein richtiger Königssohn war und die Athener ohnehin murrten, daß der Sohn des Königs von der Auslosung ausgeschlossen werden sollte, beschloß er, sich freiwillig an die Spitze der nächsten Delegation nach Kreta zu stellen und den Minotaurus zu töten. Nachdem sie in Knossos beim König Minos angekommen waren, verliebte sich Ariadne, die Tochter des Königs in den stattlichen Helden Theseus und wollte ihn deshalb retten (um ihn danach für sich zu haben). Sie gab ihm einen Wollknäuel mit in das Labyrinth, er sollte das Fadenende heimlich am Eingang befestigen und dann, um den Minotaurus zu suchen und nach dessen Tötung zum Eingang zurückzufinden, nach folgendem Algorithmus die verfahren:
1) Beim Vorwärtsgehen von einem Kreuzungspunkt zum nächsten solle er den Faden abwickeln (also Ausführung der Operation "gehe vorwärts und wickle dabei den Faden ab").
2) Wenn er an eine schon besuchte Kreuzung kommt, durch die der Faden schon läuft (die also auf diese Weise "markiert" ist), dann solle er entlang des abgewickelten Fadens zum vorigen Kreuzungspunkt zurückgehen und dabei den Faden wieder aufwickeln ("backtracking").
![]() |
Wir erkennen hier unschwer das Prinzip der Tiefensuche. Das Ab- bzw. Aufwickeln des Fadens entspricht genau dem Stackaufbau bzw. -abbau. Der Stack ist jedoch gewissermaßen in der Umgebung (dem Labyrinth) mit Hilfe des Wollfadens materialisiert. Damit wird auch Theseus' Gedächtnis entlastet (das ohnehin durch die Furcht vor dem Minotaurus störanfällig geworden ist).
Theseus trifft nun tatsächlich auf den Minotaurus und bringt ihn um. Mithilfe des Fadens finden er und seine Gefährten wieder aus dem Labyrinth heraus. Ariadne kann damit als Erfinderin des Tiefensuchalgorithmus gelten (Es mindert ihr Verdienst nicht, daß sie, wie die Sage erzählt, dazu von Dädalus, dem großen technischen Genie und Erbauer des Labyrinths, einige Hinweise erhalten haben soll). Der Rest der Sage hat mit (formalisierter) Informatik nicht mehr viel zutun, sondern mit tragischen Verwicklungen, wie wir sie in der klassischen Mythologie und im antiken griechischen Drama so oft finden. Theseus flieht noch in derselben Nacht mit seinen Gefährten und Ariadne aus Knossos, nachdem sie die Schiffe der Kreter unbrauchbar gemacht haben, so daß diese ihnen nicht folgen können. Sie ankern vor der Insel Dia, die heute Naxos heißt. Nach einer Version der Sage (es gibt mehrere) erschien hier Dionysos (Bacchus), der Gott des Weines, Theseus im Schlaf und bedeutete ihm, daß Ariadne die ihm vom Schicksal bestimmte Verlobte sei, die er ihm deshalb zu überlassen habe [Merkte Theseus, daß sie zu sehr dem Weine zugetan war?]. Theseus, der Ariadne inzwischen auch liebte (und ihr außerdem zu Dank verpflichtet war), fügte sich schweren Herzens und ließ sie auf Naxos zurück. Nun hatten die Seefahrer bei ihrer Abfahrt in Athen auf Geheiß von Ägäus zum Ausdruck seiner Trauer schwarze Segel gesetzt und vereinbart, weiße zu setzen, wenn Theseus gesund zurückkehren sollte. Auf Grund seines Kummers um die verlorene Ariadne vergaß Theseus, die Segel zu wechseln. Als Ägäus das Schiff mit den schwarzen Segeln erblickte, stürzte er sich vor Verzweiflung um den verloren geglaubten Sohn von der Klippe, von der aus er Ausschau gehalten hatte, ins Meer, das seitdem das Ägäische heißt.
Die Ereignisse im Labyrinth von Knossos liegen nun einige tausend Jahre zurück. Inzwischen hat sich der menschliche Geist und das Bewußtsein enorm weiterentwickelt. Heute gehört die Tiefensuche zum Standardrepertoire jeder Informatik- und KI-Grundlagenvorlesung. Mußte Theseus noch unter erheblichem körperlichem Aufwand im Labyrinth hin- und herlaufen (man stelle sich seine physische Anstrengung vor, wenn Ariadne ihm die Breitensuche empfohlen hätte!) und wäre ohne den Wollfaden verloren gewesen, bilden wir heute formalisiertes Problemlösen und die damit verbundenen Suchprobleme auf die Wegsuche in einem abstrakten Graphen ab. Und zwar lassen sich viele konkrete Suchprobleme in ganz unterschiedlichen Wirlichkeitsbereichen, sei es das Finden eines Weges zu einem Ziel in einer unbekannten Stadt, das Einkaufen in einem Supermarkt mit einer umfangreichen Einkaufsliste oder die Abarbeitungsstrategie des Prologinterpreters, in diese abstrakte Form transformieren. Im einfachsten Fall gelingt dies sogar durch einen Isomorphismus. Wir wissen nicht, durch welche Evolutionssschritte diese ungeheure kreative Leistung erstmals möglich war, wahrscheinlich hat sie sich schrittweise mit der Entwicklung des Frontalhirns vollzogen.
Gewissermaßen ihre Umkehrung, nämlich die Transformation vom Abstrakten ins Konkrete wird uns heute (z.B. beim Lösen von Übungsaufgaben oder beim Programmieren) immer dann abgefordert, wenn wir uns bei der Lösung einer für uns qualitativ neuartigen abstrakten Aufgabe etwas "Vorstellen", also versuchen, das abstrakte Problem zunächst einmal in eine konkret vorstellbare Welt zurückzuübersetzen. Kreative Denkprozesse die auf reiner Symbolmanipulation beruhen, sind wohl eher die Ausnahme, bei echten kreativen Leistungen greifen wir wahrscheinlich noch immer auf irgendeine Form der "Anschauung" zurück. Wir versuchen dann zunächst eine "analoge Simulation" der Problemlösung in einer vorgestellten konkreten Umwelt oder lassen uns zumindest davon anregen. Das menschliche Vorstellungsvermögen kann also das u.U aufwendige Agieren in der realen Welt ersetzen. Es ist ein Repräsentationsmedium das zwischen das Agieren in der Welt und das abstrakte Denken geschaltet ist und das heutige Computer leider noch nicht haben. Die eigentliche kreative Leistung besteht dann in der Transformation der anschaulichen in die abstrakte Darstellung oder - um im speziellen Fall auf unser klassisches Beispiel zurückzukommen - auf die Tiefensuche im abstrakten Problemgraphen. Die Abarbeitung des abstrakten Algorithmus, die auf Symbolmanipulation beruht, kann dann auch der Rechner durchführen, der wiederum im Unterschied zum Menschen ein viel größeres und störungssichereres Gedächtnis hat, ganz abgesehen von der höheren Verarbeitungsgeschwindigkeit. Selbst wenn das sogenannte menschliche Arbeitsgedächtnis wie ein Stack organisiert wäre (was einmal eine Zeit lang angenommen wurde) müßten wir, wenn wir komplexere Probleme ohne Rechner lösen müßten (z.B. die Übungsaufgabe "Maus im Labyrinth" aus INFO III für ein konkretes Labyrinthproblem) schon Papier und Bleistift zur Hand nehmen und damit unser Arbeitsgedächnis sowie die darüber ablaufenden Operationen zum großen Teil nach außen verlagern - ähnlich wie Theseus, wenn auch unter geringerem physischen Aufwand (!). Die Erfindung der mentalen (geistigen) Operationen durch die Evolution entlastet uns also auch von physischem Aufwand. Der bedeutendste Entwicklungsfortschritt - und das sei hier nur am Rande vermerkt - ist aber wohl die Möglichkeit des planenden Vorausspiels, die Erzeugung und Bewertung möglicher alternativer Situationen, die es uns erlaubt, ein Stück weit in die Zukunft zu gucken - ohne schwarze Löcher und Zeitumkehr, wie sie jetzt in modernen physikalisch - kosmologischen Theorien diskutiert wird.
![]() |
Damit geraten wir aber auch an noch andere Grenzen algorithmischen ("automatischen") Problemlösens sowie der Künstlichen und teilweise auch der natürlichen Intelligenz. Alle auf Suchtechniken beruhenden Problemlöser funktionieren zunächst nur in einer statischen Umwelt, Tiefen- und Breitensuche wären erfolglos, wenn sich die Wände des Labyrinths in unkontrollierbarer Weise zeitlich verschieben würden. Dieses Problem hat offenbar auch schon die Menschen in sagenhafter Vorzeit beschäftigt und wir finden dafür ebenfalls Beispiele in der griechischen Mythologie: Der listenreiche (!) Odysseus gelangt auf seiner vom rachsüchtigen Poseidon verordneten Irrfahrt zu Scylla und Charybdis. Charybdis ist ein dreimal täglich auf- und abschwellender Strudel, der von einem hohlen Felsen erzeugt wird. Wenn es nicht gelingt, den zeitlichen Verlauf der Strömung vorherzuberechnen (zu prognostizieren, würden wir heute sagen) und dieser so weit wie möglich durch geschicktes Steuern auszuweichen, wird das Schiff rettungslos auf den Meeresgrund gerissen. Aber leider hat das Ausweichen vor der Strömung einen sehr unangenehmen Nebeneffekt: man kommt zunahe an den dicht gegenüberliegenden Felsen, in dem das schreckliche vielköpfige Ungeheuer Scylla wohnt, das sich ,wenn Schiffe zu nahe kommen, mit seinen Fangarmen die Seeleute von Deck holt und auffrißt. Odyssues ist von Kirke (Circe), von der sie gerade kommen, auf diese komplizierte dynamische Situation vorbereitet worden (sic! wieder ist es eine Frau) und muß nun eine schwerwiegende Kompromißentscheidung treffen. Diese fällt so aus, daß er den Steuermann richtig instruiert, aber seinen Gefährten vorsichtshalber nichts von Scylla erzählt. Durch geschickte Prognose der Strudeldynamik und daraus abgeleiteter Steuerung (würden wir heute sagen) kommen sie am Strudel vorbei, aber dadurch notwendigerweise zu dicht an Scylla heran, die sechs der tapfersten Genossen erwischt und auffrißt - der bisher schmerzlichste Verlust für Odysseus, wie uns Homer erzählt (Homer, Odyssee, Zwölfter Gesang). [Schiller muß das Motiv der Charybdis ebenfalls sehr beeindruckt haben, denn er hat es in seine Ballader "Der Taucher" verwendet. Hier sind ähnliche Interpretationen möglich.]
Bei diesem wahrhaft "klassischen" Beispiel für Planen und Problemlösen in dynamischen Situationen handelt es sich immer noch um eine überschaubare Verhältnisse in einem zwar nicht mehr statischem aber doch geschlossenen System, wie der systemtheoretische Fachausdruck lautet. Das soll bedeuten, daß das Verhalten aller beteiligten Objekte mit ausreichender Genauigkeit beobachtet, auf Grund von Beobachtungen vorhergesagt und darauf aufbauend Optimalverhalten geplant bzw. situationsabhängig gelernt werden kann. Es gibt keine nicht beobachtbaren "verborgenen Parameter " die das Verhalten des Systems auf unkontrollierbare Weise mitbestimmen, z.B. Wechselwirkungen mit anderen Systemen.
Zu jeder Zeit mußten die Menschen existenziell an der Vorhersage von Ereignissen in Natur und Gesellschaft und deren zeitlichen Verläufen interessiert sein. War diese Vorhersage doch die einzige reale Grundlage, Gefahren zu begegnen und notwendige Tätigkeiten zu planen. In der Wissenschaftsgeschichte, die auch eine Geschichte der Entwichlung der menschlichen Intelligenz ist, hat daher das Entdecken von Gesetzmäßigkeiten, das immer auch mit kollektiven Lernprozessen gekoppelt war, eine entscheidende Rolle gespielt. Die Vorhersage der Planetenbewegungen auf der Basis der rein phänomenologisch beschriebenen Bahnen am Himmel war außerordentlich kompliziert, erst die überraschend einfachen drei Gesetze, die Kepler mit Hilfe der Beobachtungsprotokolle Tycho Brahes fand, lieferten eine elegante und exakte Vorhersagemöglichkeit.
Aber auch hier sind der menschlichen (und erst recht der Künstlichen) Intelligenz Grenzen gesetzt, die allerdings durch die wissenschaftliche Forschung immer weiter herausgeschoben werden. Wir sind in der Realität in ein offenes System (Bertalanffy) eingebunden, in dem sich nicht alles vorhersagen und planen läßt. Unsere Steuer- und Planungsmöglichkeiten sind begrenzt, da wir selbst Systembestandteil sind. Es treten unerwartete und unberechenbare Ereignisse in der äußeren Umwelt auf, oder unsere "innere Umwelt" (damit meine ich z.B. unkontrollierte Affekte und Emotionen), macht unseren kognitiven Prozessen [Unter kognitiven Prozessen verstehen wir Prozesse der Wahrnehmung, des Problemlösens, Schlußfolgerns und Planens, Lernens und Sprachverstehens.] einen Strich durch die Rechnung, so daß sie nicht mehr ordnungsgemäß funktionieren. Dann kann es zu den sogenannten "Schicksalsschlägen" kommen ("Faktoren", übersetzt "Macher" nennen wir sie heute meist), für die Geschichte von Theseus' Rückkehr nach Athen, und viele andere klassische griechische Sagen und Tragödien so eindrucksvolle Beispiele liefern.
Wer einmal nach Heraklion, der heutigen Haupstadt Kretas kommt, sollte unbedingt einen Ausflug in das ca. 4 km entfernte Knossos machen, wo noch die Überreste des Palastes von Minos mit guterhaltenen Fresken zu besichtigen sind. Die Fresken stellen u.a. das Stierspringen, eine im minoischen Reich beliebte und sehr gefährliche Wettkampfart dar, an der auch die Frauen teilnahmen. Das Labyrinth ist nicht zu sehen, wenn es wirklich existiert hat, ist es sicherlich in tieferen, noch nicht freigelegten Schichten zu suchen.