Randomisierte Algorithmen

1. 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$

      Probe: $S\left(n\right)=n^2-n^2=0$ 
                 
             $S\left(0\right) =n^2-0^2$  
             
                  $=S\left(1\right)+1$
             
                  $\;=n^2-1^2+1$
             
                  $\;=n^2$
             $S\left(t\right)=\frac 1 2 \left(n^2-\left(t-1\right)^2\right) + \frac 1 2 \left(n^2-\left(t+1\right)^2\right)+1$ 
             
                  $=\frac 1 2 n^2-\frac 1 2 \left( t^2-2t+1\right) + \frac 1 2 n^2-\frac 1 2$
             
                  $=\left(t^2+2t+1\right)$              
             
                  $\;=n^2-t^2$

Das ist das Random Walk Problem

Im ungünstigsten Fall (t=0) werden im Mittel $n^2$ Schritte benötigt, um durch random walk nach t=n zu gelangen.