Tip:
Highlight text to annotate it
X
Voila les réponses.
La recherche en largeur, comme le nom l'indique, suit les nœuds dans cet ordre.
Un, 2, 3, 4, 5, 6, 7.
Donc, il va à travers une bande à la fois, en largeur d'abord.
Est-ce optimal?
Bien, ça prend toujours le plus court chemin d'abord,
et donc n'importe ou le but se trouve, il va le trouver en n'examinant pas
de chemins plus long, donc en fait, c'est optimal.
Moins coûteux d'abord, d'abord prend un chemin de longueur zero,
puis le chemin de longueur 2.
Maintenant il y a un chemin de longueur 4, chemin de longueur 5,
chemin de longueur 6, un chemin de longueur 7, et finalement, un chemin de longueur 8.
Et comme on a vu, c'est garanti de trouver le plus chemin le moins coûteux de tous,
assumant que tous les pas individuels ne sont pas négatifs.
La recherche en profondeur essaye d'aller aussi profond qu'il peut en premier,
donc il va 1, 2, 3, ensuite revient, 4,
puis revient, 5, 6, 7.
Et vous pouvez voir qu'il ne prend pas nécéssairement le plus court chemin de tous.
Disons qu'il y avait des buts en position 5 et en position 3.
Il trouverait le chemin le plus long pour la position 3 et trouve le but
et ne trouverait pas le but en position 5.
Donc, il n'est pas optimal.