2.4. Heuristique
Une façon d'améliorer notre précédente technique est de choisir correctement le prochain chemin à analyser. Jusque là, on prenait le chemin le moins cher. Mais si on était capable d'estimer le coût qui reste jusqu'à l'état final, on pourrait analyser beaucoup moins de chemins.
La fonction qui permet d'estimer le coût d'un chemin inconnu entre un états et la destination recherchée est appelée une heuristique. L'utiliser nous fait gagner du temps, mais si on veut être sûr qu'elle renvoie toujours le meilleur résultat, il faut qu'elle satisfasse les critères suivants :
- l'heuristique de la destination elle-même est toujours nulle,
- l'heuristique doit toujours être inférieure ou égale au coût réel du meilleur chemin,
- si on prend 3 états quelconques A, B et C, il faut toujours avoir h(A vers C) inférieur ou égal à la somme de h(A vers B) et h(B vers C).
La façon la plus simple de trouver une heuristique est d'ignorer certaines contraintes du problème réél. Dans notre cas, on va supposer que les charriots ne se bloquent pas les uns les autres et qu'ils apparaissent instantanément devant la caisse qu'ils veulent déplacer.
# -*- coding: utf-8 -*-
def H0(state):
return 0
def H1(state):
h = 0
for i in range(4,len(state)):
p = state[i]
if p < 0:
p = state[-p - 1]
d = abs(i - 4 - p)
if d > 0:
h += 12 + 11 * d
return int(h / 4)
def H2(state):
costs = [0] * 4
idx = 0
for i in range(4,len(state)):
p = state[i]
if p < 0:
p = state[-p - 1]
d = abs(i - 4 - p)
if d > 0:
if costs[idx] > 0:
# Si le charriot vient de poser une caisse, il doit se
# déplacer d'au moins un cran pour aller chercher la
# suivante.
costs[idx] += 23
costs[idx] += 12 + 11 * d
v = costs[0]
idx = 0
for k in range(1, 4):
if costs[k] < v:
idx = k
v = costs[k]
h = max(costs)
return h
3. Analyse du résultat
Voici une comparaison d'heuristiques appliquées au tri de 4 caisses en configuration CBDA :
- Heuristique nulle
- Nombre d'états parcourus : 1'089'980
- Temps CPU consommé : 36.983 secondes
- Heuristique H2
- Nombre d'états parcourus : 191'166
- Temps CPU consommé : 9.565 secondes
Grâce à l'heuristique H2, on n'examine que 17.54 % des états et au final on consomme 25.86 du temps CPU. Ce surplus de temps vient du fait que le calcul de l'heuristique à un coût. C'est donc cette partie de l'algorithme qui demande le plus de finesse (et surtout d'expérimentations), car il faut trouver la juste balance entre une heuristique très discriminante une heuristique rapide à calculer.