C16.1a : Algorithme glouton (rappel)

Les algorithmes gloutons

L'optimisation combinatoire consiste à trouver, parmi un ensemble fini de combinaisons, la (les) combinaison(s) qui répond(ent) de façon optimale à un critère donné.

• Une façon de résoudre exactement ce problème consiste à appliquer de façon exhaustive le critère à toutes les combinaisons pour ne garder que la combinaison dont le résultat est optimal. Cette méthode peut, dans de nombreux cas, prendre un temps trop long.

• Les algorithmes gloutons permettent de trouver une solution satisfaisante (mais pas forcément la solution optimale) en appliquant le critère localement, de proche en proche.

TD - Le problème du sac à dos

Présentation du problème

Émeline a prévu de partir en vacances dans un endroit sans connexion internet.

Elle souhaite néanmoins pouvoir écouter de la musique. Elle envisage pour cela d'emporter un lecteur numérique et d'y stocker quelques morceaux.

Mais son lecteur dispose d'un espace mémoire limité (par exemple 10 Mio).

Les fichiers de musique qu'elle peut sélectionner sont caractérisés par :

- leur taille (la place qu'ils occupent en mémoire)

- la durée d'écoute.

Émeline souhaite avoir une durée d'écoute totale la plus grande possible.

Résolution du problème par la méthode gloutonne

💻 En vous appuyant sur un algorithme glouton, proposer un programme qui va permettre à Émeline de résoudre son problème.

Vous disposez pour cela du fichier csv qui contient la liste des musiques d'Émeline (fichier : musiques.csv). Les données seront récupérées sous la forme d'une liste de dictionnaires.

# =====
# Importation des modules
#=====
import csv

# =====
# Fonctions
# =====
def csv_to_liste(nom_fichier):
    liste = []
    with open(nom_fichier, 'r', encoding='utf-8') as objFichier:
        objDatasCsv = csv.DictReader(objFichier, delimiter=';')
        for ligne in objDatasCsv:
            liste.append(dict(ligne))
    return liste

def affiche_liste_musiques(liste_musiques):
    for musique in liste_musiques:
        print(musique["Titre"] + " - "
              + musique["Artiste"] + " - "
              + musique["Durée"] + " - "
              + musique["Taille"])

def affiche_infos(liste_musiques):
    taille = 0
    duree = 0
    for musique in liste_musiques:
        duree = duree + int(musique['Durée'])
        taille = taille + int(musique['Taille'])
    print('Durée : ' + str(duree))
    print('Taille : ' + str(taille))
    print('Nombre de morceaux : ' + str(len(liste_musiques)))

def cle_tri_ratio(obj:dict)-> float:
    return int(obj["Durée"])/int(obj["Taille"])

def creer_liste_musiques(liste_musique:list, taille_maxi:int)->list:
    # Tri de la liste d'objets
    liste_musique.sort(key=cle_tri_ratio, reverse = True)
    # Remplissage du smartphone
    liste = []
    taille_accumulee = 0
    i_musique = 0
    while taille_accumulee + int(liste_musique[i_musique]["Taille"]) <= taille_maxi and i_musique < len(liste_musique) - 1:
        liste.append(liste_musique[i_musique])
        taille_accumulee = taille_accumulee + int(liste_musique[i_musique]["Taille"])
        i_musique = i_musique + 1
    return liste

# =====
# Programme principal
# =====
toutes_les_musiques = csv_to_liste('musiques.csv')
liste_smartphote = creer_liste_musiques(toutes_les_musiques, 10*1024*1024)
affiche_liste_musiques(liste_smartphote)
affiche_infos(liste_smartphote)

TD - Exemple du voyageur de commerce (difficile)

Présentation du problème à résoudre

Un voyageur souhaite visiter les cinq préfectures des cinq départements des Hauts-de-France : Lille, Arras, Laon, Beauvais et Amiens. Dans un soucis écologique, il souhaite, lors de son voyage, parcourir la plus petit distance possible.

Carte des Hauts-de-France avec les cinq préfectures de département

Il a relevé sur le site openstreetmap.org les distances entre chaque préfecture en km et les a consignées dans un tableau à double entrée.

	Lille	Arras	Laon	Beauvais	Amiens
Lille	0	54	156	195	142
Arras	54	0	129	154	62
Laon	156	129	0	134	125
Beauvais	195	154	134	0	62
Amiens	142	62	125	62	0

Résolution exhaustive

Première approche

🖊️ 1. Proposer une démarche pour résoudre le problème du voyageur : c'est-à-dire lui trouver, avec certitude, le voyage le plus court.

Généralisation de l'approche exhaustive

On souhaite généraliser le problème avec un voyage où le nombre de villes à visiter est \(N\).

🖊️ 2. Combien de voyages différents sont possibles pour visiter \(N\) villes ?

🖊️ 3. La résolution exhaustive, à la main, pour un voyage de \(10\) villes vous semble-t-elle possible ?

🖊️ 4. La résolution exhaustive, à l'ordinateur, pour un voyage de \(100\) villes vous semble-t-elle possible ?

Résolution approchée avec l'algorithme glouton

Lorsqu'il y a beaucoup de villes, une approche simplifiée consiste, pour le voyageur, a adopter la démarche suivante : à chaque ville, il choisit comme ville suivante, la ville la plus proche parmi toutes celles qu'il n'a pas encore visité.

💻 Proposer un programme qui réponde au problème posé.

Aide sur les variables à utiliser

On pourra utiliser deux variables globales :

• Une liste L_villes avec les chaines de caractères correspondant aux noms des villes. Dans ce cas, chaque ville sera caractérisée par un numéro correspondant à sa position dans cette liste.
• Une liste de liste LL_distances correspondant aux distances entres les villes.

On pourra envisager les fonctions suivantes :

• Une fonction supprime_ville(num_ville, liste_num_villes) qui renvoie une liste identique à liste_num_villes, mais sans num_ville ;

• Une fonction distance(num_ville1, num_ville2) qui renvoie la distance entre les villes dont les numéros sont num_ville1 et num_ville2 ;

• Une fonction ville_suivante(num_ville, liste_num_villes_restantes) qui détermine, parmi les villes de la liste liste_num_villes_restantes, le numéro de la ville la plus proche de num_ville ;

• La fonction meilleur_voyage(num_ville_depart, liste_num_villes).
Cette fonction pourra utiliser les variables locales suivantes :

- un entier pour la ville actuellement visitée
- une liste pour les villes qu'il reste à visiter
- une liste pour les villes déjà visités

2 - Résolution exhaustive

Pour déterminer à avec certitude le voyage le plus court, il faut faire la liste de tous les voyages possibles et prendre le plus court.

Lorqu'il y a \(N\) villes à visiter, en prenant en compte que l'on peut partir de n'importe quelle ville, le nombre de voyages est \(N!\), \(factoriel(N)\).

\((10)! = 3628800\). Il n'est donc pas envisageable de déterminer tous les chemins à la main !

\((100)! = \pu{9,3E157}\). Il n'est donc pas envisageable de déterminer tous les chemins, même avec un ordinateur très puissant !

3 - Résolution approchée avec l'algorithme glouton

L_villes = ["Lille", "Arras", "Laon", "Beauvais", "Amiens"]
LL_distances = [[0, 54, 156, 195, 142],
                [54, 0, 129, 154, 62],
                [156, 129, 0, 134, 125],
                [195, 154, 134, 0, 62],
                [142, 62, 125, 62, 0]]

def distance(num_ville1, num_ville2):
    return LL_distances[num_ville1][num_ville2]

def ville_suivante(num_ville, liste_num_villes_restantes):
    """
    Renvoi num de la ville de liste_num_villes_restantes qui est la plus proche de num_ville)
    Précondition : il faut que num_ville ne soit pas dans liste_num_villes_restantes
    Paramètres :
        num_vill (int) : num d'une ville
        liste_num_villes_restantes (int) : liste de num des villes restantes
    """
    num_ville_suivante_min = liste_num_villes_restantes[0]
    dist_min = LL_distances[num_ville][num_ville_suivante_min]
    for num_ville_suivante in liste_num_villes_restantes:
        dist = distance(num_ville, num_ville_suivante)
        if dist < dist_min:
            dist_min = dist
            num_ville_suivante_min = num_ville_suivante
    return num_ville_suivante_min

def supprime_ville(num_ville, liste_num_villes):
    L = []
    for num in liste_num_villes:
        if num != num_ville:
            L.append(num)
    return L

def meilleur_voyage(num_ville_depart, liste_num_villes):
    ville_actuelle = num_ville_depart
    liste_num_villes_visitees = [ville_actuelle]
    liste_num_villes_restantes = supprime_ville(ville_actuelle, liste_num_villes)

    while len(liste_num_villes_restantes) >= 1:
        ville_actuelle = ville_suivante(ville_actuelle, liste_num_villes_restantes)
        liste_num_villes_visitees.append(ville_actuelle)
        liste_num_villes_restantes = supprime_ville(ville_actuelle, liste_num_villes_restantes)

    return liste_num_villes_visitees

def distance_totale(liste_num_villes):
    distance = 0
    for i in range(len(liste_num_villes)-1):
        numDep = liste_num_villes[i]
        numArr = liste_num_villes[i+1]
        distance = distance + LL_distances[numDep][numArr]
    return distance

# === Programme principal ===
ville_depart = 2
liste_villes = [0, 1, 2, 3, 4]

liste_voyage = meilleur_voyage(ville_depart, liste_villes)
print("Voyage : ")
for num_ville in liste_voyage:
    print("   " + L_villes[num_ville])
print("")

print("Distance = " + str(distance_totale(liste_voyage)))