Inhaltsverzeichnis
Basisalgorithmus und Typencodes
Inhaltsverzeichnis
Basisalgorithmus und Typencodes
Die Implementierung erfolgt für den PC unter dem Betriebssystem MS-DOS, zunächst steht also die Wahl zwischen Real- und Protected Mode. Ich entscheide mich für den (schnelleren) Real-Mode. Hier steht ein fortlaufender Hauptspeicher von 640 kByte (abzüglich Programmcode und Betriebssystem) zur Verfügung, der zum größten Teil zum Speichern der Typen verwendet werden kann. Für die Codes der vierzehngliedrigen Mechanismen werden 61 Bit pro Typ benötigt, daher empfiehlt sich die Verwendung eines 8-Byte Datentyps. Um einen schnellen Zugriff zu erreichen, organisiere ich den Typenspeicher als binären Baum. Dadurch entsteht ein zusätzlicher Speicherplatzbedarf von zwei 2-Byte Zeigern pro abgespeichertem Typ. Insgesamt faßt der Typenspeicher also keinesfalls mehr als 600.000 Byte / 12 Byte = 50.000 Typen.
Das ist leider zu wenig, um bei allen gestellten Problemen alle Typen darin aufnehmen zu können. Eine erste Entlastung entsteht durch die vorgenommene Einschränkung des Suchraumes: Da die verschiedenen Gelenkverteilungen nacheinander untersucht werden und nur Typen mit der gleichen Gelenkverteilung identisch sein können, müssen für den Test auf redundante Typen nur die Typen der aktuell untersuchten Verteilung bereit stehen. Ist eine Gelenkverteilung vollständig betrachtet, können die dazu ermittelten Typen auf den Massenspeicher ausgelagert werden.
Möglicherweise reicht diese Einsparung des benötigten Speichers aber nicht aus (der Verdacht wird sich zur Laufzeit bestätigen). Deshalb ist ein Mechanismus zur temporären Auslagerung von Typen auf den Massenspeicher vorzusehen. Statt einen neu gefundenen Typen mit allen schon vorhandenen Typen der gleichen Gelenkverteilung zu vergleichen, wird nun nur noch die Identität mit den im Hauptspeicher liegenden Typen geprüft. Die dadurch zwangsläufig entstehenden Redundanzen werden bei der nächsten Auslagerung durch Mischen mit den bisher ausgelagerten Typen beseitigt. Die Auslagerung muß demnach sortiert erfolgen.
Beim Aufspannen des Suchraumes sorgen zwei kleine Tricks für eine Beschleunigung des Verfahrens. Für die in ihrer Anzahl durch die Gelenkverteilung festgelegten Gelenke werden hier in verschachtelten Schleifen alle Möglichkeiten durchsucht. Der erste Trick vergleicht nachfolgende Schleifendurchläufe. Sollten die dabei für ein Gelenk ausgewählten Glieder gleichartig sein, kann der spätere Durchlauf entfallen, da er die selben Typen hervorbringen würde. Der zweite Trick ist eine Abkürzung des aufwendigen Tests auf starre Unterstrukturen. Strukturen, die starre Ketten aus genau drei Gliedern enthalten, werden nämlich erst gar nicht erzeugt.
Um mit dem gleichen Programm auch Assur-Gruppen berechnen zu können, müssen deren abweichende Eigenschaften - also die äußeren Gelenke, die es ja bei Ketten und Mechanismen nicht gibt - in das vorhandene Schema gezwungen werden. Ich erreiche das durch Einführen eines zusätzlichen, nicht vertauschbaren Gliedes, mit dem alle äußeren Gelenke verbunden sind. Dieses Glied ist eine Art von Gestell und erhält im Programm die Nummer 0. Im Programm muß also bei der Berechnung von Assur-Gruppen eine um 1 erhöhte Anzahl von Gliedern angegeben werden. Welche Ungleichungen müssen nun geprüft werden, um starre Substrukuren und enthaltene Assur-Gruppen auszuschließen? Für das erste Problem müssen grundsätzlich zwei Fälle unterschieden werden:
Fall 1: Die geprüfte Substruktur enthält nicht das Gestell
Hier läßt sich die Zwanglaufgleichung direkt anwenden. Wie bisher gilt:
k' ≤ 3n'/2 - 2
Fall 2: Die geprüfte Substruktur enthält das Gestell
Wie in der Modellierung leite ich hier die Zwanglaufbedingung aus einer Erweiterung der gesamten Struktur zur kinematischen Kette mit einem Freiheitsgrad ab. Das Gestell wird dabei durch ein zusätzliches Gelenk in zwei Glieder zerlegt. Nach dieser Transformation, in der die geprüfte Substruktur um ein Gelenk und ein Glied wächst, muß sie mindestens einen Freiheitsgrad besitzen:
f' ≥ 1
3((n'+1)-1) - 2(k'+1) ≥ 1
3n' -2k' ≥ 3
k' ≤ 3n'/2 - 3/2
Das zweite Problem - der Test auf enthaltene Assur-Gruppen - erfordert eigentlich zusätzliche Vorbereitung. Denn die hier zu prüfende Anzahl von Gelenken zählt auch die äußeren Gelenke der Substruktur mit. Dieser Aufwand läßt sich jedoch vermeiden. Neben den inneren und äußeren Gelenken einer Substruktur gibt es nur noch die Gelenke, die an keinem ihrer Glieder beteiligt sind. Das sind aber gerade die inneren Gelenke der komplementären Substruktur, die genau aus den in der geprüften Substruktur nicht enthaltenen Gliedern der gesamten Struktur gebildet wird. Die Anzahl dieser Gelenke - aus der sich durch Subtraktion von der gesamten Anzahl an Gelenken die für den hier vorzunehmenden Test notwendige Anzahl von Gelenken unmittelbar berechnen läßt - wird bei der Überprüfung der komplementären Substruktur ermittelt. An dieser Stelle kann also auch getestet werden, ob die hier zu prüfende Substruktur eine Assur-Gruppe ist. Da jede Substruktur eine komplementäre Substruktur besitzt, wird auf diese Weise auch keine enthaltene Assur-Gruppe übersehen. Sind n'' und k'' die Kenngrößen der komplementären Substruktur, dann gilt:
n' + n'' = n (das Gestell werde in n mitgezählt)
k = 3(n-1)/2
k - k'' ≠ 3n'/2 (geprüfte Teilkette soll keine Assur-Gruppe sein)
k'' ≠ k - 3n'/2
k'' ≠ 3(n-1)/2 - 3(n-n'')/2
k'' ≠ 3n''/2 - 3/2
Nur Teilketten, die das (eigentlich ja nicht vorhandene) Gestell nicht enthalten, können Assur- Gruppen sein. Deren komplementäre Teilketten sind genau die, die das Gestell enthalten - die eben gefundene Bedingung ergänzt also den oben betrachteten Fall 2. Die beiden Ungleichungen können zusammengefaßt werden zu:
k' < 3n'/2 - 3/2
Da auf beiden Seiten Vielfache von 1/2 stehen, gilt:
k' ≤ 3n'/2 - 3/2 - 1/2
k' ≤ 3n'/2 - 2
Das ist die gleiche Bedingung wie in Fall 1 und auch die gleiche wie für die Substrukturen von Ketten und Mechanismen. Der betreffende Programmabschnitt braucht also überhaupt keine Fälle zu unterscheiden. Der gleiche Test sichert die Abwesenheit sowohl starrer Teilketten als auch innerer Assur-Gruppen - letzteres aber wiederum nur, wenn die gesamte Struktur eine Assur-Gruppe ist. Zu beachten ist lediglich, daß bei den Assur-Gruppen alle Substrukturen geprüft werden müssen, statt nur derer mit ungerader Anzahl von Gliedern.
Das Programm löst nun jede der gestellten Aufgaben (aber nicht jede effizient, mehr dazu später). Dazu muß es nur zur Übersetzungszeit an das jeweilige Problem angepaßt werden. Die Anzahl n der Glieder wird in einer Konstanten festgelegt, die Anzahlen k der Gelenke und s der nicht vertauschbaren Gliedern in jeweils einer Konstanten und einer Compilerbedingung. Der Name der Katalogdatei kann frei gewählt werden.
Weitere Details der Implementierung können dem (kommentierten) Quelltext des Programms entnommen werden. (Download)
[nicht übertragen]
