Randomisierte Algorithmen: Difference between revisions
From Alda
Jump to navigationJump to search
| Line 10: | Line 10: | ||
for i in range (trials): #Anzahl der Versuche | for i in range (trials): #Anzahl der Versuche | ||
#Bestimme eine Zufallsbelegung des <math>\{ x_i \}</math>: | #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 | |||
Revision as of 15:56, 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
