5. Qu'est-ce qui pourrait nous ralentir ?
5.1 Trier les étapes
Plus les pièces seront grandes et plus notre liste d'étapes intermédiaires sera grande. Il nous faut donc un moyen rapide de trier ces étapes en fonction de leur valeur f.
L'erreur serait d'utiliser un
quick sort en pensant que c'est le plus rapide. Avec cet algorithme, si un ensemble possède
n
élements, il faudra autour de
n.log(n)
étapes de calcul pour le trier. Ca peut sembler rapide, mais je vous propose ici d'utiliser un algorithme de tri qui
ne dépende pas du nombre d'éléments.
Il n'y a aucune magie là-dessous. Nous sommes juste dans un cas particulier qui permet d'utiliser une astuce. En effet, les valeurs possibles de f sont des nombres entiers bornés. La valeur minimale est 0 et la maximale est L x C. On va donc utiliser un tableau indexé possèdant L.C + 1 piles.
Prenons un exemple.
- On a un état à mettre sur la liste d'attente. Sa valeur f est 13, alors on recherche la pile qui se trouve à l'index 13 et on l'y ajoute. C'est immédiat.
- Quand on veut dépiler l'élément de plus petit f, il suffit de prendre la première pile non vide et d'en dépiler un élément.
On peut même s'amuser à optimiser un peu la recherche de la première pile non vide en utilisant un curseur qu'on déplace dans les cas suivants :
- quand on a pris le dernier élément d'une pile,
- ou quand on ajoute un élément à une pile se trouvant à gauche du curseur.
5.2 Calculer l'heuristique
Voici une fonction qui va être appelée pour chaque étape et qui doit donc être rapide. Grossièrement, elle prend une liste de coordonnées de détecteurs, trace des traits horizontaux et verticaux à partir de ces points et compte ensuite le nombre de colonnes et de lignes non entièrement couvertes. Elle retourne alors la plus petite de ces deux valeurs.