Bah disons que dans le cas du A* (j'utilise cet exemple mais ça doit être le cas pour d'autres choses), une heuristique admissible consiste à évaluer les sommets dans l'ordre tel que la distance entre le sommet évalué et le sommet final soit le plus petit en supposant qu'il puisse exister un chemin très court partant de ce sommet (en tenant compte du chemin déjà parcouru pour arriver à ce sommet bien sûr).
Par exemple sur une carte routière, si on cherche le chemin le plus court, il faut évaluer les sommets en se disant qu'il peut exister une autoroute qui suit le "vol d'oiseau" qui part de ce point. De ce fait on va évaluer en priorité les sommets les plus proches de la destination en priorité mais sans écarter les sommets qui sont derrières dans le cas où il y aurait un cas plus favorable. Le premier chemin trouvé est forcément le plus court.
(bien sûr, je simplifie mais c'est pour rester simple)
Mon intervention est un peu hors sujet et visait simplement à tordre cette idée reçue que heuristique implique approximation. J'étais tellement dans cette vision avant que j'avais eu du mal à voir comment faire pour que mon A* me sorte un résultat optimal. D'ailleurs suffit de lire wikipédia pour se rendre compte que c'est pas très clair : "L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant le temps de calcul à l'exactitude des résultats."
On peut coder le A* simplement comme un Dijkstra dans lequel on ajoute une heuristique permettant d'évaluer les sommets dans un ordre plus efficace.
Je pense que si on mélange heuristique et approximation c'est sans doute parce que les heuristiques sont très utiles dans les problèmes compliqués où le résultat n'est pas garanti comme étant optimal. (cf algorithme glouton, metaheuristique, ...).
Bon et là, histoire d'illustrer un peu mon propos je faisais un tour sur wikipédia et je lis le contraire de ce que je viens d'expliquer : "Une heuristique, ou méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné."
D'un autre côté, on lit aussi des choses sur wikipédia qui vont dans mon sens...
Donc restez critique sur ce que vous lisez comme d'habitude. Je ne suis pas expert dans ce domaine après tout... Mais c'est ce que mon prof d'algo m'avait expliqué.
Je ne sais pas ce qu'on peut appeler "heuristique" et ça va dépendre de cette définition si cela se présente souvent ou non. J'ai lu qu'une heuristique était une méthode permettant de trouver une solution plus rapidement (exemple : faire un dessin pour mieux comprendre le problème qu'on essaye de résoudre) et donc dans ce cas, on peut arriver à prouver assez souvent que notre résultat est optimal.
[^] # Re: Note aux modos
Posté par Maxime (site web personnel) . En réponse au journal Quelques nouvelles de LaTeXila, et réflexions sur le développement d'IDE en GTK. Évalué à 3.
Par exemple sur une carte routière, si on cherche le chemin le plus court, il faut évaluer les sommets en se disant qu'il peut exister une autoroute qui suit le "vol d'oiseau" qui part de ce point. De ce fait on va évaluer en priorité les sommets les plus proches de la destination en priorité mais sans écarter les sommets qui sont derrières dans le cas où il y aurait un cas plus favorable. Le premier chemin trouvé est forcément le plus court.
(bien sûr, je simplifie mais c'est pour rester simple)
Mon intervention est un peu hors sujet et visait simplement à tordre cette idée reçue que heuristique implique approximation. J'étais tellement dans cette vision avant que j'avais eu du mal à voir comment faire pour que mon A* me sorte un résultat optimal. D'ailleurs suffit de lire wikipédia pour se rendre compte que c'est pas très clair : "L'algorithme A* a été créé pour que la première solution trouvée soit l'une des meilleures, c'est pourquoi il est célèbre dans des applications comme les jeux vidéo privilégiant le temps de calcul à l'exactitude des résultats."
On peut coder le A* simplement comme un Dijkstra dans lequel on ajoute une heuristique permettant d'évaluer les sommets dans un ordre plus efficace.
Je pense que si on mélange heuristique et approximation c'est sans doute parce que les heuristiques sont très utiles dans les problèmes compliqués où le résultat n'est pas garanti comme étant optimal. (cf algorithme glouton, metaheuristique, ...).
Bon et là, histoire d'illustrer un peu mon propos je faisais un tour sur wikipédia et je lis le contraire de ce que je viens d'expliquer : "Une heuristique, ou méthode approximative, est donc le contraire d'un algorithme exact qui trouve une solution optimale pour un problème donné."
D'un autre côté, on lit aussi des choses sur wikipédia qui vont dans mon sens...
Donc restez critique sur ce que vous lisez comme d'habitude. Je ne suis pas expert dans ce domaine après tout... Mais c'est ce que mon prof d'algo m'avait expliqué.
Je ne sais pas ce qu'on peut appeler "heuristique" et ça va dépendre de cette définition si cela se présente souvent ou non. J'ai lu qu'une heuristique était une méthode permettant de trouver une solution plus rapidement (exemple : faire un dessin pour mieux comprendre le problème qu'on essaye de résoudre) et donc dans ce cas, on peut arriver à prouver assez souvent que notre résultat est optimal.