WS 2006-07

Algorithmentheorie

03 – Randomisierung(Closest Pair)

Prof. Dr. Th. Ottmann

2 WS 2006-07

Randomisierung

• Klassen von randomisierten Algorithmen• Randomisierter Quicksort• Randomisierter Algorithmus für Closest Pair• Randomisierter Primzahltest• Exkurs: Kryptographie

3 WS 2006-07

Klassen von randomisierten Algorithmen

• Las Vegas Algorithmen

immer korrekt; erwartete Laufzeit

Beispiel: randomisierter Quicksort

• Monte Carlo Algorithmen (mostly correct):

wahrscheinlich korrekt; garantierte Laufzeit

Beispiel: randomisierter Primzahltest

4 WS 2006-07

Das Closest Pair Problem

Gegeben:

Menge von n Punkten in der Ebene

Gesucht: die zwei Punkte mit geringstem Abstand zueinander

5 WS 2006-07

Ansätze

Naiver Ansatz:

Berechne für jedes Paar von Punkten den jeweiligen Abstand und wähle das Paar mit minimalem Abstand.

Laufzeit: O(n2 )

Divide-and-Conquer Ansatz:

vgl. frühere Vorlesung

Laufzeit: O(n log n)

6 WS 2006-07

Zielsetzung

Entwerfe Las-Vegas-Typ Algorithmus mit erwarteter Laufzeit O(n).

Idee: Verbessere Laufzeit mit Hilfe von Input Randomisierung und Implementation von Dictionaries durch universelles Hashing.

Unterscheide zwischen Operationen an Dictionaries und anderen.

Konstruiere Algorithmus, der O(n) Distanzberechnungen und Lookup Operationen ausführt und zusätzlich eine erwartete Anzahl von O(n) MakeDictionary- und Einfüge-Operationen.

Also: Zweifache Verwendung von Randomisierung:

1. Reihenfolge der Punkte

2. Universelles Hashing

7 WS 2006-07

Notationen

Menge der Punkte: P = {p1, ..., pn}, wobei pi = (xi , yi )

euklidischer Abstand: d (pi , pj )

OBdA: alle Punkte liegen im Einheitsquadrat, d.h. i = 1, ..., n : 0 ≤ xi, yi < 1

8 WS 2006-07

Die Idee

betrachte die n Punkte in zufälliger Reihenfolge p1 , ..., pn und merke jeweils = min{d(pi , pj )}, d.h. beginne mit = d(p1 , p2 )

für jeden neuen Punkt pi prüfe, ob „in der Nähe“ von pi einer der bereits betrachteten Punkte p1, ..., pi-1 in einer geringeren Entfernung als von pi entfernt liegt

falls ja, muss aktualisiert werden

Problem: Was heißt „in der Nähe“ von pi ?

9 WS 2006-07

Inkrementeller Algorithmus

Ordne Punkte in zufälliger Reihenfolge p1 , ..., pn .

Algorithmus geht stufenweise (mit jeweils festem δ) vor: Beginne mit dem closest pair (p1 , p2 ) und = d(p1 , p2).

Ziel in jeder Stufe ist es, entweder zu verifizieren, dass tatsächlich der kleinste Abstand ist, oder ein neues Paar (pi , pj) mit d(pi , pj ) < zu finden.

In jeder Stufe werden Punkte der Reihenfolge nach betrachtet.

Sobald ein Punkt pi erreicht wird, so dass für ein j < i d(pi , pj ) < gilt, springe zur nächsten Stufe.

Setze = minj :j <i {d(pi , pj )}

Wird der letzte Punkt erreicht, so ist der Algorithmus fertig und das nach Betrachtung dieses Punktes ist der tatsächliche minimale Abstand.

10 WS 2006-07

Überlegungen

Offensichtlich terminiert der Algorithmus.

Die Anzahl der benötigten Schritte hängt stark von der Reihenfolge der Punkte ab:

Im besten Fall, wenn p1 und p2 bereits das closest pair sind, wird nur eine Stufe benötigt.

Im schlimmsten Fall wird für jeden Punkt geändert und man benötigt n - 2 Stufen.

Wir werden sehen, dass die erwartete Laufzeit des Algorithmus (für eine zufällig gewählte Reihenfolge der n Punkte) nur um einen konstanten Faktor von der Laufzeit im besten Fall abweicht.

11 WS 2006-07

Der Trick (1)

Hauptteil des Algorithmus ist der Test, ob ein closest pair erhalten bleibt, wenn ein neuer Punkt hinzugefügt wird.

Dazu müssen Abstände zwischen dem neuen Punkt und den bereits vorhandenen berechnet werden, für welche?

Hilfsmittel: Unterteile das Einheitsquadrat in kleinere Quadrate der Seitenlänge /2.

N2 Teilquadrate mit N =

• Für 0 ≤ s ≤ N-1 und 1 ≤ t ≤ N-1 definieren wir das Teilquadrat

Sst := {(x,y ) : s/2 ≤ x < (s+1)/2; t/2 ≤ y < (t+1)/2}

/2

12 WS 2006-07

Rasterung

13 WS 2006-07

Der Trick (2)

2 Vorteile:

1. Für zwei Punkte p, q im gleichen Teilquadrat gilt: d (p, q) < δ

2. Gilt für zwei Punkte d (p, q) < δ, so liegen sie ”nahe“ beisammen, d.h. höchstens 2 Quadrate entfernt.

14 WS 2006-07

Der Trick (3)

Beweis:(1) Jeweils die x- als auch die y-Koordinaten der beiden Punkte

unterscheiden sich um höchstens δ /2.

(2) Seien p und q in Quadraten, die nicht „nahe“ beisammen liegen, p Sst und q Ss ' t ' mit || s - s' || > 2 oder || t - t' || > 2.

in der x- oder y-Koordinate unterscheiden sich p und q um mindestens δ, also kann nicht d(p, q) δ sein.

222 22 /)/()/(),( qpd

15 WS 2006-07

Für einen beliebigen Punkt p liegen also alle Punkte q mit d (p, q) < in einem 5 mal 5 Felder großen Gitter um das Quadrat Sst , in dem p liegt.

”in der Nähe“ von p

16 WS 2006-07

closest pair-Test

Idee:

Merke zu jedem Punkt das Quadrat Sst , in dem er sich befindet.

(Speichere dazu alle Punkte in einem von δ abhängigen Dictionary.) Für jeden neuen Punkt pi : Bestimme das Quadrat, in dem er sich

befindet. Überprüfe die höchsten 25 „nahen“ Quadrate auf andere Punkte.

Dabei kann man wegen Vorteil 2 höchstens 25 Punkte finden. Zu jedem solchen Punkt: Berechne den Abstand zu pi.

Falls kein Abstand kleiner als ist, bleibt unverändert und pi wird gespeichert (zusammen mit Sst ).

17 WS 2006-07

δ-abhängiges Dictionary zur Speicherung von Punkten

Anfragemöglichkeiten:

Gegeben s, t: Finde Sst und stelle fest,ob überhaupt und ggfs.welchen Punkt Sst

enthält.

Gegeben p = (px, py):Finde das Feld Sst,das p enthält.

18 WS 2006-07

Hash-Tabellen

Wie kann pi - zusammen mit Sst - effizient gespeichert werden?

• Verwende Wörterbuch (Dictionary, z.B. als Hash-Tabelle implementiert).

• Benutze s, t als 2-dimensionalen Index (Schlüssel) zur Bestimmung des Quadrate Sst .

• Wird geändert, so werden die Hash-Tabelle und alle δ-abhängigen Quadrate Sst nutzlos und wir brauchen eine neue Hash-Tabelle für neue Quadrate der Kantenlänge ‘/2.

• Für jeden Punkt, der bisher betrachtet wurde, wird sein neues Quadrat berechnet und in die neue Hash-Tabelle eingefügt.

• Danach wird mit dem nächsten Punkt in der zufälligen Reihenfolge fortgefahren.

19 WS 2006-07

Kosten vonMakeDictionaryfür ein gegebenes δund Einfügeneiner Menge voni Punkten in dasDictionary:

MakeDictionary - Operation

20 WS 2006-07

Zusammenfassung des Algorithmus

ordne die Punkte in einer zufälligen Reihenfolge p1,...,pnsei = minimale (bisher gefundene) Distanzinitialisiere = d(p1, p2)MakeDictionary für Quadrate der Kantenlänge /2for i = 1, 2, ..., n :

finde das Quadrat Sst im aktuellen Dictionary, das pi enthält;finde die 25 nahen Quadrate von pi;berechne die Abstände von pi zu jedem Punkt in diesen Quadraten;if ein Punkt pj mit (j < i) und ´ = d(pj, pi) < existiert, dann:

lösche aktuelles Dictionary (die aktuelle hash-table)MakeDictionary für Quadrate der Kantenlänge ´/2for jeden Punkt p {p1, ..., pi}: finde das Quadrat der Kantenlänge ´/2, das den Punkt p enthält füge p in das Quadrat im Dictionary (in die neue hash-table) einendfor

elsefüge pi (zusammen mit Sst) in aktuelles Dictionary (die aktuelle hash-table) einendif

endfor

21 WS 2006-07

Laufzeitanalyse (1)

Für jeden neuen Punkt pi werden nur konstant viele Suche Operationen benötigt,ebenso nur konstant viele Abstandsberechnungen.Insgesamt höchstens O(n) viele MakeDictionary-Operationen.

Satz: Der randomisierte Closest-Pair Algorithmus liefert das korrekte Ergebnis und führt für eine Menge von n Punkten höchstens O(n) Distanzberechnungen, O(n) Finde-Operationen und O(n) MakeDictionary Operationen aus.

Es fehlt noch:Erwartungswert der Gesamtlaufzeit des Algorithmus unter

Berücksichtigung der Einfügungen in neue Dictionaries, wenn das closest pair geändert wird.

22 WS 2006-07

Laufzeitanalyse (2)

Behauptung: Die erwartete Anzahl für alle benötigten Einfüge-Operationen ist in

O(n)

Beweis:

Sei X = Zufallsvariable für Anzahl der Einfüge-Operationen

gesucht: E(X )

Sei Xi Zufallsvariable mit Wert 1, wenn der i -te Punkt in der zufälligen Reihenfolge ein Update von d erzwingt, 0 sonst.

Lemma 1:

Die Gesamtanzahl von Einfüge-Operationen ist höchstens

iiiXn

23 WS 2006-07

Laufzeitanalyse (3)

Lemma 2: P[Xi = 1] ≤ 2/i

Beweis:Betrachte die i ersten Punkte p1, ..., pi in der zufälligen Reihenfolge.

Sei = d(p, q) der minimale Abstand unter diesen Punkten.

pi kann nur dann eine Änderung des minimalen Abstands erzwingen, wenn pi = p oder pi = q

da die ersten i Punkte in zufälliger Reihenfolge angeordnet sind, ist jeder von ihnen mit gleicher Wahrscheinlichkeit der letzte

die Wahrscheinlichkeit, dass entweder p oder q letzter Punkt ist, ist demnach also 2/i

24 WS 2006-07

Laufzeitanalyse (4)

Lemma 1: Die Gesamtanzahl von Einfüge-Operationen ist höchstens

Lemma 2: P[Xi = 1] ≤ 2/i

Folgerung: Der Erwartungwert für die Gesamtzahl aller Einfüge

Operationen in Dictionaries ist in O(n).

i iiXn

nnn

n

iin

XEin

XE

n

i

n

i

n

i i

32

2

)/2(

])[(

][

1

1

1

25 WS 2006-07

Zusammenfassung der Laufzeitanalyse des randomisierten inkrementellen Algorithmus

Für eine zufällig gewählte Folge von n Punkten kann man erwarten, dass der Algorithmus ausführt:

O(n) Finde-Operationen

O(n) Distanzberechnungen

O(n) MakeDictionary-Operationen

O(n) Einfüge-Operationen

Gesamtlaufzeit hängt ab von der Implementation der Dictionaries, Möglichkeiten:

Hashtabellen, Universal Hashing: Erwartete Gesamtlaufzteit O(n)

Dynamische Tabellen, balanzierte Bäume: O(n log n) (im worst case!)

26 WS 2006-07

Zusammenfassung

• Mittels Randomisierung lässt sich zur Lösung des Closetst-Pair-Problems eine erwartete Laufzeit von O(n) erreichen.

Wichtigste Ideen:

Inkrementeller Algorithmus mit Input Randomisierung Gitteraufteilung des Universums, aus dem die Punkte stammen Universelles Hashing

27 WS 2006-07

Kleinberg, Jon M.; Tardos, Éva: Algorithm Design, Addison Wesley, 2005

Ottmann, Thomas; Widmayer, Peter: Algorithmen und Datenstrukturen, Spektrum, 2002

Smid, Michiel: Closest-Point Problems in Computational Geometry, Universität Magdeburg, 1997

http://citeseer.ist.psu.edu/167339.html

Kirkpatrick, David: Fundamentals of Algorithm Design and Analysis, Universitiy of British Columbia, 2005 http://www.cs.ubc.ca/ romanh/courses/cpsc500/lectures/L03- 0920.pdf

Literatur