Chemin hamiltonien à arêtes contraintes

bisam

Bonjour,

Pour finir d'étoffer un TP d'informatique sur le "retour sur trace" (mieux connu sous le nom de "backtracking") et plus précisément traitant de la "ronde du cavalier", problème où l'on cherche à faire parcourir toutes les cases d'un échiquier $m\times n$ à un cavalier, je cherche s'il existe un algorithme efficace permettant d'ajouter des contraintes indiquant que certaines arêtes du graphe (c'est-à-dire, ici, certains mouvements du cavalier d'une case à une autre) sont obligatoirement présent(e)s dans le chemin hamiltonien cherché.

J'ai bien trouvé une méthode pour l'implémenter mais cette méthode met à mal l'heuristique de Warnsdorff qui permet de trouver assez rapidement des solutions lorsqu'il n'y a pas ces contraintes.

Le but d'ajouter ces contraintes est de pouvoir augmenter quasiment indéfiniment la taille des échiquiers car le problème général peut se résoudre en $O(mn)$, pour peu que l'on connaisse des solutions qui vérifient ces dites contraintes pour toutes les petites dimensions.

Si vous voulez en savoir plus, je joins le TP... mais j'aimerais surtout savoir si vous avez une bonne idée pour résoudre ce problème.

bisam

J'ai finalement trouvé un moyen détourné.

J'ai constaté que la recherche de solutions "contraintes" était fortement dépendante de la case choisie comme point de départ : dans certains cas, on trouve une solution avec très peu de backtracking, et dans d'autres, il en faut des centaines de milliers. 

J'ai donc opté pour une recherche randomisée : à chaque fois que je ne trouve pas de solution après avoir effectué un certain nombre de retours en arrière, j'abandonne... et je recommence la recherche à partir d'une autre origine.

Et étonnamment, cela fonctionne au-delà de mes espérances ! Si je fixe la limite de backtracking à environ 20 fois la taille totale de l'échiquier, je trouve une solution la plupart du temps en quelques secondes contre plusieurs heures auparavant.

Voici quelques échantillons de ce que cela peut donner.

Je joins également mon corrigé de ce TP. Comme le forum n'accepte pas les fichiers dont l'extension est ".py", j'ai dû renommer le fichier en ".py.txt"... mais vous pouvez bien entendu faire l'opération inverse.

mdc2

C'est un problème somme toute classique, mais les visualisations sont éclairantes.

Remarque: ce post ne répond pas à votre problème initial mais ouvre des pistes de réflexion qui pourraient être exploitées en prolongement du TP prévu.

On y voit nettement la formation de "clusters" qui se ressemblent mais qui diffèrent toutefois. Il serait intéressant d'examiner spécifiquement ces différences entre clusters, comment on peut passer de l'un à l'autre (penser en termes relationnels) localement (entre clusters) que globalement (dans le parcours global sur un échiquier de taille donnée, il semble qu'il y ait des liens qui "forcent" une entrée dans un cluster et ont donc des répercussions sur la structure du cluster en lui-même).

Deuxièmement, Il y aurait possiblement un travail artistique à faire derrière... vu que les clusters se ressemblent sans se superposer, je pense d'emblée à un travail explorant les limites de notre perception, visuelle (pour des grandes tailles de l'échiquier, en lien avec la notion de pixel, la technologie d'impression...) et sonore (mais il faut d'abord trouver un mapping entre sortie du programme et représentation musicale ou sonore... voir par exemple la musique xenharmonique, c'est-à-dire utilisant des systèmes d'accordage différents du traditionnel tempérament égal à 12 demi-tons).

lourrran

Les clusters, ce sont les petits rectangles '8x11' ou '10x8' ou... ?

Quand j'avais lu le 1er message de Bisam, il disait que justement, il adoptait comme stratégie de découper le grand échiquier en rectangles plus petits. C'était délibéré.
Et ces rectangles n'ont pas tous la même taille (pour découper 43 en 4, on a forcément des tailles différentes), et en plus, comme les points d'ancrage sont en nombres différents, ou à des emplacements différents, avec ces 2 problèmes à gérer, même quand on a 2 rectangles de même taille, on n'a pas l'assurance d'avoir la possibilité de dupliquer le trajet. ( les points d'ancrage, ce sont les points où on va 'couper' le chemin du petit rectangle, pour faire un pont vers le rectangle voisin) 

mdc2

@lourrran

Merci pour ton message.

Oui, en effet, ces rectangles (ou clusters) n'ont pas tous la même taille. Pour autant, on peut considérer les petits clusters comme appartenant à un plus gros cluster à un niveau de regroupement plus élevé. Par exemple, dans l'exemple 52x43, les quatre petits clusters du haut à gauche (que l'on pourrait noter [1,1], [1,2], [2,1] et [2,2]) pourraient être regroupés pour former un "gros" cluster de profil presque équivalent aux clusters d'en dessous. On pourrait alors noter [3,1]:[4,2] ce "gros" cluster, par analogie avec les tableurs. Et justement, ce "presque équivalent" renvoie aux décompositions que tu proposes et aussi à mon idée de travail autour des limites de la perception : en survolant le cas 81x66, je vois tous les clusters de même taille, mais ils ne le sont pas forcément.

Concernant le fait que la méthode était évoquée dans le message initial de @bisam : est-ce que ça empêche d'avoir ce genre de réflexions ? Je dirai que non et bien au contraire ! Est-ce qu'un algorithme est toujours accessible via son code ou via ses effets ? Via ses effets, clairement (si on a le code, on peut organiser l'étude des effets en l'exécutant comme ici mais si on constate les effets, on ne peut probablement pas remonter au code : les algorithmes de recommandation). Tout cela parce que les effets transcendent le cadre formel de l'algorithme.

bisam

@mdc2 : Pour mieux comprendre ce que tu appelles les "clusters" et comment je les raccorde entre eux, je t'invite à LIRE le pdf fourni dans le post initial, en particulier la partie "4. Toujours plus grand".

Ensuite, tu pourras tenter de te plonger dans mon corrigé, que j'ai pas mal commenté (et dont certaines fonctions possèdent un mode "verbeux" expliquant par des 'print' ce qu'elles sont en train de faire).