🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Dieser Beitrag stellt das CayleyPy-Projekt vor, das Reinforcement Learning mit Diffusionsabstandsmethoden kombiniert, um Pfadsuche auf massiven Cayley-Graphen effizient zu lösen, klassische Werkzeuge wie GAP erfolgreich übertrifft, starke Belege für die OEIS-A186783-Vermutung bezüglich des Durchmessers der symmetrischen Gruppe liefert und neue theoretische Schranken etabliert, während es durch Kaggle-Wettbewerbe die Teilnahme der Gemeinschaft einlädt.

Ursprüngliche Autoren: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

Veröffentlicht 2026-05-19

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Das große Ganze: Den kürzesten Weg nach Hause in einem Labyrinth aus Spiegeln finden

Stellen Sie sich vor, Sie befinden sich in einem riesigen, unendlichen Labyrinth. Doch dies ist kein normales Labyrinth mit Wänden; es ist ein Labyrinth, das aus Regeln besteht. Jedes Mal, wenn Sie einen Schritt machen, befolgen Sie eine spezifische Regel, die Ihre Position verändert. In der Mathematik nennt man dies einen Cayley-Graphen.

Das Ziel dieses Papiers ist es, eine bestimmte Art von Labyrinth zu lösen: das LRX-Labyrinth. Dieses Labyrinth wird mit den Regeln des Mischens eines Kartendecks (oder einer Permutation von Zahlen) aufgebaut.

Regel L: Verschiebe alles eine Stelle nach links.
Regel R: Verschiebe alles eine Stelle nach rechts.
Regel X: Tausche die ersten beiden Elemente.

Die Herausforderung lautet: Wenn Sie mit einem Kartendeck in einer chaotischen Reihenfolge beginnen, was ist die kürzeste Abfolge von Links-, Rechts- und Tausch-Zügen, um sie wieder in perfekte Ordnung zu bringen?

Das Problem: Das Labyrinth ist zu groß für Menschen (und alte Computer)

Für ein kleines Kartendeck kann ein Mensch oder ein Standardcomputerprogramm (wie die berühmte Mathematik-Software GAP) die Lösung herausfinden. Doch wenn die Anzahl der Karten ( $n$ ) wächst, explodiert die Anzahl der möglichen Anordnungen.

Für $n=20$ ist das Labyrinth riesig.
Für $n=100$ ist das Labyrinth so groß, dass es mehr Pfade gibt als Atome im Universum.

Alte Computerprogramme bleiben stecken. Sie versuchen, jeden einzelnen Pfad zu kartieren, laufen in den Speicherlimitierungen aus und geben auf. Die Autoren wollten herausfinden, ob Künstliche Intelligenz (KI) wie ein intelligenter Entdecker fungieren kann, um den Weg durch diese massiven Labyrinthe zu finden, ohne jeden einzelnen Zentimeter zu kartieren.

Die Lösung: Eine KI beibringen, den Weg zu „erraten"

Die Autoren bauten ein System namens CayleyPy RL. Stellen Sie sich vor, Sie trainieren einen Roboter, um durch das Labyrinth zu navigieren. Sie verwendeten eine Methode namens Reinforcement Learning (RL) (Bestärkendes Lernen).

So haben sie den Roboter trainiert, unter Verwendung einer einfachen Analogie:

1. Das „Aufwärmen" (Diffusionsdistanz)
Stellen Sie sich vor, Sie lassen einen Tintentropfen in ein Glas Wasser fallen. Die Tinte breitet sich zufällig aus. Wenn Sie wissen wollen, wie weit ein bestimmter Punkt vom Zentrum entfernt ist, können Sie beobachten, wie lange es dauert, bis die Tinte ihn erreicht.

Die KI lernte zunächst, indem sie Millionen von „zufälligen Spaziergängen" (wie die sich ausbreitende Tinte) beobachtete. Sie kannte nicht den kürzesten Pfad, aber sie lernte ein „Gefühl" für die Distanz. Sie wusste: „Wenn ich hier bin, dauert es normalerweise etwa 50 zufällige Schritte, um nach Hause zu kommen."
Dies gab der KI eine grobe Karte, aber sie war nicht perfekt.

2. Das „intelligente Training" (Reinforcement Learning)
Als Nächstes lehrten sie die KI, schlauer zu sein. Anstatt nur auf Basis zufälliger Spaziergänge zu raten, verwendeten sie eine Technik namens Deep Q-Learning.

Stellen Sie sich vor, die KI spielt ein Spiel, bei dem sie für jeden Schritt eine „Strafe" erhält. Sie möchte die Ziellinie mit den wenigsten Strafen erreichen.
Die KI probierte verschiedene Züge aus, sah, welche sie näher brachten, und passte ihr Gehirn (neuronales Netz) an, um bessere Vorhersagen zu treffen.
Die Innovation: Sie kombinierten die Intuition des „Tintenverbreitens" mit der Logik des „Spielens". Dies half der KI, nicht in Sackgassen (lokale Minima) stecken zu bleiben, die normalerweise einfachere Algorithmen gefangen halten.

3. Die „Beam Search" (Das Team von Entdeckern)
Dies ist der kritischste Teil. Stellen Sie sich vor, Sie schicken einen Entdecker ins Labyrinth. Wenn er eine falsche Abzweigung nimmt, haben Sie verloren.

Stattdessen schickten die Autoren ein Team von Entdeckern aus (einen „Beam").
An jeder Kreuzung teilt sich das Team. Sie behalten die 10.000 vielversprechendsten Pfade und verwerfen die schlechten.
Indem sie ein riesiges Team halten (in einigen Fällen Millionen von Pfaden), stellt die KI sicher, dass, selbst wenn die meisten Entdecker verloren gehen, mindestens einer den perfekten kürzesten Pfad findet.

Der „Magische Trick" (Der X-Trick)

Die Autoren entdeckten einen lustigen kleinen Shortcut. In ihrem Code fügten sie eine einzige Zeile Logik hinzu:

Wenn die ersten beiden Karten bereits in der richtigen Reihenfolge sind, tausche sie nicht.

Das klingt für einen Menschen offensichtlich, aber für einen Computer war es ein Wendepunkt. Diese winzige Regel, die sie den „X-Trick" nannten, ermöglichte es ihrer KI, Labyrinthe mit 100 Karten ( $n=100$ ) zu lösen.

Ohne den Trick: Die KI konnte nur etwa 40 Karten bewältigen.
Mit dem Trick: Sie bewältigte 100+ Karten und schlug die alte Computer-Software (GAP), die bei etwa 20 Karten abstürzte.

Was bewiesen sie? (Der mathematische Teil)

Neben dem Aufbau eines schnellen Lösern nutzten sie ihre KI, um Entdeckungen über die Mathematik dieser Labyrinthe zu machen:

Die „Gotteszahl"-Vermutung: Es gibt eine berühmte Vermutung in der Mathematik, dass die schwierigste mögliche Mischoperation von $n$ Karten genau $n(n-1)/2$ Züge erfordert. Die KI testete dies für riesige Zahlen und fand niemals eine Mischoperation, die schwerer war als diese. Dies unterstützt stark die Idee, dass diese Formel die absolute Grenze ist.
Die „längste" Mischoperation: Sie identifizierten die einzelne chaotischste mögliche Mischoperation (das „längste Element") und bewiesen genau, wie man sie in Züge zerlegt.
Neue Schranken: Sie bewiesen mathematisch, dass das Labyrinth nicht kleiner als eine bestimmte Größe und nicht größer als eine andere Größe sein kann, wodurch sie die Antwort erheblich eingrenzen.
Die Form des Labyrinths: Sie fanden heraus, dass, wenn man zählt, wie viele Mischoperationen in jedem Abstand vom Start existieren, die Zahlen keiner perfekten Glockenkurve (wie einer Normalverteilung) folgen. Stattdessen folgen sie einer seltsamen, schiefen Form, die Gumbel-Verteilung genannt wird.

Die Ergebnisse: KI gegen die Alte Garde

Das Papier vergleicht ihre neue KI-Methode mit dem Standard-Computeralgebrasystem GAP:

GAP: Kann bis zu ~20 Karten lösen. Es dauert Stunden oder Tage. Die Pfade, die es findet, sind oft lang und ineffizient.
CayleyPy RL (KI): Kann bis zu ~100 Karten lösen. Es ist viel schneller. Es findet Pfade, die der theoretisch kürzestmöglichen Pfad sehr nahe kommen.

Zusammenfassung

Die Autoren schufen ein intelligentes KI-System, das komplexe mathematische Probleme wie ein riesiges Labyrinth behandelt. Indem sie zufälliges Raten mit intelligentem Lernen kombinieren und ein massives „Team" virtueller Entdecker aussenden, können sie Labyrinthe navigieren, die für herkömmliche Computer zu groß sind. Sie fanden sogar einen winzigen „Cheatschalter" (den X-Trick), der es ihnen erlaubt, Probleme zu lösen, die fünfmal größer sind als zuvor, und gleichzeitig neue mathematische Fakten über die Struktur dieser Labyrinthe zu beweisen.

Sie haben ihren Code und ihre Herausforderungen auch auf einer Plattform namens Kaggle veröffentlicht und laden andere ein, ihre Rekorde zu schlagen und zu helfen, noch schwierigere Versionen dieser Rätsel zu lösen.

Technische Zusammenfassung: CayleyPy RL: Pfadsuche und Reinforcement Learning auf Cayley-Graphen

Problemstellung
Der Artikel behandelt das Problem der Pfadsuche auf extrem großen endlichen Cayley-Graphen, mit einem spezifischen Fokus auf die symmetrische Gruppe $S_n$ , die durch zyklische Linksverschiebungen ( $L$ ), zyklische Rechtsverschiebungen ( $R$ ) und eine Transposition der ersten beiden Elemente ( $X$ ) erzeugt wird. Diese Konfiguration, bekannt als LRX-Cayley-Graph, entspricht der OEIS-Folge A186783. Die zentrale mathematische Herausforderung besteht darin, ein Gruppenelement in das kürzestmögliche Produkt von Erzeugern zu zerlegen (Finden des kürzesten Pfades im Graphen). Dieses Problem ist für generische endliche Cayley-Graphen NP-schwer. Klassische Computer-Algebra-Systeme wie GAP verlassen sich auf den Schreier-Sims-Algorithmus, der häufig exponentiell lange Pfade erzeugt und Gruppen mit Größen jenseits von $10^{30}$ (ungefähr $n \approx 20$ für $S_n$ ) nicht bewältigen kann. Die Autoren zielen darauf ab, effiziente, auf künstlicher Intelligenz basierende Ansätze zu entwickeln, die Graphen mit Größen bis zu $10^{70}$ (z. B. $n \approx 40$ bis $100$) handhaben und dabei nahezu optimale oder optimale Pfade erzeugen können.

Methodik
Die Autoren schlagen eine hybride Methodik vor, die Reinforcement Learning (RL), speziell Deep Q-Learning (DQN), mit einer Vor-Trainingsstrategie auf Basis von Diffusionsdistanzen kombiniert.

Reinforcement-Learning-Rahmenwerk: Das Pfadsuchproblem wird als Finden des kürzesten Pfades von einem Zustand $s$ zum Identitätselement $e$ formuliert. Dies wird mittels der Bellman-Gleichung modelliert, wobei die Distanzfunktion $d(s)$ die Bedingung $d(s) = 1 + \min_{t \in N(s)} d(t)$ erfüllt. Das Standard-DQN wird angepasst, um diese Wertfunktion unter Verwendung neuronaler Netze zu approximieren.
Vor-Training mit Diffusionsdistanzen: Um das Problem der „spärlichen Belohnungen" und das Rauschen zu adressieren, das bei der Standard-DQN-Initialisierung inhärent ist, führen die Autoren eine „Warm-up"-Phase ein. Sie generieren Trainingsdaten durch zufällige Spaziergänge (Diffusion), die vom Ziel ausgehen. Ein neuronales Netz wird zunächst darauf trainiert, die Anzahl der Schritte in diesen zufälligen Spaziergängen (Diffusionsdistanz) vorherzusagen.
Modifiziertes DQN: Das vor-trainierte Netz wird anschließend mit einem modifizierten DQN-Algorithmus feinabgestimmt. Entscheidend ist, dass die Bellman-Aktualisierungsziele basierend auf dem Zeitschritt $k$ , zu dem ein Zustand während der Generierung der zufälligen Spaziergänge erstmals besucht wurde, gekappt werden. Dies verhindert, dass das Netz Distanzen überschätzt, und stabilisiert das Training.
Gesteuerte Beam-Suche: Sobald das neuronale Netz trainiert ist, um Distanzen zu schätzen, dient es als Heuristikfunktion für einen Beam-Search-Algorithmus. Die Beam-Suche hält zu jedem Schritt eine feste Anzahl ( $W$ ) der vielversprechendsten Zustände bereit, erweitert deren Nachbarn und wählt die besten $W$ basierend auf den Vorhersagen des Netzes aus. Dies verhindert das Steckenbleiben in lokalen Minima, ein häufiger Fehlermodus bei gieriger Suche.
Der „X-Trick": Eine spezifische heuristische Modifikation für die LRX-Erzeuger wird eingeführt. Wenn die ersten beiden Elemente einer Permutation bereits sortiert sind, wird der Generator $X$ (der sie vertauscht) aus der Nachbarschaftsmenge ausgeschlossen. Diese einzeilige Modifikation reduziert den Suchraum drastisch und verbessert die Mischzeiten.
Nicht-Rückwärtsgehen: Die Autoren integrieren Einschränkungen des Nicht-Rückwärtsgehens sowohl bei der Generierung der zufälligen Spaziergänge als auch bei der Beam-Suche, um die Varianz der Distanzschätzungen zu reduzieren und ein Steckenbleiben in lokalen Minima zu verhindern.

Hauptbeiträge

Algorithmische Fortschritte: Der Artikel präsentiert eine neuartige Kombination aus Vor-Training mit Diffusionsdistanzen und modifiziertem DQN. Dieser Ansatz überwindet die Einschränkungen des Standard-DQN (spärliche Belohnungen, verrauschte Ziele) und übertrifft klassische Methoden.
Leistungsbenchmarks: Die vorgeschlagenen Methoden finden erfolgreich Pfade für LRX-Cayley-Graphen bis zu $n \approx 44$ ohne Vorwissen und bis zu $n \approx 100$ bei Verwendung des „X-Tricks". Dies übersteigt die Fähigkeiten von GAP, das auf $n \approx 20$ begrenzt ist, erheblich. Die KI-Methoden erzeugen kürzere Pfade und laufen schneller als GAP für vergleichbare $n$ .
Mathematische Ergebnisse und Vermutungen:
- Durchmesser-Vermutung: Die Autoren unterstützen stark die OEIS-A186783-Vermutung, dass der Durchmesser des LRX-Cayley-Graphen $n(n-1)/2$ beträgt. Sie verifizierten dies durch brute-force-BFS für $n \le 15$ und durch KI-Zerlegung für $n$ bis 200 (via Kaggle-Wettbewerbe) und fanden keine Zerlegung, die kürzer als die vermutete Länge war.
- Längstes Element: Sie identifizieren ein einzigartiges „längstes Element" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ und liefern eine explizite Zerlegung der Länge $n(n-1)/2$ .
- Schranken: Der Artikel beweist eine untere Schranke für den Durchmesser von $n(n-1)/2 - n/2 - 1$ und eine obere Schranke von $n(n-1)/2 + 3n$ durch einen konstruktiven Algorithmus. Ein empirischer Algorithmus schlägt eine engere Schranke von $n(n-1)/2 + n/2$ vor.
- Wachstumsverteilung: Numerische Experimente deuten darauf hin, dass die Wachstumfunktion des LRX-Graphen für große $n$ einer linksverschobenen Gumbel-Verteilung folgt, im Gegensatz zur Gaußschen Verteilung, die bei Nachbarn-Transpositionsgraphen beobachtet wird.
- Mischzeit: Während zufällige Spaziergänge Mischzeiten zwischen $O(n^3)$ und $O(n^3 \log n)$ haben, vermuten die Autoren, dass zufällige Spaziergänge, die mit dem „X-Trick" modifiziert sind, schneller mischen, mit einer Zeitkomplexität von $O(n^2)$ .
- Spektrum: Das Spektrum des LRX-Graphen scheint einer Gleichverteilung zu folgen.
Open Source und Crowdsourcing: Die Autoren veröffentlichten das Projekt „CayleyPy" und schufen Kaggle-Wettbewerbe, um Lösungen für die Zerlegung des längsten Elements und das Finden optimaler Algorithmen zu crowdsourcen, wodurch die Zusammenarbeit zwischen KI- und mathematischen Gemeinschaften gefördert wird.

Ergebnisse

Effizienz: Für $n=20$ benötigt GAP über 41 Minuten, um einen Pfad der Länge 217.944 zu finden, während die Diffusionsdistanz-Methode den optimalen Pfad der Länge 190 in unter 4 Minuten findet.
Skalierbarkeit: Mit dem „X-Trick" löste das System Instanzen für $n=100$ (Graphgröße $\approx 10^{157}$ ) in etwa 8,5 Stunden auf einer einzelnen GPU und fand einen Pfad der Länge 16.632 (im Vergleich zur vermuteten Durchmesser von 4.950).
Modellleistung: Einfache Modelle wie Multi-Layer Perceptrons (MLP) und Gradient Boosting (CatBoost/XGBoost) übertrafen für diese spezifische Aufgabe oft komplexe Architekturen wie Transformer und CNNs.
Beam-Suche: Die Erfolgsrate beim Finden eines Pfades hängt stark von der Beam-Breite ab und zeigt eine superlineare Verbesserung, wenn die Beam-Größe zunimmt, analog zum „Austausch von Ideen" in einer Forschungscommunity.

Bedeutung
Der Artikel behauptet, dass computergestützte Experimente, insbesondere solche, die KI nutzen, die mathematische Forschung an Cayley-Graphen erheblich voranbringen können. Er zeigt, dass KI-Methoden klassische Computer-Algebra-Systeme sowohl in der Skalierbarkeit (Bewältigung viel größerer $n$ ) als auch in der Lösungsqualität (Finden kürzerer, nahezu optimaler Pfade) übertreffen können. Die Arbeit schließt die Lücke zwischen theoretischer Gruppentheorie und praktischer KI, liefert rigorose Schranken, neue Vermutungen zu Wachstum und Mischzeiten sowie einen Rahmen zur Lösung von Pfadsuchproblemen in extrem großen Zustandsräumen, die zuvor unlösbar waren. Die Autoren positionieren dies als einen Schritt hin zur Anwendung von KI auf andere komplexe Planungsprobleme in der theoretischen Wissenschaft.