Estimation de la taille d'un arbre

Je voudrais estimer le nombre de feuilles dans une grande arborescence pour laquelle je ne peux pas visiter tous les nœuds de façon exhaustive. Cet algorithme est-il approprié? A-t-il un nom? Aussi, s'il vous plaît pédante si j'utilise des termes inappropriés.Estimation de la taille d'un arbre

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)

Source

2010-05-07 Full Decent

Je ne vois pas comment cela pourrait fonctionner sur un arbre déséquilibré de quelque sorte que ce soit. Il serait plus logique de personnaliser l'objet arbre lui-même pour garder une trace de ce genre de choses pendant les insertions et les suppressions. –

Pensez énorme, comme un arbre de tous les jeux de dames possibles. Pas quelque chose qui serait en mémoire. –

Je comprends énorme. :) Il semble que vous puissiez avoir un arbre qui existe physiquement (même si c'est un arbre séparé) ou vous avez un arbre qui n'existe pas réellement et qui est généré à partir d'un noeud donné si nécessaire. Dans le premier cas, le code arbre-genning doit garder les statistiques pour vous donner ce que vous voulez. Le deuxième cas, vous ne pouvez pas résoudre pour une structure arborescente arbitraire. Si vous avez un deuxième cas spécial - comme les permutations de jeux de dames - il y a de meilleures méthodes à utiliser que l'échantillonnage statistique. –

Cela pourrait être possible si vous pouvez faire des hypothèses de sécurité au sujet de votre arbre (par exemple: est-il équilibré) et son utilisation (est-il une hypothèse sûre sur le nombre de feuilles seront des enfants du même noeud ?). Mieux encore serait si vous maintenez un compte courant (compteur) chaque fois que vous ajoutez/supprimez un noeud feuille. Ensuite, vous accédez simplement à votre variable compteur en une seule opération.

Source

2010-05-07 14:56:31 FrustratedWithFormsDesigner

Je ne peux pas supposer que l'arbre est équilibré. Mais je peux mettre une limite supérieure sur la profondeur. est-ce que cela aide? Cet arbre sera énorme, représentant par exemple tous les mouvements dans un jeu d'information parfait. –

Hm qui pourrait vous donner une estimation du pire des cas pour le nombre de feuilles, mais pour se rapprocher, vous devez en savoir plus. Existe-t-il un moyen de savoir/estimer combien de branches atteignent réellement la profondeur maximale? – FrustratedWithFormsDesigner

Je ne sais pas comment estimer combien de branches atteignent la profondeur maximale, mais ce sont les seules qui m'intéressent. Je vais continuer ce sujet avec des questions supplémentaires. –

Une théorie de l'estimation de la taille des arbres, fondamentale pour l'analyse de temps exponentielle algorithmes et de certaines régions de heuristiques, est

Manuel de Satisfiabilité, IOS Press 2009, ISBN 978-1-58603-929 -5 (rédacteurs en chef Armin Biere, Marijn JH Heule, Hans van Maaren et Toby Walsh) http://www.iospress.nl/book/handbook-of-satisfiability/

à savoir le chapitre 7 "fONDEMENTS de Branching heuristiques" (pages 205-244). Le rapport technique sous-jacente est http://www.swan.ac.uk/compsci/research/reports/2008/CSR7-2008.pdf Le chapitre est disponible à http://www.booksonline.iospress.nl/Content/View.aspx?piid=11712

Cette théorie généralise l'approche dans le document mentionné ci-dessus par Donald Knuth (1975, Estimation de l'efficacité des programmes Backtrack).

Source

2011-11-05 13:57:07

Estimation de la taille d'un arbre

Répondre

Questions connexes