samedi 5 juin 2010
Le problème des n dames pour illustrer les méta-heuristiques
Par Didier Müller, samedi 5 juin 2010 à 15:13 - Articles/revues
Le but du problème des huit dames est de placer huit dames d'un jeu d'échecs sur un échiquier de 8×8 cases sans que les dames se menacent mutuellement, conformément aux règles du jeu d'échecs. Par conséquent, deux dames ne devront jamais partager la même rangée, colonne, ou diagonale.
Le problème des n dames est une généralisation de ce problème classique : on considère un échiquier nxn au lieu d'un échiquier 8x8. Bien que ce ne soit pas à proprement parlé un problème d'optimisation, il présente de nombreux avantages :
- il est visuel et facile à comprendre ;
- on peut coder la position des dames très simplement : pour chaque colonne, on note sur quelle ligne se trouve la dame. Par exemple, une position sera notée [2, 4, 6, 8, 3, 1, 7, 5] ;
- on passe très facilement d'une configuration à une configuration voisine : il suffit d'échanger deux colonnes. Une position voisine (mais qui ne satisfait pas forcément les contraintes) de celle ci-dessus est par exemple [2, 1, 6, 8, 3, 4, 7, 5].
Lire mon article complet : "Le problème des n dames pour illustrer les méta-heuristiques", Bulletin no 113 de la SSPMP, juin 2010
lu 5585 fois