1. Min-conflict

Nous allons tester la technique itérative du conflit minimal. Pour cela, il suffit de partir d'une configuration aléatoire (et donc probablement fausse) que nous allons corriger à chaque itération.
Pour effectuer les corrections, nous prendrons une variable fausse et lui donnerons la valeur qui viole le moins de contraintes. Il suffira de continuer jusqu'à ce qu'on trouve une solution.

1.1 Variables

Il nous faut tout d'abord déterminer les variables ainsi que les valeurs possibles qu'elles peuvent prendre. Dans ce problème, il y a 5 couleurs, 5 boissons, 5 cigares, 5 animaux et 5 nationalités. Et chacune de ses caractéristiques doit être attribuée à une maison. Si on numérote les maisons de 1 à 5, cela nous donne les valeurs possibles pour ces 25 variables.
Cependant, la structure du problème est telle que ces variables sont regroupées en 5 catégories avec une contrainte commune au sein de chaque catégorie : dans une même catégorie, les variables ont toutes des valeurs distinctes. Ce qui nous amène à considérer les catégories comme des méga-variables dont les valeurs sont les permutations de 5 éléments (5 couleurs, 5 nationalités, ...).
Chaque méga-variable a donc le choix entre 5x4x3x2x1 = 120 valeurs possibiles.
Représentons les contraintes binaires et unaires dans le tableau ci-contre en utilisant la légende suivante :
N A B C F
Nationalité142 3 1 4
Animal 2 7,9,11
Boisson 3 13 6 10,12
Couleur 1 6 5,15 8
Fume 4 7,9,11 10,12 8
  • 1 : Anglais = Rouge
  • 2 : Suédois = Chien
  • 3 : Danois = Thé
  • 4 : Allemand = Prince
  • 5 : Vert = Blanc - 1
  • 6 : Vert = Café
  • 7 : Oiseau = Pall Mall
  • 8 : Jaune = Dunhill
  • 9 : Chat | Blend
  • 10 : Bière = Blue Masters
  • 11 : Cheval | Dunhill
  • 12 : Eau | Blend
  • 13 : Lait = 3
  • 14 : Norvégien = 1
  • 15 : Norvégien | Bleu
  • 15 : (14) ⇒ Bleu = 2
NB : La barre verticale (|) signifie "est voisin de".
Les contraintes unaires (celles qui se trouvent sur la disgonale) permettent de réduire l'espace des possibilité des méga-variables suivante :

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.
Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Blue Master   10 Chat
Maison 3 Vert   6 Anglais   1 Lait Dunhill   8, 11 Chien   2
Maison 4 White Allemand   4 Thé   3 Pallmall   7 Poisson
Maison 5 Jaune   8 Suédois   2 Eau   12 Prince   4 Cheval   11

On teste les 120 configurations de la mégavariable Cigare et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 14.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière Blue Master Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Pallmall   7 Chat
Maison 3 Vert   6 Anglais   1 Lait Blend   12 Chien   2
Maison 4 White Allemand Thé   3 Prince Poisson
Maison 5 Jaune Suédois   2 Eau   12 Dunhill   11 Cheval   11

On teste les 24 configurations de la mégavariable Nationalité et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 12.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière Blue Master Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Pallmall   7 Chat
Maison 3 Vert   6 Suédois Lait Blend   12 Chien
Maison 4 White Allemand Thé   3 Prince Poisson
Maison 5 Jaune Anglais   1 Eau   12 Dunhill   11 Cheval   11

On teste les 24 configurations de la mégavariable Boisson et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 8.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière Blue Master Oiseau   7
Maison 2 Bleu Danois Thé Pallmall   7 Chat
Maison 3 Vert   6 Suédois Lait Blend Chien
Maison 4 White Allemand Eau Prince Poisson
Maison 5 Jaune Anglais   1 Café   6 Dunhill   11 Cheval   11

On teste les 120 configurations de la mégavariable Animal et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 6.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière Blue Master Oiseau   7
Maison 2 Bleu Danois Thé Pallmall   7 Chat
Maison 3 Vert   6 Suédois Lait Blend Chien
Maison 4 White Allemand Eau Prince Cheval
Maison 5 Jaune Anglais   1 Café   6 Dunhill Poisson
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.
Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Blue Master   10 Chat
Maison 3 Jaune   8 Anglais   1 Lait Dunhill   8, 11 Chien   2
Maison 4 Vert   6 Allemand   4 Thé   3 Pallmall   7 Poisson
Maison 5 White Suédois   2 Eau   12 Prince   4 Cheval   11

On teste les 120 configurations de la mégavariable Cigare et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 16.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Blue Master   10 Chat
Maison 3 Jaune Anglais   1 Lait Dunhill   11 Chien   2
Maison 4 Vert   6 Allemand Thé   3 Prince Poisson
Maison 5 White Suédois   2 Eau   12 Pallmall   7 Cheval   11

On teste les 24 configurations de la mégavariable Nationalité et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 14.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Oiseau   7
Maison 2 Bleu Danois   3 Café   6 Blue Master   10 Chat
Maison 3 Jaune Suédois Lait Dunhill   11 Chien
Maison 4 Vert   6 Allemand Thé   3 Prince Poisson
Maison 5 White Anglais   1 Eau   12 Pallmall   7 Cheval   11

On teste les 24 configurations de la mégavariable Boisson et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 10.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Oiseau   7
Maison 2 Bleu Danois Thé Blue Master   10 Chat
Maison 3 Jaune Suédois Lait Dunhill   11 Chien
Maison 4 Vert Allemand Café Prince Poisson
Maison 5 White Anglais   1 Eau   12 Pallmall   7 Cheval   11

On teste les 120 configurations de la mégavariable Animal et on garde celle qui minimise les conflits.
Le nombre de conflits tombe à 6.

Couleur Nationalité Boisson Cigare Animal
Maison 1 Rouge   1 Norvégien Bière   10 Blend   12 Poisson
Maison 2 Bleu Danois Thé Blue Master   10 Chat
Maison 3 Jaune Suédois Lait Dunhill Chien
Maison 4 Vert Allemand Café Prince Cheval
Maison 5 White Anglais   1 Eau   12 Pallmall Oiseau
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.
nConfigurations analysées avant succésMoyenne
2130561531012256286565671219380250584171453584716427289.0
32852770746148063522156191075816940170531022264228440980.8
416622017292348824355626487413073095458117856306096107134128409.8
515154440481549661703961800112124413759262846793497049697048.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.
Pages : 1 2
Enigme d'Einstein
Vendredi 12 octobre 2012
Sommaire général