Skip to content

Latest commit

 

History

History
100 lines (71 loc) · 2.63 KB

csp2-backtrackingsearch.md

File metadata and controls

100 lines (71 loc) · 2.63 KB
Raw
archetype title author readings tldr outcomes assignments youtube fhmedia
lecture-cg
Lösen von diskreten CSP
Carsten Gips (HSBI)
key comment
Russell2020
CSP, Backtracking: Abschnitt 5.3
key
Kumar1992
key
Bartak2001
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.
k3
Lösung von CSP mit endlichen Domänen mit Hilfe der BT-Suche
topic
sheet-csp
link name
VL BT-Suche für CSP

Einfärben von Landkarten als CSP

{width="80%"}

[[Tafelbeispiel: Suche nach Lösung]{.bsp}]{.slides}

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]]{.origin}

::: notes 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

::::::::: slides :::::: columns ::: {.column width="40%"} ::: ::: {.column width="60%"} ::: :::::: :::::::::

::::::::: notes {width="80%"} :::::::::

Wrap-Up

  • Lösung von CSP mit endlichen Domänen mit Hilfe der Backtracking-Suche

::: slides

LICENSE

Unless otherwise noted, this work is licensed under CC BY-SA 4.0. :::