Tip:
Highlight text to annotate it
X
Etant donné la non optimalité de la recherche en profondeur,
pourquoi quelqu'un choisirait de l'utiliser?
Bien, la réponse a affaire avec les demandes de stockages.
Ici j'ai illustré un espace d'état
consistant en un très large ou même infini arbre binaire.
En allant jusqu'aux niveaux 1, 2, 3, jusqu'au niveau n,
l'arbre devient de plus en plus large,
Maintenant, considérons la frontière de chacun de ces algorithmes.
Pour la recherche en profondeur, nous savons ce à quoi une frontière ressemble,
et donc quand nous descendons jusqu'au niveau n, nous demandons un espace de stockage de
2 à n passages dans la recherche en largeur.
Pour moins coûteux d'abord, la frontière va être plus compliquée.
Ca va consister à travailler ce contour de coût,
mais ça va avoir un nombre similaire de nœuds.
Pour la recherche en profondeur, en descendant l'arbre, nous descendons cette branche,
et ensuite nous revenons, mais à n'importe quel point, notre frontière va seulement avoir n nœuds
plutot que 2 jusqu'a n nœuds, donc c'est une économie substentielle pour la recherche en profondeur.
Maintenant, bien sur, si nous gardons trace de l'ensemble des explorés,
alors nous n'obtenons pas autant d'économie.
Mais sans l'ensemble des explorés, la recherche en profondeur a un gros avantage
en terme d'espace gagner.
Une propriété en plus des algorithmes à considérer
est la propriété de complétude, signifiant si il y a un but quelque part,
est-ce que l'algorithme le trouvera?
Donc, passons d'arbres très larges à des arbres infinis,
et disons qu'il y a un but de bien caché quelque part dans l'arbre.
Et la question est, est-ce que ces algorithmes sont complets?
Ou, sont il garantis de trouver un chemin jusqu'au but?
Cocher les cases pour les algorithmes que vous croyez complets dans ce sens.