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(\mathrm {A} ^{n}\right)\mathrm {A} >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}$