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)

   <math>\underbrace {\underbrace {\left(x_1 \vee x_3 \vee...\right)}_{k\; Variablen} \wedge \left( x_2 \vee x_4 \vee...\right)}_{m\;Klauseln}</math>

   for i in range (trials):    #Anzahl der Versuche
        #Bestimme eine Zufallsbelegung des <math>\{ x_i \}</math>:
        for j in range (steps):
              if <math>\{ x_i \}</math> erfüllt alle Klauseln: return <math>\{ x_i \}</math>
              #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 <math>k>2</math> : steps *trials <math>\in O\left(\Alpha^n \right) \Alpha >1</math>

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

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

---

-Zufallsbelegung hat <math>t\leq n</math> richtige Variablen (im Mittel <math>t\approx \frac {n} 2</math>)

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

<math>t\rightarrow t-1</math> mit Wahrscheinlichkeit <math>\frac 1 2</math>:: (für beliebiges k: <math>\frac {k-1} k</math>)

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

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

      Probe: <math>S\left(n\right)=n^2-n^2=0</math> 
                 
             <math>S\left(0\right) =n^2-0^2</math>  
             
                  <math>=S\left(1\right)+1</math>
             
                  <math>\;=n^2-1^2+1</math>
             
                  <math>\;=n^2</math>
             <math>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</math> 
             
                  <math>=\frac 1 2 n^2-\frac 1 2 \left( t^2-2t+1\right) + \frac 1 2 n^2-\frac 1 2</math>
             
                  <math>=\left(t^2+2t+1\right)</math>              
             
                  <math>\;=n^2-t^2</math>

Das ist das Random Walk Problem

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