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 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 :

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.
Pages : 1 2 3 4 5 6 7
Detecteur de présence
15 mai 2013
Sommaire général