7. Comparaisons, limites et erreurs fréquentes
| Aspect | Profondeur | Largeur | Dijkstra |
|---|---|---|---|
| Information utilisée | Structure du graphe | Structure du graphe | Coûts cumulés positifs |
Gestion de OUVERTS |
Enfants au début, pile | Enfants à la fin, file | Priorité à la distance minimale |
| Comportement | Une branche à la fois | Niveau par niveau | Coût provisoire minimal |
| Optimalité dans le cadre du cours | Non | Non en général | Oui pour poids positifs |
| Risque principal | S’enfoncer dans une mauvaise branche | Frontière très large | Confondre ordre de traitement et chemin optimal |
Erreurs à éviter :
- décrire les états en prose sans définir un formalisme;
- oublier les préconditions ou ne donner que le nom d’une opération;
- produire des opérations qui violent un invariant du domaine;
- confondre l’ensemble des états possibles avec ceux effectivement générés;
- confondre état visité, état développé et état appartenant au chemin final;
- ignorer l’ordre imposé aux successeurs;
- revisiter un état déjà dans
OUVERTSouFERMÉS; - déclarer une stratégie optimale sans préciser le type de coût et les hypothèses;
- appliquer Dijkstra en présence de poids négatifs;
- mémoriser un corrigé sans savoir reconstruire les listes intermédiaires.
Les recherches exhaustives sont systématiques, mais peuvent explorer une grande partie de l’espace. Les heuristiques de la semaine suivante chercheront à réduire cet effort en estimant quels états sont les plus prometteurs, parfois au prix d’une garantie moindre.
Les exercices de formation peuvent employer des formulations variées ou laisser une ambiguïté productive afin de forcer l’analyse. Il faut donc savoir reconstruire le raisonnement dans un nouveau contexte plutôt que mémoriser une trace. Les questions notées, elles, sont censées être formulées avec assez de précision pour permettre une évaluation non ambiguë.