Les salles sont modélisées par des grilles qui ressemblent à des labyrinthes. Si on a une grille composée de L lignes et C colonnes, quel est le nombre minimum de détecteurs dont on a besoin quelque soit la configuration de cette salle ?

Dans le meilleur des cas, un détecteur peut rayer une ligne et une colonne entière. Parfois moins à cause des obstacles éventuels, mais jamais plus. Donc le nombre minimal de détecteurs nécessaire est Min( L, C ).

Si la configuration est vraiment très très mauvaise, on peut se retrouver dans le cas critique où on aura besoin d'un détecteur par case de notre grille. Une borne supérieure est donc L x C.

L'heuristique est une sorte de "distance" de la configuration actuelle à une solution. En gros, ça nous donne le nombre minimal de détecteurs à ajouter pour couvrir toute la salle.

Si on pose L' le nombre de lignes non encore totalement couvertes et C' son analogue pour les colonnes, alors notre heuristique sera tout simplement : Min( L', C' ).

Cette heuristique est admissible puisqu'à aucun moment il n'est possible de résoudre le problème en ajoutant moins de détecteurs que la valeur retournée par l'heuristique. Est-elle consistente ? Dans notre cas, le passage d'une étape de résolution à la suivante se fait en ajoutant un détecteur. Donc le coup est homogène et il vaut 1. Pour que notre heuristique soit homogène, il faut qu'entre deux étapes, elle reste égale ou diminue d'une unité seulement. Revenons donc à la définition de notre heuristique : le maximum entre le nombre de colonnes ou lignes non encore complètement couvertes. Alors, on voit bien qu'en ajoutant un détecteur, on ne peut diminuer ce max de plus d'une unité, car un détecteur ne peut couvrir plus d'une ligne ni plus d'une colonne.

Nous avons donc une heuritique consistente cela signifie que la solution que trouvera notre algorithme de recherche sera optimale.