2.2 Domainbasiertes DPS

Wie in der Abbildung 1 zu sehen ist, gibt es bei diesem CSP drei Variablen V₁, V₂ und V₃, die die Position der entsprechenden Damen in der jeweiligen Spalte wiedergeben. Der Suchraum wird auf die Agenten (Prozessoren) P_1-3 verteilt, so daß jeder einen eindeutigen, mit anderen disjunkten, Untersuchraum kriegt. Das passiert in dem man die Domain (Menge der Werte) der Variable V₁ auf die einzelnen Agenten aufteilt. Die drei Agenten kriegen demnach jeweils einen Untersuchraum mit V_i = d_1i und müssen nun entsprechende Belegungen für die Variablen V₂ und V₃ finden. Zum Lösen des DCSP können innerhalb jedes Agenten sequentielle Algorithmen eingesetzt werden, d.h. auch alle bekannten Heuristiken etc. eingesetzt werden.

Der eindeutige Vorteil der domainbasierten Algorithmen liegt darin, daß sie einen Zeitgewinn mit Sicherheit garantieren. Im schlimmsten Fall ist der Zeitaufwand gleich dem eines sequentiellen Algorithmus (zzgl. eines kleinen Overheads für die Aufteilung des Suchraums), denn zumindest ein Agent wird dem Pfad des sequentiellen Algorithmus folgen (unter der Voraussetzung, daß jeweils der gleiche Algorithmus eingesetzt wird).

Der Nachteil der domainbasierten Algorithmen besteht darin, daß es keine Kommunikation zwischen den Prozessoren gibt. Hat ein Prozessor ein zusätzliches Constraint ermittelt, oder eine Belegung für eine Variable gefunden, bei der keine Lösung möglich ist, so kann er diese Erkenntnisse nicht den anderen Agenten mitteilen. Jeder Agent muß diese Erkenntnisse selbst gewinnen, d.h. die Agenten verrichten zum Teil redundante Arbeit.

Obwohl im Beispiel nur eine Variable verteilt ist (bzw. die Domain nur einer Variable) ist eine weitere Verteilung der resultierenden Untersuchräume möglich.

Beim funktionsbasierten DPS (Abb. 2) geht es darum, die parallele Verarbeitung, die auf den Mehrprozessorsystemen möglich ist, optimal auszunutzen. Dabei wird nicht der Suchraum sondern die Arbeit über mehrere Prozessoren verteilt. In der Abbildung sehen wir, daß der Vater - Prozeß (P1) zwei neue Kinder - Prozesse (P2, P3) startet, und die Arbeit zwischen diesen aufteilt. Man kann funktionsbasiertes DPS auch zum Kombinieren mehrerer Algorithmen benutzen (z.B. domain-filtering und forward-checking) um die vorhanden physischen Prozessoren maximal auszunutzen.

Für die Implementierung solcher Algorithmen sind Mehrprozessorsysteme mit shared - memory notwendig. Allerdings ist der Einsatz von solchen Systemen nur bei großen Problemen anwendbar, da der Aufwand für die Erstellung neuer Prozesse relativ groß ist.