En utilisant l'algorithme A-star pour effectuer une recherche, si vous avez deux nœuds (ou plus) dans la liste ouverte avec la même valeur, qui est la valeur la moins coûteuse, quel nœud devriez-vous choisir?
Je sais que vous devriez choisir celui qui a la moindre valeur heuristique, mais que se passe-t-il si ce coût est également le même?
Par exemple:
J'ai deux nœuds développés à partir de la racine. f (n1) = f (n2) et h (n1) = h (n2). Quel nœud devrais-je développer, n1 ou n2? Devrais-je développer au hasard ou utiliser le premier ajouté à la liste ouverte?
Réponses:
0 pour la réponse № 1Une stratégie courante consiste à gérer les nœuds liés de manière LIFO. Cela donne à l'algorithme un peu plus de profondeur. En général, cela ne doit pas nécessairement être la solution la plus efficace.
Vous pouvez également utiliser la chance de briser les liens.
Ou vous choisissez la stratégie pragmatique consistant à choisir le premier nœud que votre algorithme produit d’une manière ou d’une autre.
0 pour la réponse № 2
La plupart des algorithmes que j'ai vus ou écrits ne font que choisirla première valeur qui s'avère avoir le coût le plus bas. Si la prochaine valeur comparée a exactement le même coût, la première serait choisie pour se développer. L’algorithme se penchera généralement sur le passé et étendra l’autre assez tôt, donc pas de problème.