This flashcard is just one of a free flashcard set. See all flashcards!

Die Idee des BaB-Algo ist, Teilbäume von der Suche auszuschließen, wenn der Mindestabstand dieses Teilbaums
Eingabedaten sind ein Referenzpunkt p und ein Startknoten im Baum T.
Es wird eine obereGrenze mitgeführt (am Anfang unendlich), und eine Referenz auf den nächsten Nachbarn NN.

Nun wird T nach der lb-Distanz aufsteigend sortiert. Die lb-Distanz ist die kleinste quadratische Distanz zwischen Punkt und Cluster. Nun über sortiertes T iterieren:
Ist k aus T ein Blatt, so wird für jeden Punkt p aus k geprüft, ob die Distanz kleiner als obereGrenze ist. Falls ja: obereGrenze auf dist(k), NN=p.
Wenn k kein Blatt ist, wird geprüft, ob die kleinstmöglichste Distanz von q zu k größer ist als obereGrenze. Falls ja, wird der Knoten ignoriert, ansonsten wird BaB rekursiv auf k aufgerufen.