complexité temporelle et spatiale de l'ampleur première recherche

Question

Je ne comprends pas d'où viennent les complexités suivantes.

espeacialy b (b^d-1) dans la complexité du temps

complexité du temps: total engourdis. de nœuds générés: 1 + b + b2 + ... + bd + b (b^d-1) = O (b^(d + 1)) Complexité spatiale: O (b^(d + 1))

où b - facteur de branchement maximum de l'arbre recherche d - profondeur de la solution la moins coûteuse

Answer 1

à la racine, vous développez des b nœuds que les prochains éléments dans l'arbre de recherche. Ceux-ci, si aucun n'est la solution, à leur tour développer b nœuds de chacun. Cela continue jusqu'à ce qu'une solution soit trouvée, qui sera en profondeur d.

Par conséquent: O (b^d)

(Je ne sais pas où vous avez obtenu le +1 de, mais ...)

Answer 2

Si l'algorithme était d'appliquer le critère de but aux nœuds Lorsqu'elle est sélectionnée pour l'expansion plutôt que lorsqu'elle est générée, toute la couche de nœuds à la profondeur d serait étendue avant que le but ne soit détecté et la complexité temporelle serait O (b^(d + 1)).

Answer 3

En termes plus simples dans BFS, nous utilisons une file d'attente pour conserver le chemin du chemin visité. Chaque sommet du graphique est visité au plus une fois. Par conséquent, la taille de la file d'attente est maximale. D'où la complexité de l'espace si une fonction du nombre de sommets dans le graphe i.e O (| V |). En ce qui concerne la complexité du temps, nous exécutons une boucle pour parcourir tous les sommets du graphique. C'est O (| V |). Aussi, pour chaque sommet trouvé, nous devons vérifier tous ses voisins et donc le nombre d'arêtes auquel il est connecté. Cela nous donne O (| E |). Ainsi, la complexité peut être expliquée par la notation O (| V | + | E |).