Exercices gloutons

Cours/Algorithmie/Design d'algorithmes/Algorithmes gloutons/Exercices gloutons

Exercices de créations d'algorithmes gloutons pour résoudre divers problèmes d'optimisation. On a séparé les exercices en deux grandes parties : la première où la stratégie gloutonne est optimale (et où il faut le démontrer), la seconde où elle ne l'est pas mais dont on peut garantir les performances.

Attention, souvent les algorithmes gloutons n'ont pas de garanties du tout. Beaucoup d'algorithmes gloutons sont juste des heuristiques qui peuvent être aussi mauvaises que possible, les utiliser dépend alors de la nature des données. Nous n'en parlons cependant pas ici car, en général, les étudiants ont rarement besoin de profs pour écrire des algorithmes non optimaux et sans garanties...

Gloutons optimal

Comme toujours lorsque l'on crée un algorithme glouton, la principale difficulté est de trouver l'ordre dans lequel considérer les objets. Une fois cet ordre trouvé les preuves sont toujours les mêmes (mais il faut tout de même la faire).

Recouvrement

Donnez un algorithme glouton exhibant un nombre minimal $K$ d'intervalles unités $I_i = [u_i, u_i+1]$ ($1\leq i \leq K$) permettant de recouvrir $n$ réels donnés $x_1, \dots, x_n$.

corrigé

On classe les réels par ordre croissants puis pour chaque réel $x_i$ on ajoute l'intervalle $[x_i, x_i + 1]$ s'il n'est pas déjà couvert.

On utilise la preuve par l'absurde du cours. On suppose que l'algorithme glouton n'est pas optimal et choisit une solution optimale coïncidant le plus longtemps possible avec la solution de notre glouton. Soit $i$ la première tape où les choix ont divergé : c'est à dire la première étape où le glouton a ajouté l'intervalle $[x_i, x_i + 1]$ alors qu'il n'est pas dans la solution optimale considérée.

On va distinguer deux cas :

$i=1$. Ce cas est impossible car comme $x_1$ est le plus petit réel, on peut remplacer tous ses intervalles se finissant avant $x_1 + 1$ par l'intervalle $[x_i, x_i + 1]$ dans la solution optimale pour obtenirune solution (les intervalles couvrent clairement tous les réels) avec un nombre plus petit nombre d'intervalle et coïncidant plus longtemps avec le glouton : ceci est impossible par hypothèse.
$i>1$. Il existe dans la solution optimale (ou moins) un intervalle couvrant $x_i$. Nommons cet intervalle $[a, a+1]$. On a que $a< x+i$ puisque $[x_i, x_i + 1]$ n'est pas dans la solution optimale. Mais comme il n'existe aucun réel dans $[a, x_i[$ qui ne soit pas couvert par des intervalles précédemment mis dans le glouton, ils sont aussi couvert par cette solution optimale (les deux solutions coïncident jusque là): on peut procéder comme dans le cas précédent et supprimer tous les intervalles couvrants $x_i$ dans la solution optimale et les remplacer par $[x_i, x_i + 1]$ pour continuer de couvrir tous les réels. Ceci viole notre hypothèse puisque :
1. le nombre d'intervalle conserver est plus petit ou égale à la solution optimale initiale : c'est donc également une solution optimale
2. elle coïncide plus longtemps avec notre glouton.

Réservation SNCF

On suppose que $n$ personnes veulent voyager en train un jour donné. La personne $i$ veut prendre le train $t_i$.

Les données du problème sont :

$K$ trains partent dans la journée,
le train $j$ part avant le train $j+1$,
chaque train ne peut contenir plus de $P$ passagers.

Solution possible ?

Proposez un algorithme qui vérifie que pour un nombre de trains donné et une liste de trains choisis, il est possible de faire voyager tout le monde.

corrigé

Une solution en $\mathcal{O}(n+K)$ :

d = [0] * K

for i in range(n):
    d[t[i]] += 1

for t in range(K):
    if d[t] > P:
        print("le train", t, "contient", d[t] - P, "passagers de trop.")

On suppose maintenant que la personne $i$, si elle ne peut pas prendre le train $t_i$ parce qu’il est complet, accepte de prendre un des trains suivants (s’il y en a un).

Solution approchée

Proposez un algorithme minimisant l'attente globale pour faire voyager tous les voyageurs.

corrigé

for i in range(n):
    while d[t[i]] > P:
        d[t[i]] -= 1
        t[i] += 1

A chaque itération de la boucle for, le passager $i$ est placé dans le premier train possible qui part après son train initialement voulu si celui-ci est plein.

Notez que cet algorithme permet de faire partir tous les voyageurs dans leur train initial s'il était non plein au d´part.

Cette solution est optimale pour la fonction $\sum_{i\geq 1}(t'[i] - t[i])$ où $t'[i]$ est le train effectivement pris par le passager $i$.

Une quête d'essence

Une route comporte $n$ stations services numérotées dans l’ordre du parcours, de $0$ à $n-1$. La distance du départ de la station $i$ est de $d_i$ kilomètres et on considère que $d[0] = 0$.

Le but est d'atteindre la dernière station de la route avec un réservoir de $L$ litres d'essence, en considérant qu'un litre d'essence permet de faire 1 kilomètre.

Admissibilité

Donnez une condition nécessaire et suffisante pour que l'automobiliste puisse parcourir toute la route jusqu'à la dernière station service.

corrigé

Il faut et il suffit que les stations services soient éloignées de moins de $L$ kilomètres.

On essaie de minimiser les arrêts pour rallier la dernière station du parcours. On suppose de plus que l'on part réservoir vide.

Minimum d'arrêts

Écrivez un algorithme glouton qui donne le nombre minimum de stations auxquelles il faut mettre de l'essence dans le réservoir pour arriver à destination, en supposant que le réservoir est initialement vide.

corrigé

Il faut aller le plus loin possible à chaque fois : la prochaine station est la station la plus éloignée dont la distance est inférieure à $L$.

S = [0]
for i in range(2, n):
    s = S[-1]
    if d[i] - d[s] > L;
        s.append(i - 1)

Soit $s_i$ la première station d'une solution optimale qui ne correspond pas avec la station $g_i$ choisie par le glouton. On a :

$i>0$ puisque la première station est la station de départ
$s_{i-1} = g_{i-1}$

On en conclut que $s_i < g_i$ et que l'on peut choisir $g_i$ comme $i$ ème choix pour la solution optimale et que, comme justement la solution est optimale, $s_{i+1} > g_i$ sinon on aurait pu s'en passer.

Le raisonnement précédent montre que l'on peut construire une solution optimale qui coïncide avec le glouton : le glouton est optimal.

On suppose que le prix de l'essence à la station $i$ vaut $p_i$.

Prix fluctuant

Donnez un algorithme glouton optimal permettant de réaliser le parcours au prix minimum.

corrigé

On considère les stations par prix croissants et on leur associe à chacune un recouvrement de taille $L$.

Dans l'exemple ci-dessous on considère que l'ordre de prix croissant est le nombre, que chaque case fait 1km et que $L=10$ :

1111111111
               2222222222
      3333333333
         4444444444
1     3  4     2        5   : ordre des prix
1     2  3     4        5   : ordre dans le parcours

Pour chaque kilomètre on prend ensuite la station dont le prix est le plus faible :

1111111111
               2222222222
          33333 
                   
1     3  4     2        5
1     2  3     4        5

On voit dans l'exemple que la station 4 est inutile et qu'il faut tout de même mettre de l'essence en passant à la station 3.

L'algorithme est alors le suivant :

K = [None] * d[n - 1]
ordre_stations = list(range(n))
ordre_stations.sort(key=lambda i: p[i])

for i in ordre_station:
    for k in range(d[i], d[i] + L):
        if K[k] is None:
            K[k] = i

Le nombre de litres qu'il faut ajouter lorsque l'on s'arrête à la station $i$ est le nombre de $i$ conservé dans la liste :

station_essence_achat = [K.count(i) for i in range(n)]

La preuve de l'optimalité vient du fait que l'essence mise à la station $i$ permet de faire la distance allant de $d_i$ à $d_i + L$. On a gardé que les kilomètres ne pouvant pas être couvert par une station ayant un prix inférieur.

Problèmes d'ordonnancements

Les problèmes d'ordonnancements sont très importants car nombre de problèmes courants peuvent s'écrire sous cette forme. Nous allons voir dans cette partie quelques exemples où l'approche gloutonne est optimale.

Ordonnancement avec pénalité

Comme dans le cours mais chaque tâche a un coût si on ne la réalise pas à temps.

Le but est de minimiser la somme des pénalités.

corrigé

Tout pareil.

Il suffit de dire que la pénalité est un gain qu'on cherche à maximiser : on réalisera en priorité les tâches avec la plus grande pénalité et donc on minimisera les pénalités des tâches non effectuées.

Ordonnancement avec départ différé

On suppose que l'on a $n$ tâches à réaliser par un unique ouvrier et chaque tâche $1\leq i \leq n$ met $p_i$ unités de temps à être effectuée. Une fois que l'ouvrier commence une tâche, il la termine : s'il effectue la tâche $i$, il ne fait rien d'autre pendant $p_i$ unités de temps.

On veut minimiser la somme des débuts de réalisations des tâches.

Formalisation du problème

En supposant que l'on a effectué les tâches dans l'ordre $\sigma_1, \dots, \sigma_n$ :

donnez le temps minimum de départ et de fin des tâches $\sigma_1$, $\sigma_2$ et $\sigma_3$
en déduire que la valeur de la somme totale des temps de départ des tâches vaut $\sum_i(n-i)p_{\sigma_i}$

corrigé

la tâche $\sigma_1$ a commencé en 0 et a fini en $p_{\sigma_1}$
la tâche $\sigma_2$ a commencé en $p_{\sigma_1}$ et a fini en $p_{\sigma_1} + p_{\sigma_2}$
la tâche $\sigma_3$ a commencé en $p_{\sigma_1} + p_{\sigma_2}$ et a fini en $p_{\sigma_1} + p_{\sigma_2} + p_{\sigma_3}$

On a donc la formule suivante pour donner la somme de toutes les débuts de tâches :

$$ T = \sum_{1\leq i \leq n}( \sum_{1\leq j < i}p_{\sigma_j}) = \sum_i(n-i)p_{\sigma_i} $$

Exemple

Quel est l'ordre d'exécution des tâches minimisant la somme des débuts de tâches pour trois tâches de temps de réalisation $p_1 = 1$, $p_2 = 3$ et $p_3 =5$.

corrigé

Pour les 3 tâches, il y a 6 ordonnancements possibles qui donnent respectivement :

1 puis 3 puis 5 : $T = 2 \cdot 1 + 1 \cdot 3 = 5$
1 puis 5 puis 3 : $T = 2 \cdot 1 + 1 \cdot 5 = 7$
3 puis 1 puis 5 : $T = 2 \cdot 3 + 1 \cdot 1 = 7$
3 puis 5 puis 1 : $T = 2 \cdot 3 + 1 \cdot 5 = 11$
5 puis 1 puis 3 : $T = 2 \cdot 5 + 1 \cdot 1 = 11$
5 puis 3 puis 1 : $T = 2 \cdot 5 + 1 \cdot 3 = 13$

L'exemple précédent a dû vous donner une idée de l'ordre associé au glouton :

Ordre d'exécution des tâches

Donnez (et prouvez) un algorithme glouton permettant de trouver l'ordre optimal d'exécution des tâches pour minimiser la valeur moyenne des débuts de réalisations.

corrigé

Minimiser la valeur moyenne des débuts de réalisation minimise $T/n$. Il suffit donc de minimiser $T$.

L'ordre selon lequel il faut ordonner les tâches est par durée décroissante. S'il existait en effet $i < j$ tel que $p_{\sigma_i} > p_{\sigma_j}$ changer les deux tâches diminuerait strictement $T$ puisque $n-i > n-j$. Cet ordre donne directement l'algorithme glouton :

On trie les tâches par durée croissante
Pour chaque tâche dans cet ordre:
    réaliser cette tache

On suppose maintenant que toutes les tâches ne sont pas immédiatement disponibles. Chaque tâche $i$ a maintenant une date $d_i$ à partir de laquelle elle peut être réalisée.

Départs différés

Donnez (et prouvez) un algorithme glouton permettant de trouver l'ordre optimal minimisant la valeur moyenne des débuts de réalisations.

corrigé

Le même raisonnement que précédemment montre que l'on peut ordonner les tâches par $d_i + p_i$ croissants.

On suppose maintenant que l'ouvrier peut mettre en pause la réalisation d'une tâche puis la reprendre ultérieurement. Par exemple il peut commencer la tâche $i$ de temps de réalisation $p_i = 5$, la réaliser pendant 2 unités de temps, puis la mettre en pause pour réaliser la tâche $j$ puis, une fois la tâche $j$ terminée, reprendre la tâche $i$ et la finir en y passant les 3 unités de temps restantes.

Tâches fragmentables

Donnez (et prouvez) la méthode permettant de minimiser la moyenne des débuts de chaque tâche.

corrigé

On peut à chaque unité réaliser une unité de temps de la tâche qui se finit au plus tôt parmi les tâches que l'on peut réaliser. Ceci garantit que les tâches sont bien réalisées de la plus rapide à la plus lente.

Ordonnancement avec retard

On suppose que pour mener à bien un projet, on doit réaliser $n$ tâches où chaque tâche $t_i$ a :

une durée de réalisation : $d_i$
un temps de fin conseillé : $f_i$

Si on note $s_i$ le début de la réalisation de la tâche $t_i$ on définit son retard par :

$$ r_i = \max(0, s_i + d_i - f_i) $$

Si $r_i > 0$ la tâche $t_i$ est en retard. Le but du problème est de trouver un algorithme glouton qui affecte à chaque tâche son début et qui minimise le retard maximum : $$R = \max_{1\leq i \leq n} r_i$$

Comme on n'a qu'un seul ouvrier pour réaliser les tâches, on ne peut créer qu'une tâche à la fois.

Premières propriétés

Montrez que le retard d'une solution ne peut pas augmenter si l'on supprime les temps d'inactivité de celle-ci : l'ouvrier enchaîne les tâches sans s'arrêter jusqu'à ce que toutes les tâches aient été réalisées.
En déduire que la solution de notre problème est un ordonnancement des tâches selon un ordre particulier : c'est un algorithme glouton sans étape de choix (toutes les tâches sont dans la solution).

corrigé

Si l'on réduit l'inactivité de l'ouvrier, les tâches vont commencer plus tôt, donc $s_i$ va diminuer et donc $r_i$ aussi : $R$ ne peut que diminuer.

La remarque précédente nous indique que l'ouvrier doit commencer une nouvelle tâche immédiatement après avoir fini la précédente.

On suppose que les tâches $(t_i)_{1\leq i \leq n}$ sont rangées dans un certain ordre. Écrivez l'algorithme qui calcule le retard maximum pour cet ordre. Quelle est sa complexité ?

Mauvais ordres

Montrez que les ordres suivants ne sont pas optimaux :

Les tâches triées par durée décroissante.
Les tâches triées par durée croissante.

corrigé

Durée croissante :

$d_1 = 1$, $f_1 = 11$
$d_2 = 10$, $f_2 = 10$

Durée décroissante :

$d_1 = 10$, $f_1 = 11$
$d_2 = 1$, $f_2 = 1$

Ordre optimal

Montrez que si une solution possède deux tâches successives $t_{i}$ et $t_{i+1}$ telles que $f_{i} > f_{i+1}$, les échanger n'augmente pas le retard.

En déduire l'ordre optimal.

corrigé

On a $r_{i+1} = s_{i+1} + d_{i+1} - f_{i+1} = s_{i} + d_{i} + d_{i+1} - f_{i+1}$, donc :

$r_{i+1} \geq s_{i} + d_{i+1} - f_{i+1}$
$r_{i+1} \geq s_{i} + d_{i+1} + d_{i} - f_{i}$, si $f_{i}> f_{i+1}$

L'échange des deux tâches n'augmente pas le retard maximal.

Si l'on range les éléments par taille de fin demandée croissante, on est alors minimal car $f_{i}< f_{i+1}$ pour tout $i$ est équivalent à $f_{i}< f_{j}$ pour tout $i<j$.

Glouton pas optimal mais pas mal

Les algorithmes gloutons suivants ne sont pas optimaux, mais on peut démontrer qu'ils permettent tout de même de n'être pas trop éloigné de celle-ci.

Définition

Un algorithme est à performance garantie si sa solution est plus grande que $\alpha \cdot P(e)$ où $P(e)$ est la solution optimale pour une entrée $e$.

Empaquetage

On veut faire une partition de $n$ entiers en $m$ ensembles telle que la somme des entiers dans chaque ensemble ne dépasse pas $K$. Le but est de minimiser $m$ sachant les $n$ entiers et la borne $K$.

Applications

Donnez quelques cas d'application concret de ce problème.

corrigé

Le transport de marchandises, le déchargement d'un cargo dans des camions, ...

Commencez par montrer la propriété suivante :

Solution optimale

Le nombre minimum d'ensembles est plus grand que la somme de tous les entiers divisée par $K$.

corrigé

Si l'on a $m$ ensembles, on peut ranger au maximum une somme valant $K\cdot m$ qui doit donc être supérieure à la somme de tous les entiers.

On va utiliser l'algorithme glouton suivant :

Es = []
E = []
pour chaque entier ni:
    si somme(E) + ni ≤ K:
        ajoute ni à E
    sinon:
        ajoute E à Es
        E = [ni]

Propriété

Montrez que la somme des entiers de deux éléments successifs de Es est strictement plus grand que $K$.
En déduire que la somme de tous les entiers est plus grande que $K \cdot \frac{m}{2}$

corrigé

On ne crée un nouvel ensemble que si l'entier courant ne tient pas dans l'ensemble considéré : la somme de ces deux ensembles consécutifs est donc strictement plus grande que $K$.

Dans le cas où $m$ est pair on a alors :

somme(E[0]) + somme(E[1]) > K
somme(E[2]) + somme(E[3]) > K
somme(E[4]) + somme(E[5]) > K
...

Et on en déduit, si $m$ est pair, que : somme(E[0]) + ... + somme(E[m-1]) > K * m / 2. Le calcul est identique si $m$ est impair.

Les deux propriétés précédentes doivent vous permettre de prouver :

Performance garantie

Montrez que l'algorithme précédent trouve au maximum 2 fois la solution optimale.

corrigé

Clair en utilisant les 2 questions précédentes.

La borne peut être atteinte en utilisant uniquement deux types de caisses : des caisse de volume 1 et $K/2$.

Cas le pire

Montrez qu'en utilisant des caisses de volume 1 et $K/2$ l'ordre dans lequel les caisses sont examinées par le glouton peut aller du simple au (presque) double en nombre de solutions.

corrigé

Si l'on a $n_1$ caisses de volume $K/2$ et $n_2$ caisses de volume 1, le nombres optimal de caisses est : $n_1 / 2 + n_2/K$. L'ordre est bien optimal puisque toutes les caisses sauf une seront remplies au maximum.

En examinant les caisses alternativement de volume 1 et $K/2$, et en supposant que $n_1 \geq n_2$ on aura besoin de $n_1 + (n_2-n_1)/K = n_1(1-1/K) + n_2/K$ caisses. Si $n_1 = n_2 = 2K$, le nombre optimal sera $K +2$ et celui obtenu par le glouton de $2K$. Ce rapport de l'optimum sur le glouton va tendre vers 1/2 lorsque $K$ grandit.

La question précédente montre que quel que l'on est au pire 2 fois moins bon aue la solution optimale, quel que soit l'ordre dans lequel on regarde les marchandises !

On peut cependant faire mieux si l'on connait toutes les marchandises avant de les empaqueter et en les examinant par volume décroissant. Il a en effet été prouvé que la solution du glouton était toujours inférieure à 11/9 fois l'optimale plus 4.

Équilibrage de charge

On appelle équilibrage de charge le problème suivant :

On possède $m$ machines et $n$ tâches à effectuer.
Chaque tâche $j$ nécessite $t_j$ unités de temps pour être effectuée par une machine.
Pour chaque machine $i$, on associe l'ensemble $M_i$ des tâches effectuées par celles-ci, et on note $T_i$ le temps passé à effectuer ces tâches : $T_i = \sum_{j \in M_i} t_j$.

On cherche à trouver les ensembles $M_i$ permettant de minimiser la quantité : $\max_{1\leq i \leq m} T_i$. On note $T^\star$ ce minimum.

Quelques propriétés

Montrez que l'on a $T^\star \geq \max_{1 \leq j\leq n} t_j$.
Montrez que l'on a $T^\star \geq \frac{1}{m}\sum_{1 \leq j\leq n} t_j$ (attention, c'est bien $\frac{1}{m}$ et non $\frac{1}{n}$).

corrigé

La première inégalité vient du fait que toute tâche doit être effectuée par une machine : la machine $i$ qui réalisera la tâche de plus longue durée aura un $T_i$ plus grand que cette durée.

La seconde inégalité découle du fait que $\min T_i \leq \frac{1}{m}\sum_i T_i \leq \max_i T_i$, et que $\sum_i T_i = \sum_j t_j$. L'inégalité est ainsi vraie pour toute assignation donc également pour l'assignation optimale.

L'algorithme glouton que l'on utilisera pour résoudre le problème consistera à ajouter itérativement une tâche à la machine $i$ réalisant $T_i = \min_{1\leq j \leq m} T_j$.

Un algorithme glouton

Dans quel ordre proposez-vous de ranger les tâches ? Justifiez votre réponse.
Montrez que s'il y a $m$ tâches ou moins à classer, l'algorithme glouton trouve la solution optimale.

corrigé

Il vaut mieux répartir les tâches longues sur plusieurs machines, par exemples pour trois machines la répartition $[(4,), (4,), (1, 1, 1)]$ est préférable à la répartition $[(1, 4), (1, 4), (1,)]$ de 5 tâches de durée 4, 4, 1, 1 et 1.

On rangera donc les tâches par durées décroissantes.

Il est clair que s'il y a moins de $m$ tâches à ranger chaque machine aura au plus 1 tâche : la répartition sera optimale.

On considère une réalisation de l'algorithme. Soit $i^\star$ la machine réalisant $T_{i^\star} = \max_{1\leq i \leq m} T_i$ à la fin de l'algorithme, et $j$ l'indice de la dernière tâche qui lui a été assignée au cours de l'exécution de l'algorithme.

Propriétés

Montrez qu'à la fin de l'algorithme, on a $T_{i^\star} -t_j \leq T_k$ pour tout $k$.
En déduire que $T_{i ^\star} - t_j \leq \frac{1}{m}\sum_{1\leq k\leq m}T_k$.
Déduire de la déduction que $T_{i ^\star} - t_j \leq T^\star$.
Puis que $T_{i ^\star} \leq 2 \cdot T^\star$.

corrigé

avant l'affectation de la tâche $j$ à la machine, son temps total était le plus faible. S'il y a eu des tâches d'affectées après la tâche $j$ elles l'ont été à d'autres machines qui ont augmenté leur temps total d'exécution, la propriété est donc toujours vrai à la fin de l'algorithme.
En sommant l'inégalité précédente pour toutes les machines on obtient : $m\cdot(T_{i^\star} -t_j)\leq \sum_{1\leq k\leq m}T_k$
vient directement du fait que $T^\star \geq \frac{1}{m}\sum_{1 \leq j\leq n} t_j$
clair puisque $t_j \leq \max t_k \leq T^\star$

Les propriétés précédentes nous permettent de déduire que l'algorithme glouton est à performance garantie :

Performances

Montrez que la solution proposée par l'algorithme glouton est au pire 2 fois moins bonne que la solution optimale.
Montrer que cette performance est atteinte quelque soit l'ordre des tâches utilisé.

corrigé

La première partie est évidente et comme les inégalités ne dépendent pas de l'ordre choisit la seconde également.

Plan de tables

Une de vos cousines se marie et vous a demandé de faire le plan de table du repas de noces. Pour maximiser la convivialité du repas elle vous demande :

de ne mettre à chaque table que des personnes qui s'entendent;
d'avoir un petit nombre de tables.

On ne demande pas que le nombre de tables soit minimum.

Modélisation

Un plan de table $P$ est une structure de données contenant :

une liste $\verb|NOMS|$ contenant le nom de tous les invités;
une liste $\verb|IC|$ d'incompatibilités où $\verb|IC[i]|$ contient un ensemble d'indices tel que si $\verb|j|$ est dans $\verb|IC[i]|$ alors $\verb|NOMS[i]|$ ne peut être à la même table que $\verb|NOMS[j]|$.

On suppose de plus que la relation d'incompatibilité est symétrique (si $\verb|j|$ est dans $\verb|IC[i]|$ alors $\verb|i|$ est dans $\verb|IC[j]|$). Par exemple si les invités sont : "tata Guillemette", "cousin Valentin", "tonton Julien", "papy François" et "soeur Manon" et que les relations sont :

"tata Guillemette" aime bien tout le monde
"papy François" n'aime personne à part "tata Guillemette"
"cousin Valentin" ne supporte pas "soeur Manon"

On a la structure de données suivante (où $\verb|{...}|$ représente des ensembles) :

$\verb|NOMS = ["tonton Julien", "papy François", "tata Guillemette", "cousin Valentin", "soeur Manon"]|$
$\verb|IC = [{1}, {0, 3, 4}, {}, {1, 4}, {3, 1} ]|$

Résoudre le problème revient à trouver un plan de table (chaque invité est associé à une table unique) valide (deux invités à une même table ne doivent pas avoir d'incompatibilité), c'est-à-dire créer une liste $\verb|tables|$ telle que :

chaque élément de $\verb|tables|$ est un ensemble d'indices tel que si $i \in \mbox{tables}[k]$ alors l'invité $\verb|NOMS[i]|$ est placé à la table numéro $k$
pour tout indice $i\geq 0$ strictement plus petit que le nombre d'invités, il existe un unique $k$ tel que $i \in \mbox{tables}[k]$
si $i, j \in \mbox{tables}[k]$ alors $j \notin \mbox{IC}[i]$

Montrez que quelles que soient les incompatibilités et le nombre d'invités, il existe un plan de table valide.
Justifiez que pour l'exemple, le nombre minium de tables est 3.
Combien de solutions à 3 tables différentes existe-t-il ?
Montrez que si l'on supprime l'incompatibilité entre "papy François" et "soeur Manon" dans l'exemple alors il existe une solution à 2 tables.

corrigé

Il suffit de mettre une personne par table pour satisfaire toutes les incompatibilités
"papy François" (1) doit être sur une table différente de "cousin Valentin" (3) et "soeur Manon" (4) qui eux-mêmes doivent être sur deux tables distinctes : il faut au minimum 3 tables. Comme l'affectation $[\{1, 2 \}, \{3, 0\}, \{4\}]$ fonctionne, 3 est bien le nombre minimum de tables pour réaliser l'affectation.
Comme "tonton Julien" ne peut être avec "papy François" il a 2 tables possibles et comme "tata Guillemette" peut aller partout elle a 3 choix. Le nombre total de choix est donc $2 \cdot 3 = 6$
$[\{1, 2, 4 \}, \{3, 0\}]$ est possible.

On se propose d'écrire un algorithme glouton permettant de résoudre le problème :

créer une liste $\verb|ordre|$ contenant les indices de tous les convives;
créer une liste vide $\verb|tables|$
pour chaque élément $\verb|i|$ de $\verb|ordre|$, ajouter $\verb|i|$ à la première table de $\verb|tables|$ possible (la première table ne contenant aucune de ses incompatibilités) si elle existe ou en créer une nouvelle sinon.

Pourquoi l'algorithme précédent est-il glouton ?
Démontrez qu'il donne bien une réponse au problème quel que soit $\verb|ordre|$. Quel ordre utiliseriez-vous par défaut pour résoudre le problème ? Et pourquoi ?
Cet algorithme est efficace mais on va voir qu'il dépend fortement de la liste $\verb|ordre|$. Montrez que l'algorithme peut rendre un nombre de tables strictement plus grand que 2 alors qu'il existe une solution à deux tables.

corrigé

C'est un algorithme glouton puisqu'il affecte itérativement chaque convive à une table qui ne changera plus.
On affecte une personne à une table que lorsque c'est possible, on obtient donc bien finalement une solution au problème. On peut choisir les convives par nombre d'incompatibilité décroissante car à chaque choix on placera le convive à une table qui dépend du nombre d'incompatibilité déjà placées il faut donc placer les personnes à faible nombre d'incompatibilité à la fin.
On suppose que l'on utilise l'ordre $a$, $b$, $c$ puis $d$ avec les incompatibilités :
- $a$ et $b$
- $b$ et $d$
- $c$ et $d$

En utilisant la structure de l'algorithme glouton :

démontrez que le nombre minimum de tables ne peut excéder le nombre maximum d'incompatibilités pour une personne plus 1;
donnez un cas où cette borne est atteinte;
donnez un cas où on peut faire strictement mieux que cette borne.

corrigé

A chaque étape le convive sera placé à la première table possible. Le cas le pire arrivant si toutes ses incompatibilités ont déjà été placées à des tables différentes.
La borne est atteinte si tout le monde déteste tout le monde.
Si tout le monde aime tout le monde il suffit d'une table