Randomisierte Algorithmen: Difference between revisions
(Link zum nächsten Thema hinzugefügt) |
m (→1. Randomisierte Algorithmen: Formet) |
||
Line 40: | Line 40: | ||
<math>S\left(n\right)=0</math> #Abbruchbedingung der Schleife | <math>S\left(n\right)=0</math> #Abbruchbedingung der Schleife | ||
<math>S\left(0\right) = S\left( 1\right) + 1 \ | <math>S\left(0\right) = S\left( 1\right) + 1 \Rightarrow S\left(t\right) = n^2-t^2</math> | ||
'''Probe:''' <math>S\left(n\right)=n^2-n^2=0 | '''Probe:''' | ||
<math> | |||
\begin{align} | |||
S\left(n\right) & = n^2-n^2=0 \\ | |||
S\left(0\right) &= n^2-0^2 \\ | |||
&= S\left(1\right)+1 \\ | |||
&= n^2-1^2+1 \\ | |||
&= n^2 \\ | |||
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 \\ | |||
&= \frac 1 2 n^2-\frac 1 2 \left( t^2-2t+1\right) + \frac 1 2 n^2-\frac 1 2 \left(t^2+2t+1\right) + 1 \\ | |||
&= n^2-t^2 | |||
\end{align}</math> | |||
Revision as of 09:22, 14 August 2010
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)
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"
- Bsp. m = 232
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