DS 4 — Algorithmes d'approximation, algorithmes probabilistes¶

MPI, année scolaire 2022-2023.

Sujet d'après deux TD de l'Université de Montpellier : « Marche aléatoire pour la coloration de graphe » (B. Grenet, HMIN119m, TD 10, 2018-2019) et « Partition » (HAI503I, TD 5, 2022-2023). Les énoncés sont ici résumés ; le corrigé est celui de l'auteur.

Ce devoir porte sur le chapitre Algorithmes d'approximation, algorithmes probabilistes.

3-Coloration probabiliste¶

Une $k$-coloration d'un graphe $G = (S, A)$ attribue à chaque sommet une couleur parmi $k$ ; elle est valide si les deux extrémités de chaque arête ont des couleurs différentes. On cherche une 3-coloration valide d'un graphe 3-coloriable à $n$ sommets et $m$ arêtes.

Q.1 Les graphes $G_1$ et $G_2$ ci-dessous sont-ils 3-coloriables ? Le cas échéant, donner une 3-coloration valide.

Les graphes G_1 (à gauche) et G_2 (à droite). — Les graphes $G_1$ (à gauche) et $G_2$ (à droite).

Corrigé

1) $G_1$ n'est pas 3-coloriable : le sommet 3 est relié à tous les autres, donc seul 3 peut avoir sa couleur, et le cycle autour de 3 composé de 0, 2, 5, 4, 1 devrait être 2-coloriable, ce qui est impossible car sa longueur 5 est impaire.

2) $G_2$ est 3-coloriable avec la coloration suivante :

\[ \begin{array}{ccccc} 0 & 1 & 2 & 3 & 4 \\ \hline 0 & 1 & 2 & 0 & 1 \end{array} \]

Q.2 On tire indépendamment et uniformément une couleur parmi trois pour chaque sommet.

i. Quelle est la probabilité qu'une arête fixée soit valide ?

ii. Montrer que la probabilité d'échec (coloration non valide) est au plus $\frac{m}{3}$.

iii. Pourquoi cet algorithme n'est-il pas satisfaisant ?

Corrigé

i) Une fois la première couleur choisie, il y a deux couleurs possibles sur trois rendant l'arête valide, donc la probabilité est de $\frac{2}{3}$.

Note pour ceux qui trouveraient ça peu rigoureux : vous pouvez énumérer les couples de couleurs ici si ça vous amuse, mais ça revient à ignorer la symétrie évidente de ces cas.

ii) On considère $m$ arêtes et pour l'arête numéro $i$, l'événement $V_i$ indiquant que la coloration de cette arête est valide. On a alors

\[P(\text{échec}) = P\left(\bigcup_{i=1}^m \overline{V_i}\right) \le \sum_{i=1}^m P(\overline{V_i}) = \sum_{i=1}^m \frac{1}{3} = \frac{m}{3}\]

iii) Pour $m \ge 3$, cette majoration n'apporte aucune garantie.

On utilise maintenant une marche aléatoire : on part d'une coloration aléatoire et, tant qu'une arête n'est pas valide, on la rend valide en modifiant localement la coloration. La distance entre deux colorations est le nombre de sommets qui n'ont pas la même couleur dans les deux.

Q.3 Écrire le pseudo-code de cet algorithme.

Corrigé

On génère aléatoirement une 3-coloration.
Tant qu'il y a une arête non valide :
- on choisit aléatoirement un des sommets de cette arête ;
- on remplace sa couleur par une des deux autres couleurs en la choisissant aléatoirement.

On fixe une 3-coloration valide (la coloration cible) et on note $d$ la distance entre la coloration courante et la cible, et $\Delta d$ sa variation lors d'une étape.

Q.4 Montrer que $\Delta d \in \{-1, 0, 1\}$.

Corrigé

On ne change la couleur que d'un sommet, donc en faisant cela il y a trois possibilités :

la nouvelle couleur est celle du sommet dans la coloration cible : on s'est rapproché et $\Delta d = -1$ ;
la nouvelle couleur n'est pas celle du sommet dans la coloration cible alors que c'était le cas avant : on s'est éloigné et $\Delta d = 1$ ;
la nouvelle couleur n'est pas celle du sommet dans la coloration cible et ce n'était déjà pas le cas avant : rien n'a changé sur la distance et $\Delta d = 0$.

Q.5 Lors d'une étape, soit aucun des deux sommets de l'arête traitée n'a sa couleur cible, soit l'un des deux l'a (pas les deux, car la cible est valide et l'arête ne l'est pas). Calculer les probabilités que $\Delta d$ vaille $-1$, $0$ et $1$ dans ces deux cas. Quel est le pire cas ?

Corrigé

On suppose ici que les couleurs sont dans $\{0,1,2\}$. On va noter $0 \smile 0$ la coloration invalide initiale de l'arête.

Cas où la coloration cible est $1 \smile 2$ ($2 \smile 1$ symétrique) : on a quatre colorations possibles dans l'algorithme, équiprobables, et voici les cas de $\Delta d$ correspondant :

\[\begin{array}{c|cccc} col & 1 \smile 0& 2 \smile 0 & 0 \smile 1& 0 \smile 2 \\ \hline \Delta d & -1 & 0 & 0 & -1 \end{array}\]

Comme ces cas sont équiprobables, on en déduit : $P(\Delta d = -1) = P(\Delta d = 0) = \frac{1}{2}$ et $P(\Delta d = 1) = 0$.
Cas où la coloration cible est $0 \smile 1$ (les autres cas sont symétriques) : on a quatre colorations possibles dans l'algorithme, équiprobables, et voici les cas de $\Delta d$ correspondant :

\[\begin{array}{c|cccc} col & 1 \smile 0& 2 \smile 0 & 0 \smile 1& 0 \smile 2 \\ \hline \Delta d & 1 & 1 & -1 & 0 \end{array}\]

Comme ces cas sont équiprobables, on en déduit : $P(\Delta d = -1) = P(\Delta d = 0) = \frac{1}{4}$ et $P(\Delta d = 1) = \frac{1}{2}$.

C'est le deuxième cas qui est le pire cas, car c'est celui où la probabilité de s'éloigner est strictement positive et où la probabilité de se rapprocher est la plus faible.

Notons ici que la question est facilitée par ses probabilités mais qu'il n'est pas toujours possible d'identifier un pire cas sans précisions sur ce qui est comparé.

On note $p(d)$ la probabilité que l'algorithme atteigne la coloration cible en partant d'une coloration à distance $d$, en supposant qu'on est toujours dans le pire cas.

Q.6 Montrer que $p(d-1) - 3p(d) + 2p(d+1) = 0$ pour $1 \le d < n$, et donner les équations des cas limites $p(0)$ et $p(n)$.

On admet que la solution vérifie $p(d) \ge 2^{-d}$.

Corrigé

On va appliquer la formule des probabilités totales au pire cas en conditionnant par la valeur de $\Delta d$ :

\[ \begin{array}{rcl} p(d) &= &P(\Delta d = 0) p(d) + P(\Delta d = -1) p(d-1) + P(\Delta d = 1) p(d+1) \\ &=& \frac{1}{4} p(d) + \frac{1}{4} p(d-1) + \frac{1}{2} p(d+1) \end{array} \]

qui équivaut à

\[ 3 p(d) = p(d-1) + 2 p(d+1) \]

On a $p(0) = 1$ car si on part d'une coloration à distance 0, c'est qu'elle est valide et l'algorithme la renvoie.

Si on part d'une coloration à distance $n$, aucun sommet n'a sa couleur cible : les arêtes invalides sont forcément dans le premier cas, et on a donc $p(n) = \frac{1}{2} p(n-1) + \frac{1}{2} p(n) \iff p(n) = p(n-1)$.

Q.7 Combien y a-t-il de colorations à distance $d$ de la coloration cible ?

Corrigé

On adopte une approche constructive du dénombrement : on définit une manière univoque de construire les objets et on identifie pour chaque choix le nombre de possibilités.

Pour construire une coloration à distance $d$, il faut choisir les sommets qui changent, il y a $\binom{n}{d}$ choix possibles, et pour chacun de ces sommets il y a deux couleurs possibles pour différer de la cible.

On a donc $\binom{n}{d} 2^d$ colorations.

Q.8 En déduire que la probabilité de succès de l'algorithme est au moins $\left(\frac{2}{3}\right)^n$, et calculer l'espérance du nombre d'exécutions nécessaires avant de trouver une 3-coloration valide.

Corrigé

On conditionne sur la distance $d$ de la coloration initiale, qui est uniforme parmi les $3^n$ colorations :

\[ \begin{array}{rcl} P(\text{succès}) & \ge & \sum_{k=0}^n P(d = k) p(k) \\ &=& \sum_{k=0}^n \frac{\binom{n}{k} 2^k}{3^n} p(k) \\ &\ge& \sum_{k=0}^n \frac{\binom{n}{k} 2^k}{3^n} 2^{-k} \\ &=& \frac{1}{3^n} \sum_{k=0}^n \binom{n}{k} \\ &=& \left(\frac{2}{3}\right)^n \end{array} \]

(la première inégalité car atteindre la cible n'est qu'une des façons de réussir).

On calcule ensuite l'espérance du nombre $T$ d'exécutions de l'algorithme jusqu'à la première qui réussit, les exécutions étant indépendantes.

Il s'agit ici d'une loi géométrique : répéter une épreuve de Bernoulli tant qu'on n'a pas d'issue favorable.

La probabilité d'un succès au bout de $k$ étapes signifie qu'on a eu $k-1$ échecs puis un succès, donc $P(T=k) = p q^{k-1}$ où $p = P(\text{succès})$ et $q = 1-p = P(\text{échec})$.

On a donc

\[ \begin{array}{rcl} E(T) & = & \sum_{k=1}^{\infty} k P(T=k) \\ & = & \sum_{k=1}^{\infty} k p q^{k-1} \\ & = & p \frac{1}{(1-q)^2} \\ & = & p \frac{1}{p^2} \\ & = & \frac{1}{p} \\ & \le & \left( \frac{3}{2} \right)^n \end{array} \]

Q.9 On ne peut pas savoir a priori si une exécution va s'arrêter. Proposer une ou plusieurs stratégies pour obtenir un algorithme de type Las Vegas.

Corrigé

La stratégie la plus simple est donc de lancer l'algorithme tant qu'on n'a pas de coloration valide, cependant, il faut décider d'un nombre d'itérations limite pour gérer les exécutions infinies sans toutefois perdre de vue la possibilité de converger vers une solution.

On peut, par exemple, considérer qu'on converge en moins de $m$ itérations.

Remarque. L'algorithme obtenu est bien de Las Vegas (une coloration renvoyée est toujours valide, puisqu'on la vérifie), à condition que le graphe soit 3-coloriable ; sinon il ne termine pas. En revanche, l'analyse précédente porte sur une marche non bornée : pour garantir l'espérance $\left(\frac{3}{2}\right)^n$ avec une limite d'itérations, il faudrait minorer la probabilité d'atteindre la cible en moins de cette limite, ce que le sujet ne fait pas. Le choix de la limite $m$ est donc une heuristique.

Un exemple de code réalisant cet algorithme est donné ici :

let g = [|
    [1;2];
    [0;2;3];
    [0;1;3;4];
    [1;2;4];
    [2;3]
    |]

let coloration_aleatoire g =
    let n = Array.length g in
    Array.init n (fun i -> Random.int 3)

let coloration_valide g col =
    let n = Array.length g in
    let bvalide = ref true in
    for i = 0 to n - 1 do
        bvalide := !bvalide
            && List.for_all  (fun j -> col.(i) <> col.(j)) g.(i)
    done;
    !bvalide

exception Trouve of (int * int)
let arete_invalide g col =
    let n = Array.length g in
    try
        for i = 0 to n-1 do
            List.iter (fun j ->
                if col.(i) = col.(j)
                then raise (Trouve (i,j)))
                g.(i)
        done;
        raise Not_found
    with Trouve (i,j) -> (i,j)

let arete_switch col (i,j) =
    let flip i =
        let k = Random.int 2 in
        col.(i) <- if col.(i) > k then k else 1 + k
    in flip (if Random.int 2 = 0 then i else j)

exception TropDiterations

let coloration_marche g limite =
    let col = coloration_aleatoire g in
    let n = ref 0 in
    try
        while not (coloration_valide g col) do
            let i, j = arete_invalide g col in
            arete_switch col (i,j);
            incr n;
            if !n > limite
            then raise TropDiterations
        done;
        Some col
    with TropDiterations -> None

let rec coloration_marche_las_vegas g k =
    let m = Array.fold_left (+) 0
        (Array.map List.length g) / 2 in
    match coloration_marche g m with
    | Some col -> col, k
    | None -> coloration_marche_las_vegas g (k+1)

Le graphe g est le graphe $G_2$ de la question 1 ; coloration_marche_las_vegas g 1 renvoie une coloration valide et le nombre d'essais effectués. Dans arete_switch, si k vaut $0$ ou $1$, la nouvelle couleur est la $(k+1)$-ième couleur différente de col.(i) : elle est donc uniforme parmi les deux autres couleurs.

2-Partition approchée¶

Étant donné un ensemble de $n$ entiers positifs $A = \{a_0, \dots, a_{n-1}\}$, on cherche une partition $A = X \sqcup Y$ minimisant $\max(\Sigma_X, \Sigma_Y)$, où $\Sigma_S$ désigne la somme des éléments de $S$. On considère l'algorithme glouton qui part de $X = Y = \emptyset$ et, pour $i$ allant de $0$ à $n - 1$, ajoute $a_i$ à $X$ si $\Sigma_X < \Sigma_Y$, et à $Y$ sinon.

Q.1 a) Appliquer l'algorithme à $A = \{4, 2, 3, 2, 7\}$. La solution est-elle optimale ? b) Quelle est sa complexité ?

Corrigé

a) On présente le déroulé dans un tableau :

\[\begin{array}{c|cc} i & X & Y \\ \hline & \emptyset & \emptyset \\ 0 & \emptyset & \{ 4 \} \\ 1 & \{ 2 \} & \{ 4 \} \\ 2 & \{ 2, 3 \} & \{ 4 \} \\ 3 & \{ 2, 3 \} & \{ 4, 2 \} \\ 4 & \{ 2, 3, 7 \} & \{ 4, 2 \} \end{array}\]

Et ainsi, le max vaut $12$.

La solution optimale est ici atteinte par une division parfaite en deux : $\{ 4,2,3\}, \{ 2,7\}$ où chaque somme vaut 9. Une telle division, si elle existe, est forcément optimale. L'algorithme n'est donc pas optimal ici.

b) L'algorithme est linéaire en $O(n)$ (en maintenant les sommes).

Dans la suite, $(X^*, Y^*)$ est une solution optimale, $OPT = \max(\Sigma_{X^*}, \Sigma_{Y^*})$, et $(X, Y)$ la solution du glouton, avec, quitte à échanger les noms, $\Sigma_X \ge \Sigma_Y$.

Q.2 Montrer que a) $a_i \le OPT$ pour tout $i$ ; b) $\Sigma_A \le 2 OPT$.

Corrigé

a) Si $a_i \in X^*$, alors $a_i \le \Sigma_{X^*} \le OPT$. Le cas $Y^*$ est symétrique.

b) $\Sigma_A = \Sigma_{X^*} + \Sigma_{Y^*} \le 2 OPT$ car $a + b \le 2 \max(a,b)$.

Q.3 Soit $a_k$ le dernier élément ajouté à $X$. a) Montrer que $\Sigma_X - a_k \le \frac{1}{2}(\Sigma_A - a_k) \le OPT - \frac{1}{2} a_k$. b) En déduire que le glouton est une $\frac{3}{2}$-approximation. c) Construire un exemple où la solution vaut exactement $\frac{3}{2} OPT$.

Corrigé

a) Notons $X^0$ et $Y^0$ les valeurs de $X$ et de $Y$ au moment où on a choisi $a_k$. On a donc $\Sigma_X = a_k + \Sigma_{X^0}$ et $\Sigma_{X^0} \le \Sigma_{Y^0}$ par le test de l'algorithme (inégalité stricte si $X$ est l'ensemble de la première branche, large sinon, quand on a échangé les noms).

On a $\Sigma_A - a_k = \Sigma_X + \Sigma_Y - a_k = \Sigma_{X^0} + \Sigma_Y \ge \Sigma_{X^0} + \Sigma_{Y^0} \ge 2 \Sigma_{X^0}$.

Donc $\Sigma_X - a_k = \Sigma_{X^0} \le \frac{1}{2} (\Sigma_A - a_k) \le OPT - \frac{1}{2} a_k$ avec 2b.

b) $\Sigma_X \le OPT + \frac{1}{2} a_k \le \frac{3}{2} OPT$ avec le 2a.

c) $\{ 1, 1, 2 \}$ va produire $X = \{ 1 \}, Y = \{ 1, 2 \}$ de valeur 3 alors que l'optimale $\{1,1\},\{2\}$ vaut 2. Donc exactement $3 = \frac{3}{2} \times 2$.

On trie maintenant $A$ par ordre décroissant avant d'appliquer le glouton : $a_0 \ge a_1 \ge \dots \ge a_{n-1}$.

Q.4 a) Montrer que sur $\{10, 10, 9, 9, 2\}$, le glouton avec tri n'est pas optimal. b) Montrer que si $X$ ne contient qu'un élément, la solution est optimale. c) Si $X$ contient au moins deux éléments, montrer que le dernier élément $a_k$ ajouté à $X$ vérifie $a_k \le \frac{2}{3} OPT$. d) En déduire que le glouton avec tri est une $\frac{4}{3}$-approximation.

Corrigé

Une remarque sur l'énoncé ici, ce n'est pas très clair car il y a un choix de comparaison dans le test de l'algorithme qui défavorise $X$, donc la condition $\Sigma_X \ge \Sigma_Y$ a peu de chances d'être remplie dans des cas limites. On aurait pu mettre un $\le$ pour simplifier.

a) On obtient $X = \{ 10, 9 \}$ et $Y = \{ 10, 9, 2\}$ de valeur 21 alors que $\{ 10, 10 \}, \{ 9, 9, 2 \}$ est une division parfaite de valeur 20, donc optimale.

b) Si $X = \{ a_i \}$, la valeur de la solution est $\max(\Sigma_X, \Sigma_Y) = \Sigma_X = a_i \le OPT$ d'après 2a. La solution est donc optimale.

c) Soit $a_l \in X$ avec $l \neq k$ (existe par hypothèse). Comme $a_k$ est le dernier élément ajouté à $X$, on a $l < k$ et donc $a_k \le a_l$ grâce au tri. Avec 3a : $a_k \le a_l \le \Sigma_X - a_k \le OPT - \frac{1}{2} a_k$.

C'est l'étape clé pour pouvoir poursuivre l'encadrement : $\frac{3}{2} a_k \le OPT \iff a_k \le \frac{2}{3} OPT$.

d) Ainsi, $\Sigma_X \le OPT + \frac{1}{2} a_k \le OPT + \frac{1}{3} OPT = \frac{4}{3} OPT$, et dans le cas b la solution est optimale.