next up previous contents index
Nächste Seite: 5.2.6 Behandlung von höherwertigen Aufwärts: 5.2.5 Heuristiken zur Variablen- Vorherige Seite: 5.2.5.1 Variablenordnungsheuristiken   Inhalt   Index

5.2.5.2 Werteordnungsheuristiken

Nachdem eine Variable zur Belegung ausgewählt wurde, stehen zumeist mehrere Belegungsmöglichkeiten im Wertebereich zur Auswahl. Die Aufgabe von Werteordnungsheuristiken ist es, hiervon einen Wert auszuwählen und somit insgesamt eine Reihenfolge zu generieren, in der die Variable mit Werten belegt wird. Da diese Werteordnung die Reihenfolge vorgibt, in der während des Suchvorgangs in die Äste des Suchbaums verzweigt wird, sind Werteordnungsheuristiken in der Lage, ebenfalls beträchtlich die Effizienz des Suchvorgangs zu beeinflussen

Während Variablenordnungsheuristiken darum bemüht sind, kritische Variablen möglichst frühzeitig mit einem Wert zu belegen (engl. most critical variables first), verfolgen Werteordnungsheuristiken, auch look-ahead value ordering (LVO) genannt (vgl. Bessière und Régin, 1996; Frost und Dechter, 1995), das gegenteilige Prinzip: Sie versuchen zur Vermeidung von Backtracking Werte auszuwählen, die möglichst zur einer konsistenten Belegung aller Variablen führen (engl. most promising values first) (vgl. Ruttkay, 1998, S. 13). Wenn zuerst Zweige im Suchbaum durchsucht werden, deren Wahrscheinlichkeit zu einer konsistenten Lösung zu führen größer ist als die anderer, kann hierdurch eine erste Lösung früher aufgefunden werden. Werteordnungsheuristiken haben allerdings i.A. keinen Einfluss auf die Effizienz eines Suchverfahrens, wenn alle Lösungen für das CSP gesucht werden sollen, bzw. wenn es für das CSP keine Lösung gibt, da in diesen Fällen alle Werte berücksichtigt werden müssen (vgl. Dechter und Frost, 1998; Tsang, 1993; Dechter und Frost, 2002; Russel und Norvig, 2002; Barták, 2003).5.68

Ein häufig angewendetes Vorgehen nach dem least-constraining-value-Prinzip zur Einschätzung, wie vielversprechend mögliche Werte zur Belegung einer Variable für das Auffinden einer konsistenten Lösung sind, ist die min-conflicts-Heuristik (MC). Der Wert, der die wenigsten Konflikte mit den Werten von noch unbelegten Variablen aufweist und damit die meisten zukünftigen Belegungsmöglichkeiten offen hält, ist demnach derjenige, mit dem die aktuelle Variable zuerst belegt werden sollte. Je weniger Konflikte ein Wert mit potentiellen Belegungen von noch unbelegten Variablen aufweist, umso weiter vorn wird er in der Werteordnung eingereiht (vgl. Minton et al., 1992).

Andere Strategien zur Werteauswahl beruhen auf der Annahme, dass ein Teilproblem eher eine konsistente Lösung aufweist, wenn es keine Variablen mit Wertebereichen umfasst, die nur einen oder sehr wenige Werte beinhalten (vgl. Frost und Dechter, 1995, S. 574). Die max-domain-size-Heuristik (MD) bevorzugt demnach Werte, die den größten minimalen Wertebereich für zukünftig zu belegende Variablen garantieren. Eine Erweiterung ist die weighted-max-domain-size-Heuristik (WMD), die in Fällen von gleich großen minimalen Wertebereichen den Wert auswählt, der weniger Variablen mit dem minimalen Wertebereich erzeugt. Somit werden in Konfliktfällen mehr Variablen mit größeren Wertebereichen ermöglicht, anstatt eine zufällige Auswahl vorzunehmen.

Die letzte hier erwähnte Werteordnungsheuristik ist die point-domain-size-Heuristik (PDS), die Punkte für jeden Wert der aktuell zu belegenden Variable vergibt (vgl. Frost und Dechter, 1995, S. 575). So können z.B. 8 Punkte für jeden zukünftigen Wertebereich mit nur einem Element, 4 Punkte für zukünftige Wertebereiche mit nur 2 Elementen, 2 Punkte für zukünftige Wertebereiche mit 3 Elementen und 1 Punkt für zukünftige Wertebereiche mit 4 Elementen vergeben werden. Der Wert, der die geringste Punktsumme aufweist, wird demnach von der Heuristik als erstes zur Belegung der aktuellen Variable ausgewählt.

Frost und Dechter (1995) untersuchen experimentell die genannten LVOs und zeigen die besondere Effizienz der min-conflicts-Heuristik in Form von FC-CBJ-dom+deg-mc auf. Die Anwendung der MC-Heuristik verhält sich demnach ähnlich dem look-ahead von FC. Da FC inkonsistente Werte (temporär) aus den Wertebereichen zukünftig zu belegender Variablen entfernt, kann es auch als einfache Form von Werteordnung betrachtet werden (vgl. Frost und Dechter, 1995, S. 572). MC hingegen ordnet auch die Werte entsprechend ihrer Konflikte, die Teil einer Lösung sein können und ist so gesehen eine weitergehende Form von look-ahead. Analog werden von Bessière und Régin (1996) zur Effizienzsteigerung die Kombinationen MAC-dom+deg-mc bzw. MAC-dom/deg-mc erfolgreich eingesetzt.

Werteordnungsheuristiken sind stark problemabhängig und weit weniger häufig vertreten als Variablenordnungsheuristiken (vgl. Güsgen, 2000, S. 278). Da es u.U. sehr viele Konsistenztests erfordert, um festzustellen welche Werte geeigneter sind als andere zu einer konsistenten Lösung beizutragen, lohnt sich dieser Overhead für gewöhnlich bei einfachen Problemen nicht. Der Einsatz kann allerdings bei sehr umfangreichen CSPs das Auffinden einer ersten Lösung stark beschleunigen. Je mehr Variablen ein CSP umfasst, umso lohnenswerter ist demnach der Einsatz von LVO, und je kleiner die Wertebereiche der Variablen sind, umso mehr Variablen sind notwendig, um den Overhead von Werteordnungsheuristiken aufzuwiegen (vgl. Frost und Dechter, 1995, S. 575 u. 578).



Fußnoten

...5.68
Für den speziellen Fall, dass ein BJ-Suchverfahren zum Einsatz kommt, wird von Frost und Dechter (1995, S. 577) gezeigt, dass LVO helfen kann die Unerfüllbarkeit eines CSPs zu ermitteln. Konsistente Teillösungen können hier effizienter ermittelt und ggf. durch BJ übersprungen werden.

next up previous contents index
Nächste Seite: 5.2.6 Behandlung von höherwertigen Aufwärts: 5.2.5 Heuristiken zur Variablen- Vorherige Seite: 5.2.5.1 Variablenordnungsheuristiken   Inhalt   Index