|
|
|
Les différentes options qui déterminent le comportement du contrôle lors de son exécution sont présentées dans cette boite de dialogue. Ces options sont regroupées en plusieurs zones.
Search Target Les 4 cases à cocher fixent l'objectif de la recherche. Si aucune des cases n'est cochée, une simple recherche de parcours, sans contrainte particulière est réalisée. L'option "Magic Square" permet de rechercher des carrés magiques et l'option "Semi" sur la même ligne que "Magic Square" impose de plus que les carrés soient semi-magiques (chaque quart de l'échiquier est un carré magique). De ce fait, un carré semi-magique est magique. "Magic Diagonal" cherche des parcours dont la somme de chaque diagonale vaut 260 (la même valeur que les lignes ou les colonnes d'un carré magique). L'option "Semi-diago" permet de rechercher des parcours dont les diagonales de chaque quart de l'échiquier valent 130. Lorsque les quatre options sont cochées, le temps de parcours de l'arbre complet est de quelques heures. Si l'algorithme est exact, cela montre qu'il n'y a pas de solution de pour des carrés semi-magiques avec diagonales semi-magiques. Les 8 diagonales des quatre quart de l'échiquier devraient valoir 130. Algorithm Parameters Ces options sont utilisées par l'algorithme en mode non optimisé (case à cocher optimization code). Elles permettent de changer le comportement de l'algorithme pour des valeurs d'index donné. L'idée sous-jacente est la suivante : est-il plus rentable d'un point de vue temps de recherche de faire des tests, coûteux en temps de calcul, pour savoir si une solution peut être atteinte ou vaut-il mieux ne faire aucun test et parcourir le plus vite possible l'arbre des possibilités ? quel est le meilleur compromis ? Pour obtenir un carré magique, il n'est pas nécessaire d'attendre qu'une ligne ou qu'une colonne de l'échiquier soit complète pour faire la comparaison avec 260. On peut en effet déterminer par avance, en cours de progression, si cette valeur peut être atteinte. Deux cas peuvent se produire qui dépendent chacun de l'index courant du déplacement.
Les deux cas sont très différents. Dans le premier cas, lorsque le cavalier arrive sur une case, il calcule la valeur de la ligne et de la colonne associée à cette case et il sait a cet instant si la somme de 260 pourra être atteinte. Les valeurs limites sont connues
On pet donc vérifier cette valeur lors de l'arrivée du cavalier sur la case. Dans le deuxième cas, il ne faut pas que la valeur soit trop grande. Une valeur de ligne/colonne valide pour un index donné peut devenir invalide lorsque l'index courant est plus grand. Il est dans ce cas nécessaire de vérifier, à chaque bond, les 8 lignes et les 8 colonnes de l'échiquier. Cette vérification est coûteuse. Le problème qui se pose alors est basique : quand faut il la faire c'est à dire pour quelle valeur de l'index courant. C'est le sens du paramètre index min for checking line/row. Dead end Pour obtenir un carré complet dont les index sont reliés par des bonds de cavalier, il est utile de déceler lors de la progression les cases isolées qui ne peuvent être atteintes. Dans ce cas, il faut faire marche arrière. L'algorithme intègre la détection d'un trou isolé, de 2 trous liés mais isolés du reste des cases libres ou de 3 trous isoles reliés en triangle ou en chaîne. Pour l'instant, les solutions sont trouvées le plus rapidement avec une détection de 2 trous isolés. Le code mettant en évidence des groupes de 3 cases isolées est assez long et n'est donc pas utilisé. De plus si une case a plusieurs destinations possibles, le risque de se diriger à partir de cette case vers un mauvais chemin est possible. Si la case n'a qu'une destination l'alternative est simple : il faut aller sur cette case ou il faut reculer. Les tests montrent qu'il est plus coûteux en temps de calcul de tester s'il faut aller sur une case qui est la seule destination pour choisir alors de ne pas y aller que d'y aller pour se rendre compte après coup que ce n'était pas la bonne solution. Optimization code Cette option permet de paramétrer l'algorithme avec les options les plus performantes. La plupart des tests sont supprimés pour être intégrés dans la classe spécialisée, utilisée dans l'algorithme. Sort destinations (static) Chaque case de l'échiquier contient un tableau de cases destinations à portée d'un bond de cavalier. La rapidité de la solution trouvée, indépendamment de l'algorithme en lui-même, dépend de l'ordre dans lequel ces cases sont essayées. Lorsque le cavalier arrive sur une case, la case retourne la première case de ce tableau. L'arbre complet de recherche est parcouru à partir de cette case. La façon de trier les cases destination a une influence directe sur le temps de recherche. Statiquement, c'est à dire à l'initialisation du programme, 3 tris sont possibles
Sort destinations (dynamic) Cette option permet de modifier le tri sur les cases destination en cours de parcours. On peut réaliser les mêmes tris que lors du lancement du programme. On peut également créer des tris à partir de critères exotiques comme c'est le cas pour le dernier de la liste. Il est possible dynamiquement de construire un nouveau tableau de cases destinations ne contenant que les cases libres. La construction de ce tableau prend un peu de temps à chaque bond mais en retour les cases sont forcément libres. C'est l'option avoid busy cases Show NBS Il serait intéressant de connaître le nombre de solutions du problème du cavalier. L'option Show NBS permet de comptabiliser les solutions trouvées en continuant la recherche plutôt que de s'arrêter à la première solution. Lorsque l'option "optimization code" est cochée et que la cible choisie est un carré simple sans contrainte de carré magique, on constate que l'algorithme produit 15 000 solutions/seconde et cela pendant plusieurs jours. Par contre, lorsque le tri sur les destinations est aléatoire, aucune solution n'est trouvée pendant plusieurs heures ... Lorsque la cible de recherche est un carré avec certaines contraintes, les solutions trouvées sont sauvegardées sur le disque.
|
