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)
for i in range (trials): #Anzahl der Versuche
#Bestimme eine Zufallsbelegung des :
for j in range (steps):
if erfüllt alle Klauseln: return
#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 : steps *trials
z.B. steps=3*n, trials=
aber: bei sind im Mittel nur steps= nötig, trials=
-Zufallsbelegung hat richtige Variablen (im Mittel )
Negieren einer Variable ändert t um 1,
u.Z. mit Wahrscheinlichkeit ::(für beliebiges k: )
mit Wahrscheinlichkeit ::(für beliebiges k: )
-Wieviele Schritte braucht man im Mittel, um zu einer Lösung mit t Richtigen zu kommen?
#Abbruchbedingung der Schleife
Probe:
Das ist das Random Walk Problem
Im ungünstigsten Fall (t=0) werden im Mittel Schritte benötigt, um durch random walk nach t=n zu gelangen.
2. RANSAC-ALGORITHMUS (Random Sample Consensus)
Aufgabe: gegeben: Datenpunkte
gesucht: Modell, das die Datenpunkte erklärt
Messpunkte:
übliche Lösung: Methode der kleinsten Quadrate
Schulmathematik:
Lineares Gleichungssystem
Problem: der Datenpunkte sind Outlier
Einfaches Anpassen des Modells an die Datenpunkte funktioniert nicht
Seien mindestens k Datenpunkte notwendig, um das Programm anpassen zu können
RANSAC-Algorithmus
for l in range (trials):
wähle zufällig k Punkte aus
passe das Modell an die k Punkte an
zähle, wieviele Punkte in der Nähe des Modells liegen (d.h. muss geschickt gewählt werden)
#Bsp. Geradenfinden:-wähle a,b aus zwei Punkten
-berechne:
-zähle Punkt i als Inlier, falls
return: Modell mit höchster Zahl der Inlier
mit k=Anzahl der Datenpunkte und p=Erfolgswahrscheinlichkeit, =Outlier-Anteil
Erfolgswahrscheinlichkeit: p=99%
Ein Spiel: Wie viel Schritte braucht man im Mittel zum Ziel?
geg.: 5 Plätze, 2 Personen: eine Person rückt vom einem Platz zu dem enderen Platz;
die zweite Person wirft die Münze.
Wenn die Münze auf Kopf landet, rücke nach rechts und wenn die Münze auf Zahl landet, rücke nach links.
<--- Zahl Kopf-->
Kopf: /////
Zahl: ///
=> mit 8 Schritten bis zum Ziel
im Mittel: bei N Plätzen braucht man N2 Schritte
all: mit N2 Schritten um N Plätze rücken
Wie viel Schritte braucht man im Mittel zum Ziel?
#wenn wir uns im Stuhl Nr.1 befinden
#bei 0.Platz
Lösung:
speziell:
#wenn man am ungünstigsten Platz startet
Beziehung zu randomisiertem 2-SAT
"Platz ": Variablen haben den richtigen Wert, sind falsch gesetzt
# Anfangszustand
Las Vegas vs. Monte Carlo
* Las Vegas - Algorithmen
- Ergebnis ist immer korrekt.
- Berechnung ist mit hoher Wahrscheinlichkeit effizient (d.h. Randomisierung macht den ungünstigsten Fall unwahrscheinlich).
* Monte Carlo - Algorithmen
- Berechnung immer effizient.
- Ergebnis mit hoher Wahrscheinlichkeit korrekt (falls kein effizienter Algorithmus bekannt, der immer die richtige Lösung liefert).
Las Vegas
Monte Carlo
- Erzeugen einer perfekten Hashfuktion
- Algorithmus von Freiwald(Matrizenmultiplikation)
- universelles Hashing
- RANSAC
- Quick Sort mit zufälliger Wahl des Pivot-Elements
- randomisierte K-SAT(k>=3)(Alg. von Schöning)
- Treep mit zufälligen Prioritäten
-
Zufallszahlen
- kann man nicht mit deterministischen Computern erzeugen
- aber man kann Pseudo-Zufallszahlen erzeugen, die viele Eigenschaften von echten Zufallszahlen haben
* sehr ähnlich zum Hash
"linear Conguential Random number generator"
-sorgfältige Wahl von a, c, m notwendig
Bsp. m = 232
a = 1664525, c = 1013904223
"quick and dirty generator"
Nachteile
nicht zufällig genug für viele Anwendungen
Bsp. wähle Punkt in R3
gibt Zahl u, v, w so, dass
stark geclustert ist.
Periodenlänge ist zu kurz:
spätestens nach m Schritten wiederholt sich die Folge
allgemein: falls der interne Zustand des Zufallsgenerators k bits hat, ist Periodenlänge:
lowbits sind weniger zufällig als die highbits
Mersenne Twister
bester zur Zeit bekannter Zufallszahlengenerator (ZZG)
innere Zustand:
Periodenlänge:
Punkte aus aufeinanderfolgende Zufallszahlen in sind gleich verteilt bis
alle Bits sind unabhängig voneinander zufällig ("Twister")
schnell
class Random:
def __init__(self, seed):
self.N = 624
self.state = [0]*624
self.state = zufällig mit Hilfe des seeds initialisieren (einfacher ZZG)
self.i = 0 # zählt mit in welchem Zustand wir gerade aufhalten
def __call__(self):
N,M = 624, 397
i = self.i
r = (self.state[i] & 0x80000000)|(self.state[(i+1)%N] & 0x7FFFFFFF) # aktualisieren
if self.state[(i+1)%N]&1: # des Zustands
r^= 0x9908B0DF
self.state[i] = self.state[(i+1)%N]*^r
y = self.state[i]
self.i = (self.i + 1)%N
# bits verwürfeln
y ^= (y>>11)
y ^= ((y>>7) & 0x9D2C5680)
y ^= ((y>>15) & 0xEFC60000)
y ^= (y>>18)
return y
geg.: Zufallszahl
ges.: Zufallszahl
naive Lösung: ist schlecht.
Bsp.
rand()
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
rand()%k
0
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
=> 0,...,n kommt doppelt so häufig wie 5,...,10 "nicht zufällig"
Lösung: Zurückweisen des Rests der Zahlen (rejektion sampling)
r = rand()
while r > last.GoodValue:
r = rand()
return r%k