3.5 Résolution du problème
3.5.1 Résolution par l'algorithme «
génère et teste »
Pour résoudre ce problème il faut trouver une
affectation de valeurs distinctes aux variables de X qui vérifie toutes
les contraintes. Etant donnéque les n variables prennent des valeurs
distinctes dans 1..n, il faut chercher la solution parmi les n! permutations
possibles. Donc, la complexitéde ce problème est une
complexitéfactorielle.
39
Le tableau suivant, représente le temps estimépour
résoudre un algorithme de telle complexité.
|
Nombre des variables
|
5
|
10
|
20
|
50
|
250
|
500
|
|
Générations possibles
|
120
|
3628800
|
24 × 1017
|
31 × 1095
|
32 × 10522
|
--
|
|
Temps de résolution
|
1.2 us
|
36ms
|
770 ans
|
1048ans
|
?
|
?
|
TABLE 3.1 - temps nécessaire à
l'exécution d'un algorithme de complexitéfactotielle [8]
L'algorithme génère et teste peut toujours
trouver une solution car il génère et teste tous les permutations
possibles comme nous avons vu dans le deuxième chapitre, mais si on
augmente la valeur de n il faudra beaucoup de temps pour arriver
à la solution.
3.5.2 Résolution par l'algorithme simple retour
arrière (ou backtrack)
Puisque l'algorithme génére et teste s'est
avéréinefficace, le backtrack est une première
amélioration qui consiste à tester au fur et
à mesure la consistance de l'affectation partielle des variables, et qui
retourne en arrière si elle est inconsistante. Il est facile de voir que
la recherche effectuée par le backtrack correspond à un parcours
en profondeur d'un arbre n-aires, et dont la racine est un tuple vide,
tandis que les noeuds situés au i ème niveau sont des i-uplets
qui représentent les affectations des variables le long du chemin
correspondant dans l'arbre. Les vérifications effectuées par
l'algorithme backtrack ' assurent que les affectations construites associent
des valeurs distinctes aux différentes variables. Donc, la
complexitéde cet algorithme est de l'ordre de O(n!) (dans les
pires cas).
Avec une telle complexité, on remarque facilement que
le temps de résolution augmente d'une façon plus
qu'exponentielle, chaque fois qu'on augmente le nombre de variables, car, pour
n assez grand, on a 2' < n!.
3.5.3 Résolution par l'algorithme d'anticipation
Malgrél'amélioration proposée par le
backtrack, le temps de résolution reste toujours élevé.
C'est pourquoi on va essayer la résolution avec l'algorithme
d'anticipation. L'algorithme d'anticipation (look ahead) reprend le principe de
l'algorithme précèdent (backtrack) et tente d'anticiper les
conséquences de l'affectation partielle en cours de la construction sur
les domaines des variables qui ne sont pas encore affectées. Par
conséquent, les domaines des variables vont être réduits,
au fur et à mesure, ainsi que la complexitéde l'algorithme. Cette
dernière reste toujours exponentielle malgrésa diminution.
40
| 
