Quel est le nombre total de nœuds générés par Depth-First Search

Question

Supposons que 'd' est la profondeur finie d'un arbre; 'b' est un facteur de ramification; 'g' est le noeud d'objectif le moins profond. D'après ce que je sais, le pire des cas est lorsque le nœud de l'objectif se trouve au tout dernier nœud à la base d'un arbre. Ainsi, soi-disant le nombre total de nœuds générés est O (bg), n'est-ce pas? Cependant, mon instructeur m'a dit que c'était faux car le pire des cas est quand tous les arbres sont explorés à l'exception du sous-arbre enraciné au nœud de but. Il a mentionné quelque chose au sujet de O (bd) - O (b (g-d)) .... Je ne suis pas entièrement sûr.

Je ne comprends pas vraiment ce qu'il veut dire, alors quelqu'un peut-il me dire quelle réponse est correcte?

Answer 1

Je recommande de dessiner un arbre, en marquant les nœuds qui sont explorés, et en comptant le nombre.

Votre raisonnement est correct si vous utilisez la largeur de la première recherche parce que vous aurez seulement atteint une profondeur de g pour chaque branche (O(b**g) nœuds explorés au total).

Le raisonnement de votre instructeur est correct si vous utilisez la recherche en profondeur car vous atteignez une profondeur de d pour toutes les parties de l'arbre sauf celle avec le but (O(b**d - b**(d-g)) nœuds explorés).

Le but est le cercle vert.

Les nœuds bleus sont explorés.

Les nœuds rouges ne sont pas explorés.

Pour compter le nombre exploré nous comptons le total dans l'arbre, et emportons les rouges.

Profondeur = 2 = d

but en profondeur = 1 = g

facteur de ramification = b = 3

Notez que nous avons appelé le nombre total de noeuds dans l'arborescence O(b**d). Strictement parlant, le total est b**d + b**(d-1) + b**(d-2) + ... + 1, mais c'est O(b**d).