LCA N-ary Tree
-
@Jester
Die Frage ist: wie markiert man die Knoten non-intrusive und in O(1)?@SeppJ
Man sollte auf ~ 4x (Tiefenunterschied LCA <-> Knoten) Vergleiche runterkommen. Ähnlich wiestd::vectorresizen tut.
Ich hoffe das ist für dich verständlich und gleichzeitig ausreichend wenig konkret
-
hustbaer schrieb:
@Jester
Die Frage ist: wie markiert man die Knoten non-intrusive und in O(1)?Ist das wirklich die Frage? Wo steht die denn?
-
Naja sag mir wo/wie du aus der Aufgabenstellung rausliest dass du was in den Nodes ändern kannst.
So wie ich das verstehe wird ausschliesslich mit IDs gearbeitet.
Also non-intrusive.
Und dass das Markieren O(1) gehen muss sollte mMn. auch klar sein. Weil sonst ja bloss alles langsamer wird.
-
Wenn du so willst, dann sag doch mal wo du was von IDs siehst und wo steht eigentlich, dass man zwei knoten effizient miteinander vergleiche kann. :p
Ich denke es ist vollkommen natürlich davon auszugehen, dass man das alles darf. Das kann meinetwegen auch über ein voralloziertes Array mit timestamps gehen. Algorithmen leben nunmal nicht im luftleeren Raum und ggf. Muss man halt seine Datenstrukturen geeignet entwerfen. Es macht ja auch keiner Kürzeste-Wege-Suche auf ner Kantenliste.
-
Jester schrieb:
Wenn du so willst, dann sag doch mal wo du was von IDs siehst und wo steht eigentlich, dass man zwei knoten effizient miteinander vergleiche kann. :p
Zumindest der Root-Knoten wird über eine ID identifiziert:
AlgorithTheMan schrieb:
For an N-ary Tree find the nearest common ancestor.
Given: rootid and a function which finds and returns the immediate parent of a node.Da sich in der Angabe sonst nichts zum Thema wie Nodes gehandhabt werden befindet, bin ich also davon ausgegangen dass da generell mit IDs gearbeitet wird.
Jester schrieb:
Ich denke es ist vollkommen natürlich davon auszugehen, dass man das alles darf.
Ich denke das kommt auf den Dozenten drauf an. Es gibt da immer wieder Spezialisten die recht eigene Vorstellungen davon haben was man vollkommen natürlich annehmen darf und was nicht.
-
aber mal losgelöst.von schrulligen Dozenten ist das was ich da ruagelesen habe das was geschätzte 95% aller Algorithmiker da rauslesen würden.
Wenn man mal davon ausgeht, dass die Knotenids von 0 bis n-1 gehen, kann man das Problem mit einem zuvor initialisierten Array lösen. Und wenn man keine Zeit zum Vorinitialisieren kriegt, dann kann man noch den folgenden Trick spielen: man legt zwei Arrays der Größe n an, initialisiert den speicher aber nicht. Außerdem braucht man einen Zähler für die anzahl der verwendeten Einträge. Die beiden Arrays nennen wir mark und init.
Die Idee ist folgende: wenn ein Eintrag in mark[id] gültig ist (der knoten also markiert ist), dann ist sein Inhalt ein Index in Init. In dem Fall ist der entsprechende Eintrag von init wieder id, verweist also auf die Speicherstelle, die es als initialisiert bestätigt. Wenn wir abfragen wollen ob ein Eintrag mark[id] gültig ist, dann schaun wir zunächst ob mark[id] < anzahl der initialisierten Einträge ist (0-basierte Arrays). Ist das nicht der Fall, so zeigt der Einzrag auf keinen sinnvollen Eintrag von init ist damit nicht initialisiert. Anderenfalls schauen wir den entsprechenden Eintrag von init an. Dieser ist dann geeignet befüllt und bestätigt die Initialisierung von mark[id] (wenn init[mark[id]] = id) oder eben nicht. Um einen Eintrag von mark zu initialisieren, lassen die entsprechenden felder von init und mark aufeinander verweisen (mark[id] = counter, init[counter] = id) und erhöhnen anschließend den zähler um 1.
Jnd nun sehen wir auch, warum man normalerweise einfach gewisse Grundannahmen wie Markierbarkeit von Knoten macht: man beschäftigt aich sonst mit einem Haufen Kleinkram der mit dem eigentlichen Problem so gut wie nix zu tun hat.
-
Und was machst du bei der nächsten Anfrage?
-
Vorher den Zähler wieder auf 0 setzen.
Oder meinst Du im allgemeinen Fall, wenn ich einfach Markierbarkeit annehme? Dann führ ich noch eine Liste mit in die alle Knoten kommen, deren Markierung ich zurücksetzen muss und tue das nach der Anfrage. Oder ich verwende als Markierung gleich einen Timestamp, den ich vor jeder Anfrage erhöhe, dann muss ich nicht demarkieren.
Beantwortet irgendwas davon Deine Frage?
-
Jester schrieb:
Oder meinst Du im allgemeinen Fall, wenn ich einfach Markierbarkeit annehme? Dann führ ich noch eine Liste mit in die alle Knoten kommen, deren Markierung ich zurücksetzen muss und tue das nach der Anfrage. Oder ich verwende als Markierung gleich einen Timestamp, den ich vor jeder Anfrage erhöhe, dann muss ich nicht demarkieren.
Beantwortet irgendwas davon Deine Frage?
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
-
Wieso sollte das Markieren dadurch nicht mehr O(1) sein?
ps: Man muss auch nichtmal eine Liste mitführen.
Man kann den ganzen Vorgang auch einfach wiederholen, und statt Nodes zu markieren die Markierung dabei wieder entfernen bis man die (dann ja bereits bekannte) LCA Node findet.
Dadurch verdoppelt man den Aufwand genau. Was aber an der Komplexität nichts ändert.
-
SeppJ schrieb:
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
Für jeden Knoten den ich markiere fällt folgender Aufwand an:
- O(1) für markieren
- O(1) für Einfügen in Aufräumliste
- O(1) für Rücksitzen der Markierung am Ende
- O(1) für entfernen aus der Aufräumlistemacht insgesamt O(1) pro Knoten den ich irgendwann mal markiere. Natürlich nicht alles auf einmal sondern halt ein bisschen über die Laufzeit verteilt (amortisiert). Ich fasse ja am Schluss beim Rücksetzen nur Knoten an, die ich ohnehin vorher schonmal angefasst habe. Und das waren nur so viele wie eben erlaubt.
-
Jester schrieb:
SeppJ schrieb:
Ja, das wollte ich wissen. Aber dann ist die Markierung doch nicht mehr O(1).
Für jeden Knoten den ich markiere fällt folgender Aufwand an:
- O(1) für markieren
- O(1) für Einfügen in Aufräumliste
- O(1) für Rücksitzen der Markierung am Ende
- O(1) für entfernen aus der AufräumlisteAhh, so war das mit der Liste gemeint. Da hatte ich dich nicht richtig verstanden.
