Randomisierte Algorithmen

Randomisierte Algorithmen

Def.: Algorithmen, die bei Entscheidung oder bei der Wahl der Parameter Zufallszahlen benutzen

Bsp.: Lösen des K-SAT-Problems durch RA

   geg.: logischer Ausdruck in K-CNF (n Variablen, m Klauseln, k Variablen pro Klausel)

   $\underbrace {\underbrace {\left(x_{1}\vee x_{3}\vee ...\right)} _{k\;Variablen}\wedge \left(x_{2}\vee x_{4}\vee ...\right)} _{m\;Klauseln}$

   for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des $\{x_{i}\}$:
        for j in range (steps):
              if $\{x_{i}\}$ erfüllt alle Klauseln: return $\{x_{i}\}$
              #wähle zufällig eine Klausel, die nicht erfüllt ist und negiere zufällig eine der Variablen in dieser Klausel (die Klausel ist jetzt erfüllt)
   return None