Upload
diederick-eckermann
View
106
Download
2
Embed Size (px)
Citation preview
SpezialvorlesungSuchalgorithmen
Thema: Einzelzustandsraumsuche
Stefan Edelkamp
Struktur des Buchs
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Heuristikenh konsistent 0 ≤ w(u,v) + h(v) – h(u)
h zulässig h(u) ≤ h*(u)
Satz: Konsistenz impliziert Zulässigkeit
Beweis: Sei p = (s=v0,…vk=t) beliebiger Pfad
h(u) ≤ h*(u)
Graphabstraktion durch Knotenkontraktion
Additiv: Nicht-Additiv:
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Dijkstra´s Kürzeste Wege Algorithmus
Auswahl: u mit f(u) = min { f(v) | v ist in Open }
Update: f(v) = min { f(v), f(u) + w(u,v) | v ist Nachfolger von u }
Initialisierung: f(s) = 0, f(u) = unendlich, falls u <> s
A* = Dijkstra + Neubewertung der Kantengewichte
h konsistent 0 ≤ w(u,v) + h(v) – h(u)
neues Kantengewicht nicht negativ
Auswahl: u mit f(u) = min { f(v) | v ist in Open }
Update: f(v) = min { f(v), f(u) + w(u,v) +h(v) – h(u) |
v ist Nachfolger von u }
Initialisierung: f(s) = h(s), f(u) = unendlich, falls u <> s
Vor- und nach der Neubewertung der Kantengewichte
Problem: Negative Kantengewichte Wiederöffnung bereits expandierter Knoten
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Datenstrukturen (1): Vorrangwarteschlangen
Neu in 2005: Relaxed Weak Queues (Katajainen, Elmasry. Jensen): Insert/DecreaseKey: O(1) und DeleteMin O(log n) worst-case mit „einfacher“ Datenstruktur als Fibonacci-Heaps!
Weak-Heaps
Merging zweier WHs:
Relaxierte Weak-Queues
(Heap-geordneter) Bin-baum == Perfekter (balancierter) WH
Binomialqueue: Dualdarstellungsanordnung von Bin-bäumen
Weak-Queue: Dualdarstellungsanordnung von WHs
Relaxierte Weak-Queue: Liste von WHs nahe
Dualdarstellungsanordnung + wenige Anordnungsfehler
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Datenstrukturen (2):Hash-Tabellen
Neu in 2003: Cuckoo Hashing (Pagh et al.):
Insert: O(1) amortisiert und Lookup O(1) worst-case mit „einfacher“ Datenstruktur!
Cuckoo-Hashing
Problem: Rehash der gesamten Tabelle
Einfügen:
Suffix-Lists
Bit-State Hashing
Single Bit-State Double Bit-State
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
DFID und IDA*
DFID (depth-first iterative-deepening): simuliert die Breitensuche mit stetig
ansteigender Kostenschranke: f(n) = g(n) IDA* (iterative-deepening A*) simuliert A* mit stetig ansteigender
Kostenschranke f(u)=g(u)+h(u)
Analyse IDA*
Anzahl erwarteter Knoten, die von IDA* bis zur Kostenschranke cin einem Suchbaum mit Ni Knoten in Tiefe i expandiert werden
Anomalie Tiefensuche + Tiefenschranke
Wiederöffnung bereits expandierter Knoten
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Frontier-Suche (1):Genutzte Operatoren
Frontier-Suche (2):Munagala & Ranade
A
t t+1
t+2
BCD
XYZAX
AXYZ
XYZ
I: Lösche Duplikate in aktuell generierter BFS-Schicht
II: Subtrahiere BFS-Schichten t und t+1 von t+2.
Überblick
Heuristiken und Graphabstraktionen Verbindung Dijkstra und A* Datenstrukturen
Vorrangwarteschlangen (State-of-the-Art) Hash-Tabellen (State-of-the-Art)
Speicherplatzbeschränkte Suche DFID + IDA*, Anomalie Frontier-Suche BFHS + Lokalität
Breadth-First Heuristic Search