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.

Aujourd'hui, je vais parler de balances. Un de mes proches possède une vieille balance avec une boîte contenant une série de poids. Jusqu'ici, rien d'extraordinaire me direz-vous, sauf que certains poids sont manquants. Pour certains objets, il n'est donc pas possible de connaître le poids exact mais seulement s'en approcher. Et là, je me suis dit : "il y a un problème d'optimisation derrière". Voyons maintenant comment formaliser cela.

Soit $$\Omega \in (\mathbb{R}^+_0)^n$$ un ensemble de nombres réels positifs non nuls. On cherche à décomposer $$\Omega$$ en $$k < n$$ ensembles disjoints $$\Omega_1,\ldots,\Omega_k$$ en minimisant la distance de la somme des éléments entre chaque paire $$\Omega_i$$ et $$\Omega_j$$. On cherche donc à optimiser la fonction objectif suivante :

$$ \min \frac{1}{2} \sum_{i,j} f\Big(\sum_{p \in \Omega_i} p - \sum_{q \in \Omega_j} q\Big), $$

où $$f : \mathbb{R} \rightarrow \mathbb{R}^+$$ est une fonction symmétrique (i.e. $$f(x)=f(-x)$$) avec les contraintes suivantes :

• (i) $$\Omega=\cup_{i=1}^k \Omega_k$$.
• (ii) $$\Omega_i \cap \Omega_j = \emptyset$$, $$\forall i,j \in \{1,\ldots,k\}$$ et $$i \not= j$$.

Pour la fonction $$f$$, on peut typiquement utiliser $$f(x)=x^2$$ ou bien $$f(x)=|x|$$. En toute honnêteté, je pense que ce problème a dû déjà être étudié mais j'ignore son nom. Mon intuition me dit aussi qu'il doit probablement être NP-difficile pour un $$k$$ quelconque. Reste à savoir si c'est encore le cas lorsque $$k=2$$, par exemple. Une première approche pour résoudre heuristiquement ce problème peut consister à faire une recherche locale en choisissant à chaque itération le couple d'élément $$(p,q) \in (\Omega_i \times \Omega_j)$$ qui fait décroître le plus la fonction objectif en les permutant. On garantit ainsi une décroissance de la fonction objectif mais avec le risque d'être coincé dans un minimum local sans pouvoir s'en échapper. On recommence ainsi jusqu'à convergence.

Pour ceux qui suivent régulièrement ce site, j'avais discuté en 2009 d'un problème de placement de tours. Rappelons brièvement en quoi consiste ce problème : on dispose de $$K$$ tours de couleur différente, chacune contenant un nombre d'habitants croissant. Les tours doivent être placées sur un graphe non-orienté $$G=(V,E)$$ où les sommets $$V$$ désignent les emplacements des tours et les arêtes $$E$$ correspondent aux relations entre les tours (on a typiquement un voisinage de type 4 ou 8 connexité). Les contraintes de placement sont alors les suivantes :

1. Chaque sommet $$v \in V$$ est colorié exactement une fois.
2. Un sommet de couleur $$k \in \{1,\ldots,K\}$$ doit posséder dans son voisinage au moins un sommet de couleur $$k-1$$, un sommet de couleur $$k-2$$, $$\ldots$$, et un sommet de couleur 1.

L'objectif est alors de trouver la coloration optimale de $$V$$ qui maximise la population. Notez au passage que le degré maximum de $$G$$ doit être strictement inférieur à $$K$$ pour que la contrainte (2) soit satisfaite. Voici maintenant quelques définitions utiles pour la suite :

1. Ensemble dominant : un ensemble de sommets $$D \subset V$$ est dit dominant dans $$G$$ ssi chaque sommet $$v \not\in D$$ possède au moins un voisin $$w \in D$$.
2. Weak $$K$$-coloring : c'est un coloriage de $$G$$ qui affecte une couleur $$k \in \{1,\ldots,K\}$$ à chaque sommet $$v \in V$$ tq chaque sommet non-isolé est adjacent à au moins un sommet de couleur différente.
3. $$K$$-partition domatique : l'ensemble des sommets $$V$$ est une $$K$$-partition domatique de $$G$$ en ensembles disjoints $$V_1,\ldots,V_K$$ ssi chaque ensemble $$V_k$$ est un ensemble dominant de $$G$$, $$\forall k \in \{1,\ldots,K\}$$.

On a alors les relations suivantes :

1. Weak 2-coloring $$\Leftrightarrow$$ 2-partition domatique
2. Weak $$K$$-coloring $\Leftarrow$ $$K$$-partition domatique ($$K>2$$)
3. 2-partition domatique $$\Rightarrow$$ $$V_1$$ (ou $$V_2$$) est un ensemble dominant de $$G$$
4. Ensemble dominant minimum $$\Rightarrow$$ 2-partition domatique

Outre la maximisation des $$V_k$$, le problème qui nous intéresse est donc à mi-chemin entre le weak $$K$$-coloring (deux sommets voisins ont des couleurs différentes) et la $$K$$-partition domatique (chaque sommet est entouré de toutes les couleurs possibles). Lorsque $$K=2$$, notre problème correspond en fait à celui du Minimum Dominating Set (on cherche un ensemble dominant de taille minimum dans $$G$$. Au passage, cela correspond d'ailleurs au nombre de domination souvent noté $$\gamma(G)$$.) qui est connu comme étant NP-difficile. C'est notamment le cas dans les graphes à grille mais le problème reste polynomial lorsqu'une des dimensions de la grille est fixée. Un algorithme polynomial existe en revanche pour les arbres (voir [HHP98b]). A ma connaissance, le problème qui nous intéresse n'a pas été traité auparavant dans la littérature et laisse donc des perspectives de travail intéressantes parmi :

1. Montrer que le problème est NP-difficile (réduction à partir du problème de partition domatique ?)
2. Trouver des algorithmes polynomiaux pour des classes de graphes à degré borné puis non borné.

Références :

• [CS91] D.G. Corneil et L.K. Stewart. Dominating sets in perfect graphs. Discrete Mathematics, 86(1-3) : 145-164, 1991.
• [HHP98a] T.W. Haynes, S.T. Hedetniemi, et P. Slater. Domination in Graphs : Advanced Topics. Marcel Dekker 1998.
• [HHP98b] T.W. Haynes, S.T. Hedetniemi, et P. Slater. Fundamentals of Domination in Graphs. Marcel Dekker, 1998.