Algorithme A* et recherche de chemin dans les jeux

Audio automatique activé : les prochaines questions seront lues quand vous cliquerez sur Continuer.

1. 1

   Quelle fonction A* utilise-t-il généralement pour déterminer la priorité d’un nœud ?

   A f(n) = g(n) + h(n) B f(n) = g(n) − h(n) C f(n) = g(n) × h(n)
2. 2

   Quand une heuristique est-elle dite admissible dans A* ?

   A Lorsqu’elle est toujours égale au coût déjà parcouru B Lorsqu’elle ne surestime jamais le coût minimal restant C Lorsqu’elle attribue une valeur différente à chaque nœud
3. 3

   Quelle heuristique convient le mieux à une grille uniforme autorisant seulement les déplacements horizontaux et verticaux ?

   A La distance euclidienne au carré B Le nombre total de cases de la carte C La distance de Manhattan
4. 4

   Sur la grille illustrée, quelle est la distance de Manhattan entre le départ et l’objectif ?

   

   A 7 B 6 C 9
5. 5

   Dans la situation illustrée, quelle règle empêche l’agent de traverser le coin formé par les deux obstacles ?

   

   A Réduire le coût de tous les déplacements diagonaux B Exiger que les deux cases orthogonales adjacentes soient libres C Ignorer les obstacles lors du calcul de l’heuristique
6. 6

   À quel algorithme A* devient-il équivalent si h(n) vaut zéro pour tous les nœuds ?

   A La recherche en profondeur B La recherche gloutonne C L’algorithme de Dijkstra
7. 7

   Pourquoi A* peut-il préférer le détour illustré plutôt que le trajet géométriquement le plus court ?

   

   A Le détour possède un coût de déplacement cumulé plus faible B A* choisit systématiquement le chemin contenant le plus de cases C L’heuristique interdit toujours de traverser le terrain coûteux
8. 8

   D’après l’état de la liste ouverte illustré, quel nœud A* doit-il développer ensuite ?

   

   A Le nœud A B Le nœud B C Le nœud C
9. 9

   Quelle inégalité caractérise une heuristique cohérente pour une transition de n vers n’ de coût c(n,n’) ?

   A h(n) ≥ c(n,n’) + h(n’) B h(n) = c(n,n’) − h(n’) C h(n) ≤ c(n,n’) + h(n’)
10. 10

    Après le développement du départ S dans le graphe illustré, quel nœud est sélectionné en premier par A* ?

    

    A Le nœud B B Le nœud A C Le nœud G
11. 11

    Lorsque plusieurs nœuds ont la même valeur f, quel départage peut souvent réduire le nombre de nœuds explorés sans changer le coût optimal ?

    A Choisir systématiquement le nœud créé en dernier, sans autre critère B Privilégier le nœud ayant la plus grande valeur g C Privilégier le nœud dont l’heuristique est la plus grande
12. 12

    Un obstacle mobile vient de bloquer une case du chemin déjà calculé. Quelle stratégie est la plus adaptée ?

    

    A Conserver le chemin jusqu’à ce que l’agent traverse l’obstacle B Modifier uniquement l’heuristique sans mettre à jour la carte C Mettre à jour les cellules affectées puis recalculer ou réparer le chemin
13. 13

    Avec des coûts non négatifs et une heuristique cohérente, quand A* peut-il confirmer que le chemin optimal vers l’objectif est trouvé ?

    A Lorsque l’objectif est retiré de la liste ouverte pour être développé B Dès que l’objectif est découvert comme voisin d’un nœud C Lorsque tous les nœuds du graphe ont été placés dans la liste fermée