Ich habe einen Wald, dh Knoten mit gerichteten Kanten und keinen Zyklen (gerichtet oder ungerichtet). Ich definiere die Höhe eines Scheitelpunkts als 0, wenn er keine eingehenden Kanten hat, oder die maximale Anzahl von Kanten, die umgekehrt verfahren werden müssen, um einen Scheitelpunkt der Höhe 0 zu erreichen.
Ich weiß auch, dass der durchschnittliche Grad eines Knotens eine kleine Konstante ist, etwa 2 oder so. Um die Höhe aller Eckpunkte zu ermitteln, kann ich mir zwei Algorithmen vorstellen:
Gehalgorithmus
- Gehen Sie durch und markieren Sie für Eckpunkte ohne eingehende Kanten.
Grenzalgorithmus
- Wiederholen Sie 2, bis sich nichts mehr hinter der Grenze befindet.
Meine Fragen:
- Gibt es einen Namen für dieses Problem und eine bekannte schnellste Lösung?
quelle
Ich weiß nicht, ob dieses Problem einen offiziellen Namen hat oder nicht. Ihr Titel fasst es gut genug zusammen. Das Aufsteigen von den Knoten mit der Höhe 0 ist schnell, vorausgesetzt, Sie vermeiden Doppelarbeit. Angenommen, Sie haben einen Knoten mit vielen untergeordneten Elementen und einen langen Pfad über diesem Knoten zur Wurzel. Angenommen, die Höhen der einzelnen Kinder sind unterschiedlich. Jedes Kind kann die Höhe des betreffenden Knotens aktualisieren. Das ist ok. Sie sollten jedoch vermeiden, auch den langen Pfad über diesem Knoten zu aktualisieren, bis alle untergeordneten Knoten ihre Höhen gemeldet haben.
Der resultierende Algorithmus wird in linearer Zeit ausgeführt, und der Pseudocode würde ungefähr so aussehen:
quelle
Ein Problem, das so ähnlich ist, dass es von Interesse sein könnte, ist "Paralleles Präfix für gerootete gerichtete Bäume". Der Algorithmus ermittelt die Anzahl der Kanten zur Wurzel von jedem Knoten. Die Wurzeln haben also den Wert 0, während beispielsweise der untere rechte Knoten den Wert zwei hat.
Beachten Sie, dass der folgende Algorithmus das allgemeinere Problem für gewichtete Kanten löst, Sie jedoch einfach W (i) für alle i auf 1 initialisieren können. Und der Nachfolger jedes Knotens i ist gegeben durch P (i) = j.
Das Bild unten zeigt die "Halbierung" der Pfadlängen und macht die logarithmische Laufzeit leicht verständlich. Die berechneten Knotenhöhen werden jedoch nicht angezeigt.
(aus "Einführung in parallele Algorithmen" von Joseph Jaja).
Bei Verwendung mehrerer Prozessoren ist es in O (lg n) -Zeit lösbar, verwendet jedoch O (n lg n) -Operationen. Es gibt einen Hack, um es auf lineare Arbeit zu bringen, aber es ist leicht involviert.
quelle
S(i)
?