Hello, 

J'ai récemment fait un exo dans mon cours d'IA portant sur l'algo A* dont voici l'énoncé sur la capture d'écran suivante : 

Et donc ma réponse pour cette énoncé : 

Le chemin le plus court selon moi est donc Toulouse -> Bordeaux -> Limoges -> Clermont -> Paris (en additionnant à chaque fois la distance parcourus et la distance estimée avec l'heuristique). Ma prof m'a dit que ce n'était pas la bonne solution, mais je n'arrive pas à trouver mon erreur. 

Si il y a des matheux pro en IA parmi vous, je suis preneur pour quelques explications :) 

-
Edité par hippomssc 14 septembre 2021 à 9:21:30

Salut,

à la main, le trajet Toulouse -> Montpellier -> Clermont -> Paris est plus court de 65 km (1000km contre 1065km).

Salut merci pour ta réponse, 

J'avais remarqué ce chemin effectivement, mais si ont suit l'algorithme à la lettre et en utilisant l'heuristique, on aurait Montpellier 241+595=836 et Bordeaux 244+498=742, pourquoi choisir Montpellier dans ce cas là si la distance (ou plutôt la qualité du noeud) est plus grande ? 

-
Edité par hippomssc 13 septembre 2021 à 16:55:30

up?

Effectivement, je trouve la même solution que toi, à savoir que la solution \(A^{\star}\) n'est pas la bonne. Je ne sais pas ce qui est faux dans ton exercice du coup.

Merci pour ta réponse @Nozio, 

L'exploration te paraît correcte également ? Je dis ça car c'était un exercice d'examen pour lequel je n'ai pas eu tous les points, et je n'arrive toujours pas à comprendre pourquoi...

Je n'ai pas fait pas la dernière étape Clermont -> Paris, mais pour le reste, je suis bien allé à Clermont en passant par Bordeaux et Limoges.

Bonjour, 

Si cela intéresse quelqu'un, voici la correction de mon exercice :