uni/algodat/report123/p2-fragestellungen.md

P2 Fragestellungen

Vergleiche

1. Die beiden resultierenden spannenden Bäume wurden in der Visualisierung so angeordnet, um ihre Gleichheit sofort ersichtlich zu machen. Intuitiv lässt sich auch schon sagen, dass der spannende Baum vermutlich minimal ist, da alle Kantengewichte kleiner als die Gewichte unausgewählter Kanten sind. Die Korrektheit ergibt sich, wenn beispielsweise Prim händisch durchgespielt wird.

1. Der Graph small, sparse, Prim 55 (55) ist ein Teilgraph von dem Graphen small, dense, Prim 118 (118). Das bedeutet, alle Knoten und Kanten aus 55 finden sich in 118 wieder. Es lässt sich leicht erkennen, dass der dichtere der beiden Graphen, nämlich 118, für dieselbe Knotenzahl mehr Kanten aufweist. Allgemein sagt man ist ein Graph dünn (licht), wenn die Anzahl der Kanten in der Größenordnung der Knoten sich befinden, daher $m = O(n)$. Bei zu vielen Verbindungen zwischen Knoten lässt sich das nicht mehr sagen, der Graph wird dicht, daher $m = \Theta(n^2)$. Zwar sind dieselben Kanten aus 55 in 118 vorhanden, aber neuere Kanten mit geringeren Gewichten haben dazu geführt, dass der spannende Baum anders aufgebaut ist. Die Korrektheit lässt sich bei 118 auf dieselbe Art und Weise argumentieren.

Prim Vergleiche

Durch die Implementierung des Prim Algorithmus mithilfe eines binären Heaps (Min-Heap), befindet sich die Laufzeitkomplexität bei einem $O(m*log(n))$. Diese quasi-polynomielle Laufzeit stellt den worst-case dar, wobei gar nicht erst berücksichtigt ist, dass irrelevante Knoten ausgelassen werden und effektiv wegfallen. Wenn $m$ sich in der Größenordnung von $n$ befindet, d.h. der Graph is licht, $m = O(n)$, dann ergibt sich eine Laufzeit, welche nicht einmal quadratisch ist. Wenn aber $m$ sich in der Größenordnung von $n^2$ befindet, ist das Endresultat eine Laufzeit, welche $n^2$ als untere Schranke aufweist, d.h. $m*log(n) = \Omega(n^2)$.

Diese dramatischen Unterschiede in Laufzeitkomplexität spiegeln sich sehr wohl in Observationen wieder, wie in Fig.1 ersichtlich ist.

Kruskal Vergleiche

Kanonisch fällt der Aufwand bei Kruskal Algorithmen an die Sortierung der Eingabegröße, sodass der tatsächlich algorithmische Teil für das Finden eines minimalen spannenden Baumes in linearer Zeit möglich wird, mit entsprechenden Optimierungen. Der initiale Aufwand des Sortierens liegt außerhalb des Problembereiches für die Programmieraufgabe, also wird diese außer Acht gelassen.

Besonders wichtig hier ist zu beachten, dass die x-Achse durch die Anzahl der Knoten gekennzeichnet wird, nicht durch die Kanten. Der erste Teil der Implementierung initialisiert die Sets für die Union-Find Datenstruktur, mit einer Laufzeit von $\Theta(n)$. Anschließend werden unabhängig davon die geordneten Kanten iteriert, wobei Kanten zwischen irrelevanten Knoten ausgelassen werden. Innerhalb der dafür zuständigen Schleife werden die Set-Repräsentanten der zu gerade betrachtenden beiden Knoten gesucht, mithilfe von findset(v). Zwar besitzt findset(v) in der Form in der sie implementiert ist eine theoretische worst-case Laufzeit von $O(n)$, aber dass genau $n$ Schritte durchgeführt werden müssen tritt erst auf, nachdem $n-1$ Kanten aufgenommen worden sind. Da zu Beginn jeder Knoten sein eigener Repräsentant ist, muss erst begonnen werden, einen minimal spannenden Baum aufzubauen. Erst wenn alle Knoten vereint sind, also ein minmal spannender Baum mit $|V_T| = n$ besteht, für jeden Knoten ein Aufwand von $n$ für findset(v). Da aber der Algorithmus terminiert werden kann, sobald $|E_T| = n-1$, ist das nie der Fall.

Bei dichten Graphen existieren redundante Verbindungen zwischen zwei beliebigen Knoten. Wenn diese aber geringe Gewichte aufweisen, werden diese in der Sortierung bevorzugt und müssen abgearbeitet werden. Da sich im Plot nur die Laufzeitunterschiede bei variierenden Knotenzahlen ersichtlich machen, ist es schwer, den Unterschied lichter und dichter Graphen am Plot zu charakterisieren. Durch die redundanten Verbindungen dichter Graphen werden aber im Allgemeinen mehr Kanten überprüft, was dem sprunghaften Unterschied einen Charakter geben kann. Wie ersichtlich steigt mit der Anzahl relevanter Knoten die Laufzeit nur minimalst, da für jeden weiteren Knoten nur einige zusätzliche Kanten überprüft werden müssen, bevor der Algorithmus terminiert. Zwar lassen sich schwer erklärliche Artefakte im Plot erkennen, aber die ersichtlichen Trends deuten auf eine erwartungsgemäße lineare Laufzeit (in Hinsicht auf Anzahl relevanter Knoten).

Prim vs. Kruskal

Werden die Ergebnisse von Prim und Kruskal für large, dense Graphen gegenübergestellt, lassen sich in der Laufzeit beider Algorithmen starke Unterschiede erkennen. Wie bereits observiert, wächst die Laufzeit von Prim polynomiell mit Respekt zur Anzahl relevanter Knoten, während bei Kruskal die Laufzeit lediglich linear wächst. Wie bereits diskutiert fällt die hauptsächliche Laufzeitkomplexität bei Kruskal auf die initielle Sortieroperation, welche für den Rahmen dieser Aufgabenstellung wegfällt. Diesen Luxus haben wir bei Prim nicht, wodurch wir uns mit der eigentlich zu Stande kommenden Komplexität von $O(n*log(m))$ zufrieden geben müssen.