Unter einem hybriden Suchverfahren wird die Kombination von look-back- und look-ahead-Strategien innerhalb eines Suchverfahrens verstanden. In wissenschaftlichen Veröffentlichungen (vgl. Bessière und Régin, 1996; Chen und van Beek, 2001; Haralick und Elliot, 1980; Grant und Smith, 1996; Prosser, 1995a,b,1993b,a) gibt es eine lang anhaltende Diskussion darüber, welche Kombination am besten geeignet ist, einfaches, chronologisches Backtracking zu erweitern und damit effizienter zu gestalten. Es sind eine ganze Reihe von Mischformen denkbar, in denen komplementäre look-back- und look-ahead-Erweiterungen in einem Algorithmus zusammengeführt werden können. Aber auch untereinander lassen sich z.B. look-back Verfahren kombinieren. So kann Backjumping relativ einfach um Backmarking zu einem Algorithmus BMJ bzw. BM-CBJ erweitert werden, so dass durch BJ bzw. CBJ trashing verhindert wird (insgesamt dadurch weniger Knoten im Constraint-Graphen durchlaufen werden müssen) und zusätzlich, bei den verbleibenden Knoten, die redundanten Konsistenztests durch BM vermieden werden (vgl. Prosser, 1993b, S. 281 ff.). Ferner lassen sich die bisher vorgestellten look-ahead-Strategien mit unterschiedlichen Backjumping-Varianten kombinieren. Allerdings verhalten sich look-back- und look-ahead-Strategien nicht vollständig orthogonal zueinander, sondern beeinflussen sich in ihrer Wirkungsweise gegenseitig. Je höher der während eines Suchvorgangs hergestellte Konsistenzgrad ist, umso weniger wirksam werden look-back-Strategien und umso mehr fällt deren in diesem Fall nutzloser Overhead ins Gewicht (vgl. Chen und van Beek, 2001, S. 62).
Prosser (1995a,1993a) stellt einen Algorithmus FC-BM vor, der Forward Checking mit Backmarking-Mechanismen kombiniert, wodurch sich der Suchaufwand weiter reduziert. Effizienter wirkt es sich allerdings aus, wenn anstatt eines chronologischen Backtrackers eine Backjumping-Variante zum Einsatz kommt. In der Tat bietet es sich an, Forward Checking zur Vermeidung von trashing grundsätzlich mit einem Backjumping-Verfahren zu kombinieren. Entsprechend wurde von Prosser (1993b, S. 289 f.) Forward Checking mit (konfliktbasiertem) Backjumping in dem Algorithmus FC-CBJ vereint. FC-CBJ kann ebenfalls wiederum um Backmarking erweitert werden (FC-BM-CBJ), was sich allerdings nach der empirischen Untersuchung von Prosser (1995a) weniger stark effizienzsteigernd auswirkt, und in seltenen Fällen, durch wechselseitige Beeinflussung der Verfahren, sogar zu einer Verschlechterung der Performanz führen kann.5.57
Aufgrund der empirisch ermittelten Ergebnisse von Prosser (1993b, S. 290 ff.) galt FC-CBJ anderen Kombinationen lange grundsätzlich als überlegen. Auch bei Güsgen (2000, S. 279 f.) findet sich die Aussage, dass die Herstellung eines höheren Konsistenzgrades für look-ahead-Verfahren aufgrund des erhöhten Aufwands i.A. nicht lohnt. Von Prosser (1995b) wird allerdings bereits in Anlehnung an Sabin und Freuder (1994b,a) dargelegt, dass mehr Constraint-Propagation durch hybride Verfahren, die während des Suchvorgangs höhere Grade lokaler Konsistenz herstellen, in Abhängigkeit von der Problemstellung zu einer effizienteren Suche führen kann. Um den von Sabin und Freuder (1994a) vorgestellten MAC-Algorithmus (der ebenso wie Forward Checking chronologisches Backtracking einsetzt) weiter zu verbessern, wird MAC von Prosser (1995b) daher um konfliktbasiertes Backjumping erweitert: MAC-CBJ. Wie von Grant und Smith (1996) dargelegt, profitiert MAC allerdings weniger als FC von einer look-back-Strategie. Da MAC den Lösungsraum stärker reduziert als FC, wird eine Backtracking-freie Suche über größere Regionen erlaubt, wodurch Backjumping seltener zum Einsatz kommt. Die Kombination von MAC mit CBJ hat demnach auf die meisten Suchvorgänge weniger Einfluss, garantiert allerdings eine stabile Performanz bei fast allen Problemstellungen.
Unter den Veröffentlichungen finden sich eine Reihe weiterer, z.T. kontroverser Studien zu dem Verhalten der Kombination MAC-CBJ, die sich an der Diskussion beteiligen, wie viel look-ahead letztendlich sinnvoll ist, bzw. ob bei dem entsprechendem look-ahead von MAC eine look-back-Strategie noch sinnvoll einsetzbar ist.5.58 So kann nach Bessière und Régin (1996, S. 72) die Erweiterung von MAC um CBJ nicht einfach als eine Verbesserung von MAC angesehen werden, wie CBJ für BT und FC-CBJ für FC. Die Ergebnisse der empirischen Untersuchung von Bessière und Régin (1996, S. 66 ff.) lassen annehmen, dass CBJ die Suche mittels MAC verlangsamt, da eine signifikante Anzahl Konsistenztests eingespart werden müsste, um den Overhead von CBJ aufzuwiegen. Die durch CBJ eingesparten Backtracking-Schritte und Konsistenztests reichen demnach allerdings i.A. nicht aus, diesen zusätzlichen Aufwand wieder wettzumachen. Stattdessen wird von Bessière und Régin (1996) empirisch gezeigt, dass durch Ausnutzung einer effizienten Reihenfolge der zu belegenden Variablen CBJ redundant wird (vgl. Abschnitt 5.2.5.1). Tatsächlich wird von Chen und van Beek (2001, S. 58 ff.) nachgewiesen, dass eine Variablenordnung existiert, so dass BT niemals mehr Knoten im Constraint-Graphen durchläuft als CBJ.5.59 Allerdings wird der Aussage von Bessière und Régin (1996, S. 72 f.) widersprochen, dass CBJ bei Verfahren, die während des Suchvorgangs Kantenkonsistenz herstellen, grundsätzlich sinnlos ist. So wird von Chen und van Beek (2001) neben dem theoretischen Nachweis, dass bei erhöhtem Konsistenzgrad während einer Backtracking-Suche grundsätzlich der Nutzen von Backjumping verringert wird, anhand einer Reihe von empirischen Untersuchungen auf Standardproblemen gezeigt, dass die Ergänzung von MAC um CBJ in der Lage ist, die Effizienz des Suchverfahrens um mehrere Größenordnungen zu verbessern.5.60
Abschließend muss festgestellt werden, dass es nicht das beste Lösungsverfahren bzw. eine optimale Kombination gibt, da es eben nicht das typische CSP gibt. Um herauszufinden, welches Lösungsverfahren sich für ein bestimmtes Problem besonders eignet, sind eine eingehende Evaluierung der bestehenden Untersuchungsergebnisse zu diesem Thema, die Analyse des konkreten Problems bzw. des Constraint-Netzes sowie u.U. eigene empirische Untersuchungen erforderlich. In Bezug auf ein Constraint-System, welches für unterschiedliche Problemstellungen eingesetzt werden soll, bedeutet dies, das unterschiedliche Lösungsalgorithmen angeboten werden sollten, die je nach Problemstellung flexibel eingesetzt werden können. Eine wichtige Rolle bzgl. der Effizienz eines Lösungsverfahrens spielt, wie bereits angedeutet, die Reihenfolge, in der Variablen mit Werten belegt werden und damit einhergehend die entsprechenden Heuristiken, die diese Reihenfolge generieren. Der nachfolgende Abschnitt befasst sich daher mit Variablen- und Werteordnungsheuristiken.