4.4 Vergleich

In Versuchen mit Netzwerken hat Yokoo synchrone, asynchrone und asynchrone weak commitment search Verfahren gegenübergestellt und auf Beispiele mit starker und auch schwacher Vernetzung angewandt. Das Ergebnis besagt, daß bei starker Vernetzung des Constraint-Graphen der Asynchronous Backtracking Algorithmus keinen Geschwindigkeits-gewinn im Vergleich zu dem einfachen, synchronen Backtracking Algorithmus erzielt. Auch hat sich gezeigt, daß sich beide Verfahren kritisch verhalten in Bezug auf die Wahl der initialen Belegungen.

Anders der Asynchronous Weak Commitment Search Algorithmus. Dieser ist unempfindlich gegenüber schlecht gewählter Initialisierung und er kann durch seine dynamischen Ränge früh getroffene, falsche Entscheidungen schneller revidieren und damit weitaus größere Problemstellungen lösen.

Wir haben bewußt versucht uns auf dem Weg der Statistiken der einzelnen Algorithmen nicht zu verfangen, da wir zum einen selbst keine Messungen durchführen konnten, zum anderen die von diversen Autoren erwähnten Zahlen nicht immer große Aussagekraft besitzen. So heißt z.B. eine Vergrößerung des Suchraums nicht unbedingt eine Vergrößerung des Rechenaufwands, denn mit der Vergrößerung des Suchraumes auch die Anzahl der möglichen Lösungen vergrößert werden kann (für den Fall, daß nur eine Lösung gesucht wird). Daher macht ein Vergleich der verschiedenen Strategien in verschieden Suchräumen wenig Sinn.

Zurückblickend können wir sagen, daß es nach wie vor, keine generell überlegenen DCSP Algorithmen gibt, obwohl gerade auf dem Gebiet der variablenbasierten Algorithmen große Fortschritte zu verzeichnen sind. Die Wahl eines passenden Algorithmus für eine konkretes Problem muß jedoch nach wie vor problemabhängig getroffen werden.

1. M. Yokoo, "The Distributed Constraint Satisfaction Problem: Formalization and Algorithms", IEEE Trans. On Knowledge and DATA engineering, vol. 10, No.5 September 1998

2. Chandy and L. Lamport, "Distributed snapshots: determining global states of distributed systems", ACM Trans. On ComputerSystems, vol. 3 no. 1, pp. 63-75, 1985

3. Q.Y. Luo, P.G: Hendry, J.T. Buchanan "Heuristic Search For Distributed Constraint Satisfaction Problems, Department of CS, University of Strathclyde, Glasgow, Research Report KEG-6-93, 5.02.93