Inhaltsverzeichnis
2.1.2. Bewegungsabhängigkeit

2.2. Zerlegen in Assur-Gruppen

In Abschnitt 2.1. wurde gezeigt, dass der Aufbau eines MTs aus AGn eindeutig ist. Wie kann nun diese eindeutige Zerlegung ermittelt werden? Problematisch ist dabei, dass die Anzahl der Verbindungsglieder einer Erweiterungsgruppe nicht unmittelbar am MT abgelesen werden kann, da Gelenke zu anderen Gliedern sowohl bei der Erweiterung um die Gruppe selbst als auch bei späteren Erweiterungen um fremde Gruppen entstehen können. Die Zerlegung muss daher Schritt für Schritt in umgekehrter Richtung zur Ableitung erfolgen.

Die zuletzt angehängte(n) AG(n) lassen sich dadurch finden, dass innerhalb des MTs nach Teilstrukturen gesucht wird, die selbst ein MT sind. Beim jeweiligen Rest handelt es sich laut Definition genau dann um eine AG, wenn sich die gefundene Teilstruktur nicht schrittweise über andere enthalten MTen auf den gesamten MT erweitern lässt. Gesucht werden könnte also nach der größten echten Teilstruktur, die ein MT ist. Diese kann mit Sicherheit nur noch auf den gesamten MT erweitert werden, der Rest ist also eine AG.

Anschließend wird das gleiche Verfahren mit dem gefundenen MT wiederholt. Auf diese Art kann man jeden MT Schritt für Schritt auf den Basistyp reduzieren und dabei alle enthaltenen AGn erfahren.

In algorithmischer Form sieht das für den MT M (verwendet als die Menge seiner Glieder) so aus: 

MRest := M
wiederhole
    gefundene AG A := keine
    für alle Teilmengen S von MRest\{Antrieb, Gestell} mit geradem 0<|S|<|MRest|-2
        n' := |MRest\S|
        k' := Anzahl der inneren Gelenke von MRest\S
        falls
            3(n'-1)-2k' = 1 und |S|<|A|
        dann
            A := S
    AG A gefunden
    MRest := MRest\A
bis |MRest| = 2

Ob ein Algorithmus praktikabel ist, entscheidet sich daran, ob er mit realistischen Ressourcen lauffähig ist. Bezüglich des Arbeitsspeichers gibt es hier keine Probleme: Keine der im Algorithmus vorkommenden Variablen benötigt einen Speicherplatz, der schneller als linear mit der Anzahl der Glieder des zu zerlegenden MT wächst - und diese Anzahl ist ja sehr niedrig. Bleibt die Frage nach der benötigten Rechenzeit. Dabei sind vor allem die Anweisungen in der inneren Schleife von Interesse, denn diese werden am häufigsten ausgeführt.

MRest\{Antrieb, Gestell} hat |MRest|-2 Elemente, also 2**(|MRest|-2) Teilmengen. Etwa die Hälfte davon haben eine gerade Mächtigkeit. Die innere Schleife wird also bei einem Durchlauf der äußeren Schleife etwa 2**(|MRest|-2)/2 mal ausgeführt. Allein beim ersten Durchlauf der äußeren Schleife sind das 2**(|M|-2)/2 mal. Der Algorithmus besitzt also ein exponentielles Laufzeitverhalten und würde trotz der relativ kleinen Werte für |M| - maximal 14 für diese Arbeit - eine nicht unerhebliche Rechenzeit in Anspruch nehmen. Das ist besonders dann ungünstig, wenn die Zerlegung in AGn innerhalb einer Suche unter den MTen benötigt wird - etwa, um solche mit einer bestimmten Eigenschaft zu finden - da sich die Laufzeit dann noch mit der Anzahl der MTen multipliziert. Überlegungen für eine Verbesserung der Laufzeit sind also angebracht.

Vor dem jeweils nächsten Durchlauf der inneren Schleife wird MRest um eine AG reduziert, verliert somit mindestens zwei Elemente, und 2**(|MRest|-2)/2 wird mindestens geviertelt. Selbst im ungünstigsten Fall dauert also der zweite Durchlauf der äußeren Schleife nur 1/4 so lange wie der erste, der dritte nur noch 1/16 usw. Der Großteil der für den Ablauf des gesamten Algorithmus benötigten Rechenzeit fällt im ersten Durchlauf an. Mit anderen Worten: Nachdem die zuletzt angefügte AG erkannt ist und entfernt wurde, ist der Restmechanismus so einfach, dass seine Untersuchung zeitlich kaum mehr ins Gewicht fällt. Der entscheidende Ansatzpunkt zur Beschleunigung des Algorithmus ist daher das Finden der ersten - also zuletzt angefügten - AG. Daran, wie schnell die erste Reduktion auf einen Restmechanismus erfolgen kann, hängt die Effizienz des gesamten Algorithmus.

Betrachtet man den Algorithmus unter diesem Gesichtspunkt, wünscht man sich vor allem, dass die innere Schleife gleich nach der ersten gefunden zwangläufigen Teilstruktur abgebrochen werden kann. Um das zu erreichen, müssen die Teilmengen S von MRest nur in der richtigen Reihenfolge durchsucht werden: von der kleinsten zur größten. Eine größere als die erste gefundene zwangläufige Teilstruktur kann es dann nicht geben.

2.3. Erkennen von Eigentlichkeit