Algorithme glouton et A* Fermé

Question

Bonjour, 

je dois écrire un programme de réolution de labyrinthe avec les algo gloutons et A*. J'ai compris leur fonctionnement global mais je ne sais pas ce que l'on doit faire lorsque l'on a plusieurs choix possibles par exemple
A---B(10)---C(10)---G(4)
  ---D(10)---E(10)---F(5)
on se retrouve bloqué dès le premier niveau dans les deux cas!
donc est-ce que l'on choisit aléatoirement?
Merci de m'aider!

Configuration: Windows 7 / Firefox 8.0

KX · Answer

Aléatoirement non, A* doit être déterministe, tu dois les prendre suivant une stratégie fixée, exemple : du plus petit au plus grand, de gauche à droite... ça dépend du problème.
Pour le glouton à la rigueur on pourrait mettre un peu d'aléatoire, mais le mieux est quand même d'avoir un glouton un minimum intelligent et donc suivre aussi une stratégie (pas forcément la même que A*).

emilie · Answer

Oui mais dans le cas du glouton en gros a partir de A il peut aussi bien prendre B que D vu qu'ils ont le meme cout, y'en a pas un minimum
De meme dans le cas du A* lorsque l'on prend l'un ou l'autre des héritiers bah on est tjs dans l'impasse vu que genre en prenant B, je regarde C mais ma fonction cout n'a toujours pas diminuée!

Algorithme glouton et A*

2 réponses

Discussions similaires