www.AlgorithMan.de
where theory comes alive
Ein Open Source Graphentheorie Framework für C++, das ich (alleine) entwickelt habe. Der Fokus liegt auf der Implementierung komplexer Optimierungs-Verfahren (Verzweigungs-Vektor Minimierung, Problemkern-Reduktionen, Früherkennung von suboptimalen Kandidaten, Früherkennung von Sackgassen, etc.) mit denen auch für algorithmisch schwere Probleme gute Laufzeiten erreicht werden.
Es beinhaltet
24 KiB
Meine Lösung für das bekannte Einstein-Rätsel. (Eigentlich ist das das Zebrarätsel und hat überhaupt nichts mit Einstein zu tun...)
So habe ich es manuell gelöst und dann dieses Javascript geschrieben, das das Problem genau so löst. Graphentheoretisch ausgedrückt, konstruiert es einen Graphen für das Problem und zerlegt diesen in 5 Cliquen der Größe 5 und nutzt dabei hauptsächlich aus, dass die Kantenrelation in Cliquen transitiv ist.
22 KiB
Berechnet offene oder geschlossene Springerzüge (Graphentheoretisch ausgedrückt, sucht es Hamiltonkreise bzw. Hamiltonpfade in Springergraphen).
Mit Hilfe von Warnsdorffs Heuristik und Erreichbarkeits-Analysen (mit denen verhindert wird, dass Schnittknoten im Springergraphen zu früh verwendet werden) wird die Laufzeit deutlich verbessert.
108 KiB
Es ist zwar nichts Anderes als der Dijkstra Algorithmus, den ich natürlich auch im Open-Graphtheory.org Projekt implementiert habe, aber ich kann mich trotzdem nicht davon trennen... Dafür bin ich einfach zu stolz darauf, den Algorithmus schon in der Schulzeit selbst entwickelt zu haben.
29 KiB
Ein Programm, das (per Backtracking) Damen auf einem Schachbrett so verteilt, dass jedes Feld bedroht ist. Graphentheoretisch ausgedrückt, sucht es Dominanzmengen in Queen-Graphen.
2 KiB
Generiert in nur O(n²) Schritten Spielpläne für Turniere. Dazu verwendet es die 1-Faktorisierung von vollständigen Graphen nach Kirkman und Reiß (Satz 7.14 auf Seite 129 in Graphen an allen Ecken und Kanten von Professor Lutz Volkmann).