LCA N-ary Tree
-
Hi,
eine kleine aufgabe, mich wuerde die effizienteste loesung interessieren...
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.LG
-
Was hat das mit C++ zu tun? Und warum sollen wir dir deine Hausaufgaben googeln?
-
Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (alle ISO-Standards) in das Forum Rund um die Programmierung verschoben.
Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?Dieses Posting wurde automatisch erzeugt.
-
@SeppJ: das ist keine hausaufgabe mein freund!
-
@AlgorithTheMan: das ändert nix an der aussage mein freund!
-
AlgorithTheMan schrieb:
@SeppJ: das ist keine hausaufgabe mein freund!
Du sitzt gerade direkt in der Prüfung, oder was? Oder bist du gar derjenige, der die Hausaufgabe korrigieren muss?
-
@SeppJ: keine pruefung und keine korrektur!
-
ich will nur ueber verschiedene loesungsansaetze auf einer sachlichen ebene diskutieren.
-
AlgorithTheMan schrieb:
ich will nur ueber verschiedene loesungsansaetze auf einer sachlichen ebene diskutieren.
Dann fang doch mal mit einem an.
-
Der naive Ansatz hätte O(depth).
Kann man das signifikant verbessern?
-
hustbaer schrieb:
Der naive Ansatz hätte O(depth).
Kann man das signifikant verbessern?Unter den Restriktionen des Threaderstellers meines Wissens nach nicht. Da kann man höchstens noch um die Konstanten feilschen. Ich vermute, dass er die Aufgabenstellung falsch wiedergegeben hat. Eine Funktion, um die Kinder eines Knotens zu bekommen wäre beispielsweise recht nützlich. Dann könnte man mit einmaliger Vorbereitung (in O(Anzahl Elemente)) Datenstrukturen erstellen, die eine Antwort in O(1) erlauben.
-
Vergessen dazuzuschreiben, weiss nicht ob es klar war: ich meinte ob man den avg. case siginifikant verbessern kann.
Worst case muss es denke ich - unter den gegebenen Voraussetzungen - O(depth) sein (also genauer irgendwas ala O(max(depth(node1), depth(node2))) - keine Ahnung wie man in der Big-O Notation korrekt "das grössere von" schreibt).Allerdings gibt es ja viele Fälle wo der gemeinsame Knoten nicht der Rootknoten ist, und da könnte man abkürzen. Dadurch müsste man mMn. auf O(max(depth(node1), depth(node2)) - depth(LCA)) runterkommen.
Die Frage ist bloss ob das was bringt, da depth(LCA), bei zufälliger Auswahl der Knoten, im Schnitt wohl recht klein sein wird.
-
Den gleichen Gedankengang hatte ich auch und ich vermute, du hast die gleichen oder ähnliche Vorstellungen, welche Strategien man hier vergleichen könnte. Aber ich möchte bewusst davon Abstand nehmen, konkret zu werden, bis der Threadersteller wenigstens einen Anflug von Initiative zeigt.
Weiterhin bin ich mir nicht sicher, ob O(max(depth(node1), depth(node2)) - depth(LCA)) machbar ist. Würde das nicht quadratisch viele Vergleiche während der Suche zur Folge haben? Vielleicht denken wir auch an unterschiedliche Strategien.
-
Ne, das geht. Du läufst einfach von beiden Anfrageknoten aus gleichzeitig nach oben (also immer abwechselnd einen schritt) und markierst dabei die knoten. Sobald eine der suchen auf einen schon markierten knoten trifft ist das der Lca. Man macht dann höchstens doppelt so viele Schritte wie der größere abstand der anfrageknoten vom lca.
-
@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.
