|
Bei der Partitionierung von Bäumen geht es darum, aus einem großen Baum
mehrere Teilbäume zu machen, indem man aus dem ursprünglichen Baum
mehrere Teilbäume zu machen, indem man aus dem ursprünglichen Baum
Kanten entfernt. Es wird jeweils eine Partition gesucht, die aus einer
vorgegebenen Anzahl von Teilbäumen besteht und ferner bezüglich allen
vorgegebenen Anzahl von Teilbäumen besteht und ferner bezüglich allen
möglichen Partitionen optimal ist. Ein Beispiel für eine mögliche
möglichen Partitionen optimal ist. Ein Beispiel für eine mögliche
möglichen Partitionen optimal ist. Ein Beispiel für eine mögliche
möglichen Partitionen optimal ist. Ein Beispiel für eine mögliche
Optimalitätsbedingung ist, das maximale Gewicht von Teilbäumen zu
minimieren. Als Gewichtsfunktion kommt prinzipiell jede Funktion in
Frage, die Teilbäumen jeweils eine reelle Zahl zuordnet. Bei
Shiftingalgorithmen sind allerdings Bedingungen an die
Gewichtsfunktionen zu stellen, damit ein Optimum erreicht wird.
Shiftingalgorithmen repräsentieren Partitionen durch Cuts auf den zu entfernenden Kanten. Anfangs werden diese Cuts alle auf die Kante der Wurzel gesetzt. Dann werden diese Cuts nacheinander nach unten geshiftet. Die Entscheidung, welcher Cut auf welche Kante zu shiften ist, erfolgt ausschließlich aufgrund lokaler Bedingungen. Diese garantieren trotz ihrer Lokalität, daß im Laufe des Algorithmuses eine optimale Partition erreicht wird. Literatur
|