Inhaltsverzeichnis
2.3. Erkennen von Eigentlichkeit
Inhaltsverzeichnis
2.3. Erkennen von Eigentlichkeit
In den Abschnitten 2.2. und 2.3. wurden brauchbare Algorithmen zur Analyse von MTen entwickelt. Dabei wurde auch auf eine gute Laufzeiteffizienz geachtet; effizientere Algorithmen zur Analyse eines einzelnen MTs wird es innerhalb dieser Arbeit nicht mehr geben. Trotzdem ist die Laufzeit der entwickelten Algorithmen nicht unerheblich; sie sind immer noch von exponentieller Komplexität. Das fällt besonders dann ins Gewicht, wenn eine große Menge an Typen untersucht werden soll.
In [1] wurde festgestellt, dass es sinnvoll ist, MTen bei Bedarf aus der zu Grunde liegenden kinematischen Kette durch Wahl von Gestell und Antrieb abzuleiten. Spätestens bei den 14-gliedrigen MTen ist das auch gar nicht anders möglich, denn ein Katalog existiert dort nicht. Ein auf diesem Prinzip basierender Algorithmus, der eine Untersuchung aller MTen vornimmt, würde nacheinander alle kinematischen Ketten betrachten und jeweils alle daraus ableitbaren MTen untersuchen. Dabei werden nacheinander alle aus einer gemeinsamen kinematischen Kette ableitbaren MTen einzeln untersucht.
An den Algorithmen zur Zerlegung in AGn und zur Bestimmung der Eigentlichkeit fällt unter diesem Aspekt auf, dass für MTen, die auf der gleichen kinematischen Kette basieren, gerade die für die Laufzeit kritischen Schleifen über alle Teilmengen des MTs weitgehend identisch ablaufen. Die numerischen Eigenschaften von Teilstrukturen, nach denen dort gesucht wird, sind von der Lage von Antrieb und Gestell unabhängig. Lediglich die Einschränkung, dass Teilmengen, die Antrieb oder Gestell enthalten, nicht untersucht werden müssen, da sie keine AGn sein können, führt zu Unterschieden innerhalb dieses Abschnitts.
Im Hinblick auf die Laufzeit könnte es vorteilhaft sein, die aufwändige Untersuchung der Teilmengen nur einmal pro kinematischer Kette vorzunehmen. Allerdings ist zu bedenken, dass eine solche allgemeine Untersuchung, obwohl auf dem gleichen Verfahren basierend, wesentlich zeitaufwändiger ist als die Untersuchung eines einzelnen MTs. Erstens können keine der Glieder mehr außen vor gelassen werden, denn Antrieb und Gestell stehen nicht fest. Schon allein dieser Umstand bewirkt etwa eine Vervierfachung der Laufzeit, da 2**|M|/2 Teilmengen zu untersuchen sind statt 2**(|M|-2)/2. Zweitens muss bei der Analyse der kinematischen Kette die Schleife über die Teilstrukturen wieder vollständig durchlaufen werden. Ein vorzeitiger Abbruch ist nicht mehr möglich, da die erste gefundene AG - welche auch immer das ist - nicht bei allen der auf der Kette basierenden MTen gültig sein muss, denn in diesen können Glieder aus der Gruppe als Gestell oder Antrieb gewählt sein.
Für eine kinematische Kette K sieht dieser Algorithmus so aus:
für alle Teilmengen S von K mit geradem 0<|S|<|K|-2
n' := |K\S|
k' := Anzahl der inneren Gelenke von K\S
falls
3(n'-1)-2k' = 1
dann
S markieren
|
Jede hier markierte Gliedergruppe besitzt die korrekte Anzahl an Gliedern, Gelenken und Verbindungsgliedern, um eine AG zu sein. In einem konkreten aus der Kette abgeleiteten Mechanismus kann sie aber nur dann auch tatsächlich als AG auftreten, wenn die dort als Gestell und Antrieb gewählten Glieder nicht in ihr enthalten sind. Außerdem muss noch die Unteilbarkeit der betreffenden Ableitung sicher gestellt werden. Wenn von den markierten Gliedergruppen alle entfernt würden, in denen mindestens eine andere markierte Gliedergruppe vollständig enthalten ist, wäre dieses Ziel erreicht. Dass dabei potenzielle AGn verloren gehen, ist ausgeschlossen, denn laut Satz 6 kann es in einer AG keine Unterstrukturen mit den numerischen Eigenschaften einer AG geben.
Im Anschluss an obigen Algorithmus werden also diejenigen markierten Gliedergruppen extrahiert, in denen keine andere der markierten Gliedergruppen vollständig enthalten ist. In den einzelnen aus der Kette abgeleiteten Mechanismen kann jetzt die zuletzt angefügte Assur-Gruppe sehr schnell gefunden werden: Jede der extrahierten Gliedergruppen, die weder Gestell noch Antrieb enthält, ist eine AG. Auf diese Art können zwar nur die Assur-Gruppen schnell gefunden werden, um die der abgeleitete MT zuletzt erweitert werden könnte - die restliche Zerlegung muss wie gewohnt nach dem Algorithmus aus Abschnitt 2.3. erfolgen. Wie dort aber schon festgestellt wurde, macht ja gerade das Finden der zuletzt angefügten AG den größten Zeitaufwand aus.
|
Beispiel 5:
werden durch den Algorithmus folgende Gliedergruppen markiert:
Anschließend für die spätere MTen-Analyse extrahiert werden davon nur die Gruppen 1 und 2. Nur diese können in einem aus der Kette abgeleiteten MT als letzte AG auftreten. |
Ein willkommener Nebeneffekt dieser Methode ist, dass zum Erkennen der Eigentlichkeit der einzelnen abgeleiteten MTen keine AGn-Zerlegung mehr notwendig ist. Alle zuletzt anfügbaren AGn wurden bestimmt - ein MT ist genau dann nicht eigentlich, wenn es für ihn mehrere gibt.
Abschließend ist noch zu bemerken, dass eine solche Untersuchung einer kinematischen Kette bezüglich der Gesamt-Rechenzeit beim Durchsuchen von MTen natürlich um so attraktiver wird, je mehr MTen sich aus ihr bilden lassen. (Wie in [1] ersichtlich, basieren auf den - bezüglich der Laufzeit besonders kritischen - 14-gliedrigen kinematischen Ketten im Durchschnitt 36 MTen.) Ob dieses Verfahren am Ende tatsächlich weniger Zeit in Anspruch nimmt als die einzelne Analyse aller MTen, kann an dieser Stelle nicht festgestellt werden. Daher werden beide Varianten implementiert.
