估計樹的大小

我想估計一個大型樹結構中的樹葉數，我無法詳盡地訪問每個節點。這個算法是否合適？它有名字嗎？另外，如果我不恰當地使用任何條款，請小心。估計樹的大小

sum_trials = 0 
num_trials = 0 
WHILE time_is_not_up 
    bits = 0 
    ptr = tree.root 
    WHILE count(ptr.children) > 0 
     bits += log2(count(ptr.children)) 
     ptr = ptr.children[rand()%count(ptr.children)] 
    sum_trials += bits 
    num_trials++ 
estimated_tree_size = 2^(sum_trials/num_trials)

來源

2010-05-07 Full Decent

我看不出這可能會在任何種類的不平衡樹上工作。定製樹對象本身以在插入和移除過程中跟蹤這種東西會更有意義。 – 2010-05-07 14:52:41

認爲巨大，就像所有可能的跳棋遊戲的樹。不是記憶中的東西。 – 2010-05-07 14:54:44

我明白了。 :)看起來你可能有一個樹在物理上存在（即使它是分裂的），或者你有一棵實際上並不存在的樹，並根據需要從給定節點生成樹。在第一種情況下，樹型代碼需要保留統計信息以給你想要的東西。第二種情況，你不能解決任何任意的樹結構。如果你有特殊的第二種情況 - 比如跳棋遊戲排列 - 有比統計抽樣更好的方法。 – 2010-05-07 15:01:39

這可能是可能的，如果你可以讓你的樹一些安全的假設（如：？是平衡）和它的使用（在那裏有多少葉子會在同一節點的孩子一個安全的假設？）。如果您每次添加/刪除葉節點時都保持運行計數器（計數器），那更好。然後，您只需在一個操作中訪問您的計數器變量。

來源

2010-05-07 14:56:31 FrustratedWithFormsDesigner

我不能假設樹是平衡的。但我可以在深度上設置一個上限。這有幫助嗎？這棵樹將是巨大的，例如代表完美信息遊戲中的所有動作。 – 2010-05-07 15:18:05

嗯，這可能會給你一個葉片數的最壞情況估計，但要接近，你需要知道更多。有沒有辦法知道/估計有多少分支實際達到最大深度？ – FrustratedWithFormsDesigner 2010-05-07 15:47:42

我不知道如何估計有多少分支達到最大深度，但這些實際上是我唯一有興趣計算的分支。我將繼續討論其他問題。 – 2010-05-07 15:52:24

估計樹大小的一個理論，基本爲指數時間和啓發式的某些領域算法，是

手冊可滿足性的分析，IOS出版社2009年，ISBN 978-1-58603-929 -5 （編輯阿明BIERE，Marijn JH Heule，漢斯·範Maaren和託比沃爾什） http://www.iospress.nl/book/handbook-of-satisfiability/

即第7章「分支啓發式的Fundaments」（205-244頁）。底層的技術報告是 http://www.swan.ac.uk/compsci/research/reports/2008/CSR7-2008.pdf 本章可在 http://www.booksonline.iospress.nl/Content/View.aspx?piid=11712

這個理論可以推廣由高德納上述論文（1975年，估計回溯方案的效率）的方法。

來源

2011-11-05 13:57:07

估計樹的大小

回答

相關問題