Ziel dieses Verfahrens ist es ,eine globale Lösung eines CSP´s zu finden, jedoch ohne die Trägheit des asynchronen Backtracking. Betrachtet man den Suchbaum des Asynchronous Backtracking, fällt auf, daß falsche Entscheidungen/Belegungen in einem frühen Stadium erst nach einer vollständigen Enumeration des restlichen Suchraumes, also sehr spät, revidiert werden. Bei dem Weak Commitment Search Algorithmus, der hier vorgestellt wird, soll dieses Problem durch eine schwache Bindung an die derzeitige partielle Lösung behoben werden. Bei diesem Verfahren wird jede Variable zu Beginn mit einem Wert aus ihrer Domain initialisiert. Jede Variable gehört genau einer Menge an. Die eine Menge repräsentiert eine partielle Lösung und enthält die Variablen, deren Belegung fest gebunden ist, die andere Menge enthält die ungebundenen Variablen deren Belegung noch variabel ist. Beide Mengen sind disjunkt zueinander und zu Beginn ist die Menge der gebundenen Variablen leer.

Eine ungebundene, initialisierte Variable, wird zu einer gebundenen Variablen, wenn sie die partielle Lösung erweitert. Verletzt die Belegung der gewählten Variablen ein Constraint zu einer gebundenen Variablen, wird versucht, eine neue, gültige Belegung nach der min-conflict Heuristik zu finden. Das heißt, daß die neue Belegung möglichst wenige Constraints zu ungebundenen Variablen verletzen darf.

Sollte keine konsistente Belegung gefunden werden können, kann die derzeitige partielle Lösung nicht Teil einer globalen Lösung sein und es werden die bisher gewählten Belegungen der gebundenen Variablen als neues Constraint in das System aufgenommen, um zu verhindern, daß diese Situation erneut eintreten kann. Anschließend wird die gesamte partielle Lösung verworfen und die Menge der gebundenen Variablen ist erneut leer. Die Belegung der Variablen wird als neue Initialisierung beibehalten und von neuem wird versucht, eine partielle Lösung schrittweise zu einer globalen Lösung zu erweitern. Die Vollständigkeit dieses Algorithmus ist leicht nachzuweisen.

Das Charakteristische dieses Verfahrens lässt sich in folgenden Punkten zusammenfassen:

• Die Min-Conflict-Heuristik dient als Value-Ordering-Heuristik innerhalb einer Domain.

• Eine partielle Lösung wird verworfen und der Suchprozess erneut gestartet, wenn keine konsistente Belegung für die aktuell betrachtete Variable existiert.