Les contraintes unaires (celles qui se trouvent sur la disgonale) permettent de réduire l'espace des possibilité des méga-variables suivante :
- Nationalité : puisque le Norvégien est dans la première maison, les 4 autre se répartissent suivant
4x3x2x1 = 24
configurations.
- Boisson : le lait est dans la maison 3, il reste donc aussi 24 configurations.
- Couleur : ici on a deux contraintes (5 et 15) qui réduisent drastiquement le nombre de configurations.
- Rouge, Bleu, Vert, Blanc, Jaune.
- Jaune, Bleu, Vert, Blanc, Rouge.
- Rouge, Bleu, Jaune, Vert, Blanc.
- Jaune, Bleu, Rouge, Vert, Blanc.
- Animal et Fume : pas de contrainte unaire donc on a 120 possibilités.
1.2 Déroulons l'algorithme
Ainsi, si l'on veut s'amuser à tester toutes les configurations possibles, il y en aura
4x24x24x120x120 = 33'177'600
. C'est tout à fait à la portée d'un ordinateur, mais on va tenter de réduire ce nombre en utilisant la technique
min-conflict. Cela consiste à choisir aléatoirement une méga-variable qui est en conflit et à tester toutes ses autres valeurs possibles pour garder celle qui donne le moins de conflits possibles.
On teste les 120 configurations de la mégavariable Cigare
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 14.
On teste les 24 configurations de la mégavariable Nationalité
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 12.
On teste les 24 configurations de la mégavariable Boisson
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 8.
On teste les 120 configurations de la mégavariable Animal
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 6.
Le nombre total de configurations testées est de 288. Mais l'algorithme s'arrête ici car aucune mégavariable ne peut diminuer ses conflits.
On peut cependant remarquer que la contrainte 6 est violée alors qu'on aurait pu éviter qu'elle le soit en restraignant le domaine de la mégavariable Couleur.
En effet, puisque le
thé se boit dans la maison
verte et que le
lait se boit dans la maison
3, on peut être sûr que la maison
3 ne peut pas être
verte. Cela va donc réduire le domaine de la mégavariable
Couleur à ceci :
- Rouge, Bleu, Jaune, Vert, Blanc.
- Jaune, Bleu, Rouge, Vert, Blanc.
Il est alors possible d'espèrer mieux pour notre algorithme du min-conflict.
On teste les 120 configurations de la mégavariable Cigare
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 16.
On teste les 24 configurations de la mégavariable Nationalité
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 14.
On teste les 24 configurations de la mégavariable Boisson
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 10.
On teste les 120 configurations de la mégavariable Animal
et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 6.
Chou-blanc ! On est dans la même impasse. Pourquoi donc ?
Imaginez que vous soyez perdu dans le brouillard en pleine montagne. Vous savez que votre hélicoptère salvateur se trouve au sommet. Pour l'atteindre, vous utilisez l'algorithme du min-conflict : à chaque embranchement, vous choisissez le chemin qui monte le plus. Êtes-vous sûr de rejoindre le sommet ?
Cela peut arriver, mais ce n'est pas certain. La montagne est rarement un cône et il existe souvent de nombreux sommets locaux dans lesquels votre algorithme peut vous emener. C'est ce qui arrive avec notre problème. Comment peut-on sortir de ce piège ?
Peut-être faut-il être plus souple. On n'est pas obligé de sélectionner toujours le chemin qui monte le plus rapidement. Il serait intéressant de voir ce qui arrive si on sélectionne les 3 meilleurs par exemple, et qu'on en choisi ensuite un au hasard. Dans ces conditions, on peut avoir, de temps à autre, un chemin qui redescent un peu et on espère que cela nous permettra de sortir des sommets locaux.
En effet, dans ce cas, l'algorithme fini par trouver la solution à notre problème. Dans le tableau suivant, j'indique le combre de configurations analysée en fonction du paramétrage
n pour 10 essais. Le paramètre
n correspond au nombre de candidats parmi lesquels on fait une sélection aléatoire.
n | Configurations analysées avant succés | Moyenne |
2 | 13056 | 15310 | 12256 | 28656 | 56712 | 19380 | 25058 | 41714 | 53584 | 7164 | 27289.0 |
3 | 2852 | 77074 | 61480 | 63522 | 15619 | 10758 | 16940 | 17053 | 102226 | 42284 | 40980.8 |
4 | 166220 | 17292 | 34882 | 43556 | 264874 | 130730 | 95458 | 117856 | 306096 | 107134 | 128409.8 |
5 | 151544 | 4048 | 154966 | 170396 | 18001 | 121244 | 137592 | 62846 | 79349 | 70496 | 97048.2 |
Evidemment, si n vaut 1, on se retrouve dans l'algorithme précédent qui n'a pas de souplesse et qui se perd donc dans les sommets locaux sans jamais parvenir à la solution. Le tableau précédent est intéressant car il nous montre que, pour le problème d'Einstein, la soulesse nécessaire est minime puisqu'il suffit d'avoir 2 candidats pour obtenir la solution le plus rapidement possible.
Comme vous l'avez sans dout remarqué, je ne vous donne pas la solution. Car dans l'histoire, ce n'est pas l'hélicoptère le plus intéressant, mais bien le chemin qui nous permet de rejoindre cet hélicoptère.