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

Eigenschaft: falls $k>2$ : steps *trials $\in O\left(\Alpha^n \right) \Alpha >1$

z.B. $k=3$ steps=3*n, trials=$\left(\frac{4}3\right)^n$

aber: bei $k=2$ sind im Mittel nur steps=$O\left(n^2\right)$ nötig, trials=$O\left(1\right)$

---

-Zufallsbelegung hat $t\leq n$ richtige Variablen (im Mittel $t\approx \frac {n} 2$)

Negieren einer Variable ändert t um 1, u.Z. $t\rightarrow t+1$ mit Wahrscheinlichkeit $\frac 1 2$:: (für beliebiges k: $\frac 1 k$)

$t\rightarrow t-1$ mit Wahrscheinlichkeit $\frac 1 2$:: (für beliebiges k: $\frac {k-1} k$)

-Wieviele Schritte braucht man im Mittel, um zu einer Lösung mit t Richtigen zu kommen?

      $S\left(t\right)=\frac 1 2 S\left(t-1\right) + \frac 1 2 S\left(t+1\right) +1$
      
      $S\left(n\right)=0$    #Abbruchbedingung der Schleife
      $S\left(0\right) = S\left( 1\right) + 1 \Longrightarrow S\left(t\right) = n^2-t^2$