Randomisierte Algorithmen: Difference between revisions
From Alda
Jump to navigationJump to search
Line 31: | Line 31: | ||
Negieren einer Variable ändert t um 1, | 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>) | 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>) | ::::::::::::<math>t\rightarrow t-1</math> mit Wahrscheinlichkeit <math>\frac 1 2</math>:: (für beliebiges k: <math>\frac {k-1} k</math>) |
Revision as of 16:11, 3 July 2008
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>)