Statistische Schätzung der Gesamtknoten in einem Baum, in dem die Kantenüberquerung teuer ist
Ich habe einen gerichteten Baum, und ich möchte seine Größe bekommen. Ich habe keine Informationen über seine Tiefe oder Verteilung von Knoten. Es gibt zwei Haupthindernisse:
1) Der Baum ist sehr groß (~ Milliarden von Knoten)
2) Edge Traversal ist teuer.
Gibt es statistische Methoden, die ich verwenden kann, um eine Schätzung der Größe (Anzahl der Knoten) schnell und mit begrenztem Fehler zu erhalten? Leider führt das Googlen nur zu genauen Zählalgorithmen, die angesichts dieser Einschränkungen schlecht funktionieren würden.
Bonus
Wenn ich die Einschränkung von Baum zu DAG (gerichteter azyklischer Graph) lockere, kann ich dann sowohl die Größe als auch die Anzahl der eindeutigen Pfade erhalten? Z.B. für diese DAG (jede Kante zeigt nach unten)
Es gibt 19 Knoten (Größe) und 23 Pfade (4 zusätzliche, da die rote Kante 1 weiteren Pfad für den Zielknoten und 3 weitere Pfade für die untergeordneten Knoten des Zielknotens gibt)
Dinge, die ich versucht habe
Für den Baumfall denke ich an etwas wie:
%Vor%Es berechnet im Wesentlichen die "Reichweite" an den tiefsten Knoten des Baumes und breitet sie dann zurück in die darüber liegende Ebene aus, um die Reichweite auf dieser Ebene zu finden. Es tut das, bis es schließlich die "Reichweite" der Wurzel des Baumes findet. Ich bin mir nicht sicher, ob ich im obigen Algorithmus irgendwelche Annahmen über eine gleichmäßige Verteilung von Knoten mache oder nicht. Um es noch einmal zu sagen, ich weiß nicht, welche Art von Verteilung ein bestimmter Baum haben wird.
Wenn es funktioniert, löst das auch die "Pfade" für die DAG. Sobald Sie alle "Pfade" haben, denke ich an die Umkehrung des Geburtstagsparadoxons, um herauszufinden, wie viele eindeutige Knoten es gibt. Das Geburtstagsparadoxon antwortet, "wie viele Tage (Pfade) wir wählen müssen, bis wir einen zufälligen Tag mit einer Wahrscheinlichkeit von 365 einzelnen Tagen des Jahres erreichen". Also versuchen wir immer wieder zufällige Pfade (Tage) bis wir einen doppelten Knoten treffen, wir wiederholen das mehrmals, um eine Wahrscheinlichkeit für dieses Ereignis zu finden, und dann verbinden wir ihn mit dem Geburtstagsparadox, um die Anzahl eindeutiger Knoten zu finden Jahr). Beachten Sie jedoch, dass das Geburtstagsparadoxon auch eine Annahme der Einheitlichkeit annimmt.
Nichts davon ist sehr streng. Was wäre ideal, ist etwas, das mir eine Schätzung mit einer Fehlergrenze gibt, und ein Papier, das den Algorithmus mit ausreichender Strenge beschreibt. Alle Hinweise in die richtige Richtung werden sehr geschätzt.
1 Antwort
Knuth hat dazu im Zusammenhang mit der Backtracking-Baumsuche eine Abhandlung geschrieben: Die Effizienz von Backtrack-Programmen - z. Ссылка . Suchbegriffe Knuth-Baum-Schätzung finden auch Papiere, die auf diese verweisen, wie ftp://ftp.cs.indiana.edu/ pub / techreports / TR60.pdf und Ссылка .
Ich habe keine Ahnung, wie sich dies im Allgemeinen auf DAGs übertragen lässt, aber - wiederum im Kontext der Baumsuche - können Sie DAGs als Bäume mit der gleichen Anzahl von Stützpunkten neu definieren, indem Sie Einschränkungen hinzufügen, die Kanten in jeden Stützpunkt verbannen nachdem er zuerst. Z.B. Wenn Sie eine Teilmenge von Zahlen nacheinander auswählen, müssen sie in aufsteigender Reihenfolge aufgelistet sein - dann hat (1,3,8) nur den einzelnen Vorgänger (1,3).
Wenn Sie darüber nachdenken, können Sie auch einen Baum definieren, in dem jeder DAG-Pfad zu einer Kante eine andere Kante im Baum definiert. Wenn Sie die Anzahl der Kanten in diesem Bereich zählen, können Sie etwas über die Anzahl der DAG-Pfade erfahren.
Tags und Links python algorithm tree statistics duplicates