Strukturelle Analyse in kombinatorischen Rekonfiguration

Die Kombinatorische Rekonfiguration beschäftigt sich mit den Transformationen zwischen Zuständen eines Objekts. Ein Beispiel hierfür ist der Rubiks Cube: Jeder Zustand stellt eine Anordnung der farbigen Sticker auf dem Würfel dar, und ein Zustand kann durch das Drehen einer Fläche in einen anderen Zustand transformiert werden. Die Aufgabe besteht darin, den schnellsten Weg von einem Ausgangszustand (einer zufälligen Anordnung der Sticker) zu einem gewünschten Zustand (dem gelösten Würfel mit einheitlichen Farben auf jeder Fläche) zu finden. Rekonfigurationsprobleme treten nicht nur bei Puzzles wie dem Rubiks Cube auf, sondern auch in vielen anderen Kontexten, von denen dieses Projekt zwei genauer untersucht. Zum einen wird die k-Opt-Heuristik für das Problem des Handlungsreisenden (TSP) betrachtet. Dieses Problem verlangt eine kürzeste Tour, die eine Reihe von Städten besucht und zum Ausgangspunkt zurückkehrt. Die k-Opt-Heuristik beginnt mit einer beliebigen Tour und ersetzt schrittweise bis zu k Reiseabschnitte der Tour durch Alternativen, um die Gesamtlänge der Tour zu verkürzen. Diese Heuristik ist ein zentraler Bestandteil des Lin-Kernighan-Algorithmus, einer weit verbreiteten Methode zur Lösung des TSP. Obwohl die k-Opt-Heuristik in der Praxis gut funktioniert, sind die mathematischen Garantien für die Laufzeit deutlich schlechter, insbesondere wenn k > 4. Dieses Projekt zielt darauf ab, diese Lücke zu schließen: Gibt es bessere Laufzeitgarantien falls k < 5? Gibt es spezifische strukturelle Eigenschaften der Distanzen zwischen den Städten, die die Effizienz der Heuristik verbessern könnten? Kann die Heuristik so modifiziert werden, dass sie schneller läuft, wenn wir uns mit einer etwas schlechteren Lösung zufriedengeben? Der zweite Kontext ist die kombinatorische Generierung, bei der alle Objekte einer bestimmten Beschreibung aufgelistet werden. Ein klassisches Beispiel ist das Erzeugen aller binären Zeichenketten einer bestimmten Länge mit dem Binary Reflected Gray Code. Eine interessante Eigenschaft dieser Auflistung ist, dass aufeinanderfolgende Zeichenketten sich nur an einer einzigen Stelle unterscheiden. Allgemeiner gesagt bezieht sich der Begriff "Gray-Code" auf jede Auflistung, bei der sich aufeinanderfolgende Elemente nur durch eine kleine Änderung unterscheiden. (Hier entsprechen die Elemente den Zuständen eines Rekonfigurationsproblems und die kleinen Änderungen entsprechen den Transformationen.) Obwohl viele Gray-Codes bekannt sind, ist es nachgewiesenermaßen im Allgemeinen schwierig, einen Gray-Code für eine gegebene Menge von Objekten zu finden. Dieses Projekt zielt darauf ab, unser Verständnis der Berechenbarkeit von Gray-Codes zu vertiefen: Welche strukturellen Eigenschaften muss eine Menge von Objekten haben, damit ein Gray-Code effizient berechnet werden kann? Die untersuchten Objekte umfassen unter anderem Zeichenketten, Permutationen und Graphstrukturen, die alle in verschiedenen Bereichen der Informatik wichtig sind.