Lösen von diskreten CSP

TL;DR

CSP's mit endlichen Domänen lassen sich mit einer Backtracking-Suche lösen. Dabei wird schrittweise eine Variablen ausgewählt und dann ein Wert aus deren Wertebereich für die Belegung ausgewählt. Danach ruft sich die Backtracking-Suche rekursiv auf. Falls dabei keine Lösung gefunden werden kann, erfolgt Backtracking und die Belegung wird schließlich rückgängig gemacht und durch die nächste Möglichkeit ersetzt.

Videos (YouTube)
Videos (HSBI-Medienportal)
Lernziele
  • (K3) Lösung von CSP mit endlichen Domänen mit Hilfe der BT-Suche

Einfärben von Landkarten als CSP

Endliche Domänen: Formulierung als Suchproblem

def BT_Search(assignment, csp):
    if complete(assignment): return assignment

    var = VARIABLES(csp, assignment)

    for value in VALUES(csp, var):
        if consistent(value, var, assignment, csp):
            assignment += {var = value}

            if INFERENCE(csp, assignment, var) != failure:
                result = BT_Search(assignment, csp)
                if result != failure: return result

            assignment -= {var = value}

    return failure

Quelle: Eigener Code basierend auf einer Idee nach [Russell2020, p. 176, fig. 5.5]

Hierbei handelt es sich um eine etwas angepasste Tiefensuche: Starte mit leerem Assignment und weise schrittweise Variablen passende Werte zu und mache notfalls Backtracking.

BT-Suche für CSP am Beispiel Landkartenfärbeproblem

Wrap-Up

  • Lösung von CSP mit endlichen Domänen mit Hilfe der Backtracking-Suche
Übungsblätter/Aufgaben
Quellen
  • [Bartak2001] Theory and Practice of Constraint Propagation
    Barták, R., 2001.
  • [Kumar1992] Algorithms for Constraint Satisfaction Problems: A Survey
    Kumar, V., 1992.
  • [Russell2020] Artificial Intelligence: A Modern Approach
    Russell, S. und Norvig, P., Pearson, 2020. ISBN 978-0134610993.
    CSP, Backtracking: Abschnitt 5.3