Problème de la réservation de gymanses
Introduction du problème
Dans un lycée, on décide d'organiser des olympiades sportives. Pour la réalisation du planning, chaque responsable de sport, a soumis à l'organisation les créneaux pour lesquels iels ont besoin d'un gymnase.
Malheureusement, le lycée ne comporte pas assez de gymnases pour satisfaire tous les sports. On décide donc de chercher un algorithme qui permet au maximum de compétition de se produire sans se chevaucher.
Sport | Début | Fin |
|---|---|---|
Basket-ball | 9h00 | 10h30 |
Badminton | 9h30 | 10h45 |
Tennis de table | 10h15 | 11h15 |
Volley-ball | 10h30 | 12h00 |
Gymnastique | 11h00 | 11h45 |
Handball | 11h30 | 12h45 |
Escalade | 12h15 | 13h15 |
Danse | 12h30 | 13h30 |
Boxe française | 13h15 | 14h15 |
Futsal | 13h45 | 14h45 |
Définition : Problème des gymnases ou Problème de la sélection d'activité
Entrées :
activites: Une liste de couple d'entiers, chaque couple représente le début et la fin d'une activité ;nb_gymnase: Un entier représentant le nombre de gymnase.
Sortie :
edt: Une liste longueurnb_gymnase, chaque case contient une liste de couple qui représente les activités organisées dans un gymnase (les activités organisées dans un même gymnase ne pouvant se chevaucher).L'emploi du temps retenu étant celui qui permet d'organiser le plus d'activités.
Exemple : Exemple avec un gymnase
Si l'on prend un cas simplifié du début avec un seul gymnase et les sport qui finissent avant midi.
Sport | Début | Fin |
|---|---|---|
Basket-ball | 9h00 | 10h30 |
Badminton | 9h30 | 10h45 |
Tennis de table | 10h15 | 11h15 |
Volley-ball | 10h30 | 12h00 |
Gymnastique | 11h00 | 11h45 |
On peut organiser différent emploi du temps :
Basket-ball et Volley-ball
Badminton et Gymnastique
Tennis de table
On constate que le maximum est 2 activités, avec plusieurs combinaisons possibles et que le tennis de table n'est pas compatible avec les autres activités.
Complément : Nombre de combinaisons candidates
On peut s'intéresser au nombre de combinaisons possible en fonction du nombre d'activité et du nombre de gymnase.
Soit un problème à \(n\) activités et \(k\) gymnases.
Pour chaque activité, elle peut soit être annulée, soit dans l'un des \(k\) gymnases. Ce qui lui donne \(k+1\) états possibles.
Cela donne donc \((k-1)^n\) combinaisons candidates.
Ce nombre peut être abaissé quand on s'aperçois que certaines combinaisons ne sont pas possible car elles impliquent un chevauchement d'activités. Mais cela ne change pas beaucoup l'ordre de grandeur.
Nombre de combinaisons | Nombre d'activités | |||||
|---|---|---|---|---|---|---|
2 | 3 | 4 | 5 | 6 | ||
Nombre de gymnase | 1 | 4 | 8 | 16 | 32 | 64 |
2 | 9 | 27 | 81 | 243 | 729 | |
3 | 16 | 64 | 256 | 1 024 | 4 096 | |
4 | 25 | 125 | 625 | 3 125 | 15 625 | |
5 | 36 | 216 | 1 296 | 7 776 | 46 656 | |
6 | 49 | 343 | 2 401 | 16 807 | 117 646 | |
Si on prend \(n=80\) et \(k=10\) comme pour les Jeux Olympiques par exemple, on obtient un nombre de combinaison possible suppérieur au nombre d'atomes dans l'univers.
Remarque : Utilité de ce problème
Ce problème bien que d'apparence très limité dans son utilisation est aujourd'hui au cœur de l'informatique. Dans une version plus complexe, il est connus sous le nom de problème ordonnancement.
En effet, dans nos ordinateurs, afin de pouvoir faire plusieurs choses en même temps, notre OS découpe le temps d’exécution des processus en quanta qui doivent alors être exécuté sur un cœur de notre processeur.
Les quanta sont alors les activités et les cœurs du processeur, les gymnases.
Attention : Un problème d'apparence difficile
Cette version du problème, bien que d'apparence très compliquée, est en fait assez simple car il existe un algorithme optimal et efficace pour le résoudre.
Malheureusement dans sa version plus utile et complexe, il n'existe pas d'algorithme optimal rapide. On utilisera donc souvent une approximation utilisant la solution optimal de la version simple.