Ces jours-ci, je me suis remis sur un problème qui me tenait à coeur depuis quelques temps. Le problème est le suivant: étant donné un graphe à grille $$\mathcal{G}=(\mathcal{V},\mathcal{E})$$ non orienté à $$n \times m$$ sommets, on souhaite trouver un chemin hamiltonien dont le nombre de segments géométriques est maximum ou minimum. Dans ce dernier cas, la solution est triviale: on peut facilement montrer que le nombre de segments minimum est égal à $$2 \min{(n,m)} - 1$$ (la preuve est donnée ici). Cela correspond, par exemple, à un chemin en spirale partant de l'extérieur du graphe vers l'intérieur. Il y a quelques années, un article a d'ailleurs traité ce problème en le généralisant à des grilles multidimensionnelles.

Exemple de chemin hamiltonien 'minimum' pour un graphe 5 x 5. Le nombre de segments trouvé est 9.

Trouver une solution qui maximise le nombre de segments est un problème moins trivial. Je n'ai en revanche pas trouvé de références traitant de ce problème mais il est fort probable qu'il ait déjà été étudié dans la littérature. Dans un premier temps, l'objectif pour moi est de connaître la valeur optimale pour tout couple $(n,m)$ afin de trouver des bornes ou de me comparer par rapport à des heuristiques. Pour cette raison, je me suis naturellement tourné (et mes fidèles lecteurs l'auront deviné) vers une approche de type programmation linéaire. L'aspect modélisation de ce problème est intéressant. Voyons maintenant de plus près comment s'y prendre.

Tout d'abord, on transforme notre graphe initial en graphe orienté en remplaçant chaque arête $$(p,q)$$ par deux arcs $$(p,q)$$ et $$(q,p)$$. On représente une solution de notre problème en introduisant une variable binaire (belongs_to_path[p,q]), indiquant si l'arc $$(p,q)$$ appartient au chemin hamiltonien ou non. La fonction objectif nécessite de compter le nombre de segments qui peut être décomposé en segments horizontaux et verticaux. Par exemple, le nombre de segments horizontaux sur une ligne $$1 \leq q \leq m$$ du graphe est égal à la moitié du nombre de fois où

$$ |belongs\_to\_path[p-1,q] - belongs\_to\_path[p+1,q]|=1, $$

Je présente dans le tableau ci-dessous quelques résultats pour plusieurs valeurs de $$n$$ pour lesquelles on a $$n=m$$. La machine utilisée est une station de calcul à 12 processeurs Intel Xeon cadencés à 3.0 Ghz avec 64 Go de RAM. Le solveur CPLEX en version 12.40.0.1 a été utilisé. Les temps de calcul sont le résultat d'une moyenne de 10 lancements. Sans grande surprise, les temps de calcul deviennent très élevés dès que $$n=7$$. J'ai également mis un exemple de solution fournie par le solveur pour $$n=m=5$$.

Exemple de chemin hamiltonien 'maximum' pour un graphe 5 x 5. Le nombre de segments trouvés est 20.

En creusant un peu, il semblerait que le problème de décision associé (i.e., étant donné un nombre de segments $$k$$, existe-t-il un chemin hamiltonien comptant un nombre de segments supérieur ou égal à $$k$$ ?) soit finalement polynomial. En effet, pour un couple $$(n, m)$$, on peut montrer que le nombre maximum de segments (notons-le $$S(n,m)$$) peut être donné par

$$ S(n, m) = S'(\min{\{n, m\}}, \max{\{n, m\}}), $$

$$ S'(n, m) = \left\{ \begin{array}{ll} n(n-1)+(1-n\%2) & \mbox{si}~m=n\\ n(n-1)+(1-n\%2)+n & \mbox{si}~m=n+1\\ n(n-1)+(1-n\%2)+n+(n-n\%2)(m-n-1) & \mbox{sinon}.\\ \end{array} \right. $$

La première équation permet de gérer la symétrie entre $$n$$ et $$m$$. La seconde décompose les cas en fonction de la valeur de $$m$$. C'est plutôt une bonne nouvelle mais cela ne nous donne en revanche pas d'algorithme. Je pense que l'on doit pouvoir modifier une solution $$(n,m)$$ pour une solution $$(n+1,m)$$ ou $$(n,m+1)$$ mais j'ignore encore comment. Pour finir, notons que ce problème peut être facilement généralisé à des grilles multidimensionnelles et en prenant en compte des types de segments supplémentaires (par exemple, des segments diagonaux). Pondérer le nombre de segments horizontaux et verticaux par des $$\beta_i \in ]0,1]$$ semble aussi être une piste intéressante. Lorsque l'on fixe $$\beta_i = 1$$, on retrouve notre problème de départ. J'ignore par exemple si le problème reste polynomial lorsque les coefficients sont tous différents de un. Bref, affaire à suivre :)

• Code source : [ZIP]

Aujourd'hui, j'avais besoin de copier un répertoire d'un premier dépôt vers un second. Pour ce faire, je dois omettre les dossiers .svn lors de la copie. En cherchant sur le net, on trouve tout un cas de commande à base de find, grep et autres joyeuseries. Mais pour ce cas particulier, il existe une commande bien pratique qui fait le boulot :

svn export nom_du_dossier_dans_le_depot repertoire_de_sortie

Il y a quelques temps de cela, je me suis intéressé au comportement des marches aléatoires. Pour rappel, une marche aléatoire est un processus stochastique qui décrit le mouvement d'un système à dynamique discrète ou continue. Il est composé d'unités élémentaires (les pas) dont la longueur est soit constante ou variable (aléatoire par exemple). On fixe le point de départ de la marche (par exemple l'origine) et à chaque étape, on choisit une direction selon une densité de probabilité donnée (par exemple la loi uniforme) et une longueur de pas. La direction peut être choisie dans le domaine continu ou discret. Le processus est dit isotrope lorsque la densité de probabilité est une loi uniforme : chaque direction a donc la même chance d'être tirée au sort. Ce processus est dit markovien car chaque direction de saut est indépendante de la précédente. Le futur du système dépend donc uniquement de l'état présent. Les marches aléatoires sont très étudiées en informatique et en mathématiques. Elles seraient d'ailleurs utilisées par Google pour classer ses pages sur le réseau.

Le soft ci-dessous permet de tracer simultanément plusieurs marches aléatoires anisotropes sur le réseau $$\mathbb{Z}^2$$ (par oposition à isotrope) à partir du même point de départ. Le nombre de marches, le point de départ, la distribution de probabilité peuvent être modifiées à tout moment. Pour plus de fun, j'ai inséré des obstacles à éviter par les marches. Pour l'instant, l'approche utilisée est de type brute-force : tant que la direction tirée au sort se trouve en face de l'obstacle, on en tire une nouvelle afin de le contourner. Evidemment, cette approche est inadaptée lorsqu'une direction est fortement privilégiée et qu'elle se trouve perpendiculaire à un mur droit. La vidéo ci-dessous montre une simulation de 1000 marches aléatoires où la densité de probabilités est modifiée à chaud par l'utilisateur et correspond donc à un changement de direction du système. Lorsque la probabilité d'aller à droite est maximum (donc minimum pour les autres directions), et que le point de départ est situé exactement en face le premier obstacle à gauche, il est possible de reproduire la fameuse expérience de la planche de Galton.

• Code source : [ZIP]

Quatre news en quatre jours, on ne m'arrête plus :). Cette fois-ci, petit retour sur un soft que j'avais codé en 2009 pour résoudre les grilles de jeu Boggle. Je rappelle ici rapidement en quoi consiste le jeu. On a d'un côté un dictionnaire et de l'autre côté une grille de jeu avec des lettres (apparaissant évidemment dans le dictionnaire) tirées aléatoirement. Le but du jeu est de trouver un maximum de mots du dictionnaire apparaissant dans la grille (au sens que la connexité de la grille). De plus, chaque case de la grille ne doit être utilisée qu'une fois par mot. Plus le mot est long, plus il rapporte de points. Ce problème est clairement polynomial puisqu'il s'agit simplement d'une recherche en profondeur sur la grille à partir de chaque case.

Considérons maintenant le problème inverse : connaissant une grille tirée aléatoirement (selon la distribution des lettres de la langue choisie), on souhaite trouver l'arrangement optimal qui maximise le nombre points. Ce problème est autrement plus difficile que le précédent. Côté optimalité, il n'est pas certain qu'un solveur de type cplex ou glpk n'éprouve pas de difficulté à résoudre ce type de problème vu la grande taille du dictionnaire. Notez que ce problème a donné lieu sur la toile à un contest en 1997.

L'idée était donc plutôt de commencer avec une heuristique de recherche locale en sélectionnant à chaque itération le couple de lettres qui assure une montée rapide du nombre de points. Ce processus peut alors être réitéré jusqu'à ce qu'aucune permutation n'améliore le score courant. Les algorithmes génétiques sont une autre possibilité : l'idée est de faire évoluer un ensemble de solutions en appliquant des opérateurs de croisement (mix de solutions) et de mutation (modification des solutions). Le fait de laisser une grande liberté dans le choix de ces opérateurs et des paramètres est clairement à la fois un avantage et un inconvénient. Pour finir, ces deux heuristiques ont été implémentées dans Smoggle.