Tip:
Highlight text to annotate it
X
Nous avons donc étudié 2 algorithmes de recherche
L'un, la recherche en largeur, dans lequel nous explorons d'abord
les chemin les plus courts.
Le second, cheapest-first search, dans lequel nous explorons
le chemin ayant le plus petit coût.
J'en profite maintenant pour introduire un troisième algorithme, la recherche en profondeur,
qui est, d'un certaine façon, l'opposé de la recherche en largeur.
Lors d'une recherche en profondeur, nous explorons d'abord le chemin le plus long,
celui contenant le plus d’arêtes.
Maintenant, je veux que vous me donniez, pour chacun de ces arbres,
l'ordre dans lequel les nœud sont visités,
premier, second, troisième, et ainsi de suite, en mettant un chiffre dans chaque case.
Si il y a égalité, notez le chiffre puis visitez les nœud ex-aequo de la gauche vers la droite.
En suite, je veux que vous posiez une autre question :
Quels algorithmes de recherche sont optimaux ?
C'est a dire, est-il garanti qu'ils trouvent la meilleure solution.
Pour la recherche en largeur, l’optimalité serait de trouver le chemin le plus court.
Si vous pensez que la recherche en largeur trouve le chemin le plus court, cochez cette case.
Pour la cheapest-first, cela signifierait trouver le chemin de coût minimal.
Cochez cette case si vous pensez que c'est le cas.
Et nous admettrons que tout les coûts sont positifs.
Et, dans la recherche en profondeur, l’optimalité signifierait à nouveau,
comme dans la recherche en largeur, de trouver le chemin ayant le moins d’arêtes.
Cochez ici si vous pensez que c'est toujours le cas.