Un algoithme glouton pour l'allocation de ressource

Introduction⚓︎

Nous allons résoudre le problème de l'allocation de salles de cinéma pour la projection de films. Le cinéma dispose de 20 films à projeter chaque jour, entre 9h et 23h. Chaque film a une heure de début et de fin, et notre objectif est de trouver la meilleure manière de les distribuer dans les différentes salles disponibles en minimisant les conflits d'horaires.

Variables globales⚓︎

Debut = 9 # heure ouverture du cinéma

Fin = 23 # heure fermeture du cinéma

Duree_max = 4 # Durée maximum d'un film

Nb = 20 # Nb de films

Étapes du Projet⚓︎

Génération des films avec des heures de début et de fin aléatoires
Affichage des horaires sous forme de graphique
Tri des films par heure de fin
Application de l'algorithme glouton pour affecter les films aux salles
Affichage des films par salle

1 - Génération des Films⚓︎

Générer aléatoirement des films avec des heures de début, de fin et une durée maximale, puis les organiser sous forme d'une liste. Chaque film possèdera 4 éléments:

une heure de début
une heure de fin
un identifiant
une couleur d'affichage (liste de 3 flottants correspondant à [R,V,B])

Code à compléter⚓︎

Python

from random import randint, uniform

def Generation(Debut, Fin, Duree_max, Nb):
    Res = []
    for i in range(Nb):
        Di = randint(Debut, Fin-1)  # Début aléatoire du film
        Reste = ... # Calcul de la durée qui reste avant la fermeture du ciném
        Reste = min(Reste, Duree_max)
        Duree = randint(...) # a compléter
        Fi = Di + Duree  # Heure de fin du film
        Col = [uniform(0,1), uniform(0,1), uniform(0,1)]  # Couleur aléatoire pour chaque film
        ind = i + 1  # Identifiant unique pour chaque film
        R = [Di, Fi, ind, Col]  # Liste avec début, fin, id et couleur
        Res.append(R)
    return Res

Nous pouvons générer les films avec Res = Generation(Debut, Fin, Duree_max, Nb)

2 - Affichage des Films⚓︎

Afficher les films sous forme graphique à l'aide de Matplotlib, pour visualiser les horaires de projection.

Python

from matplotlib import pyplot as plt
plt.close('all')

def Affiche(LR, Type, trie):
    n = len(LR)
    y = 0
    for i in range(n):
        R = LR[i]
        x1, x2, ind, Col = R
        y = y + 1 if trie else ind # Permet d'afficher les films soit dans l'ordre de la liste soit par indice de film
        plt.plot([x1, x2], [y, y], Type, color=Col, linewidth=3)
    plt.yticks([i + 1 for i in range(Nb)])
    plt.show()

3 - Tri des Films par Heure de Fin⚓︎

Trier les films par heure de fin afin de faciliter l'affectation dans les salles.

Plutôt que le tri à bulles, nous allons utiliser la fonction sorted qui peut prendre un argument key, cela permet de trier des listes par un de leur éléments

Exemple avec des couples de coordonnées de points⚓︎

Python

# Liste de couples (x, y)
coordonnees = [(1, 3), (4, 1), (2, 5), (3, 2), (5, 4)]

# Tri de la liste par ordonnée (le deuxième élément du tuple)
coordonnees_triees = sorted(coordonnees, key=lambda x: x[1])

code du tri des films par heure de fin⚓︎

Python

def Tri_fin(LF):
    LF_Tri = sorted(LF, key=lambda x: x[...]) # A compléter pour trier par heure de fin des films
    return LF_Tri


L_Triee = Tri_fin(Res)
Affiche(L_Triee,'-',True)

4 - Résolution avec l'Algorithme Glouton⚓︎

Utiliser l'algorithme glouton pour allouer les films dans les différentes salles. L'idée est de toujours choisir le film suivant qui commence après la fin du dernier film projeté dans une salle.

Python

def Resolution(L_triee):
    liste_par_salle = []
    while len(L_triee): # Boucle non bornée, tant qu'il reste des films à affecter à une salle
        salle_actuelle = [L_triee.pop(0)]  # Prendre le premier film pour la nouvelle salle
        heure_fin = salle_actuelle...  # heure_fin prend la valeur de l'heure de fin du dernier film choisi pour cette salle, au début celle du 1er film
        choix = [] # sert à garder en mémoire les films qui seront ajoutés à la salle actuelle 

        for i in range(len(L_triee)): # parcours des films possibles pour cette salle
            debut, fin = L_triee[i][:2] # heure de debut et fin du film étudié
            if ...:  # teste si le film commence après la fin du dernier projeté
                choix.append(i)
                heure_fin = ... # Mise à jour de l'heure de fin

        # Ajout des films sélectionnés à la salle
        choix.reverse()
        salle_actuelle += [L_triee.pop(i) for i in choix]  # Ajouter les films compatibles dans la salle
        salle_actuelle.sort(key=lambda x: x[0])  # Trier par l'heure de début
        liste_par_salle.append(salle_actuelle)

    return liste_par_salle

5 - Affichage de la liste regroupée par salle⚓︎

Nous pouvon utiliser la fonction affichage en affichant les films regroupés par salle.

Python

liste_par_salle =  Resolution(L_Triee)
liste_globale_par_salle =  []
for i in range(len(liste_par_salle)):
    liste_globale_par_salle += liste_par_salle[i]

Affiche(liste_globale_par_salle,'-',True)