Exemples d'utilisation

En informatique, on retrouve fréquemment des problèmes d'optimisation comme par exemple le problème du rendu de monnaie. Les algorithmes gloutons sont utilisés pour résoudre ce type de problème.

Le Programme

---

Définition

Problème d'optimisation : problème dont on cherche à maximiser (ou minimiser) un résultat.

Un algorithme glouton est un algorithme qui vise à optimiser la résolution d'un problème en utilisant une approche particulière :

• On procède par étapes, en effectuant à chaque fois le meilleur choix possible.
• On ne revient jamais sur un choix déjà fait.
• Répétez ces étapes jusqu'à ce qu'une solution globale soit obtenue.

Selon le problème on utilise une méthode pour résoudre ce dernier. Il peut exister plusieurs instances qui donneront lieu à des résultats différents.

À un problème d'optimisation, on associe une fonction objective.

Prenons un exemple simple : la liste des 23 joueurs sélectionnés pour la coupe du monde :

Didier Desvilles est bien embêté : il doit choisir 23 joueurs pour aller jouer une compétition.
Dans cette optique, il décide d'utiliser une méthode simple: choisir le meilleur joueur possible pour chaque poste, puis le deuxième meilleur comme remplaçant.

Peu importe si les joueurs sélectionnés ne s'entendent pas forcément très bien, comme Olivier Gibrun et Karim Benzemb, l'important c'est de faire le meilleur choix à chaque étape.

Un algorithme glouton ne renvoie pas obligatoirement un résultat optimal, dans ce cas-là, on parle d'heuristique. Il renverra un résultat optimal pour chacun des sous-problèmes.

Un algorithme glouton ne revient pas sur un sous-problème déjà traité.

---

Exemple de problème d'optimisation : rendu de monnaie

Le problème du rendu de monnaie s'énonce de la façon suivante : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c'est-à-dire avec le nombre minimal de pièces et billets ?

On veut programmer une caisse automatique qui rend de façon optimale la monnaie (le moins de pièces/billets) :

Des exemples

Exemple 1 : - Système de monnaie : {1, 2, 5, 10} - Recherché : 14 - Résultat optimal : 10 + 2 + 2 (3 pièces)

Exemple 2 : - Système de monnaie : {1, 2, 5, 7, 10} - Recherché : 14 - Résultat optimal : 7 + 7 (2 pièces)

Algorithme

def rendu_monnaie(systeme, montant):
    reste = montant
    i = len(systeme) - 1
    resultat = []

    while reste > 0 and i >= 0:
        # On trouve le nombre de pièces de la valeur courante à rendre
        nb_pieces = reste // systeme[i]
        for _ in range(nb_pieces):  # Pour chaque pièce à rendre
            resultat.append(systeme[i])  # On ajoute cette pièce au résultat
            reste -= systeme[i]  # On met à jour le reste à rendre
        i -= 1  # On passe à la valeur inférieure dans le système

    return resultat

# Exemples d'utilisation
systeme_1 = [1, 2, 5, 10]
systeme_2 = [1, 2, 5, 7, 10]

print(rendu_monnaie(systeme_1, 14))  # Devrait afficher [10, 2, 2] qui est optimal pour le système_1
print(rendu_monnaie(systeme_2, 14))  # Devrait afficher [10, 2, 2] qui est non optimal car [7, 7] est mieux pour le système_2

Force brute avec le systeme_2 pour 14:

On cherche toutes les solutions possibles : - [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1] - [2, 2, 2, 2, 2, 2, 2] - [5, 5, 2, 2] - [7, 7] - [10, 1, 1, 1, 1] - [10, 2, 2] - ...

On parcourt la liste des solutions pour garder la solution la plus optimale (la plus courte) : [7, 7].

Exemples de problèmes que l'on peut résoudre par algorithme glouton

• Sac à dos
• Rendu de monnaie
• Gestion d'organisation de classe
• Voyageur de commerce.

Sac à dos

Un voleur entre dans une maison avec un sac à dos pouvant contenir un poids maximum. Il trouve plusieurs objets, chacun ayant une valeur et un poids. Quels objets doit-il prendre pour maximiser la valeur totale sans dépasser la capacité du sac ?

Exemple

Objets disponibles (valeur, poids) : [(60, 10), (100, 20), (120, 30)]

Capacité du sac : 50 kg

Stratégies gloutonnes possibles

1. Prendre l'objet de plus grande valeur en premier
2. Prendre l'objet le plus léger en premier
3. Prendre l'objet avec le meilleur ratio valeur/poids en premier (souvent la meilleure stratégie)

Algorithme (stratégie ratio valeur/poids)

def sac_a_dos_glouton(objets, capacite):
    """
    objets : liste de tuples (valeur, poids)
    capacite : poids maximum du sac
    """
    # Calculer le ratio valeur/poids et trier par ratio décroissant
    objets_avec_ratio = [(v, p, v/p) for v, p in objets]
    objets_tries = sorted(objets_avec_ratio, key=lambda x: x[2], reverse=True)

    poids_total = 0
    valeur_totale = 0
    sac = []

    for valeur, poids, ratio in objets_tries:
        if poids_total + poids <= capacite:
            sac.append((valeur, poids))
            poids_total += poids
            valeur_totale += valeur

    return sac, valeur_totale, poids_total

# Exemple d'utilisation
objets = [(60, 10), (100, 20), (120, 30)]
capacite = 50

sac, valeur, poids = sac_a_dos_glouton(objets, capacite)
print("Objets pris :", sac)
print("Valeur totale :", valeur, ", Poids total :", poids)
# Résultat : [(60, 10), (100, 20)] avec valeur=160 et poids=30
# Note : ce n'est pas optimal ! L'optimal serait [(100, 20), (120, 30)] = 220

Attention : L'algorithme glouton ne donne pas toujours la solution optimale pour le problème du sac à dos !

---

Voyageur de commerce

Un voyageur de commerce doit visiter plusieurs villes exactement une fois, puis revenir à son point de départ. Quel est le chemin le plus court ?

Exemple

Imaginons 4 villes : A, B, C, D avec les distances suivantes :

De/Vers	A	B	C	D
A	-	10	15	20
B	10	-	35	25
C	15	35	-	30
D	20	25	30	-

Stratégie gloutonne : "Plus proche voisin"

À chaque étape, on se déplace vers la ville non visitée la plus proche.

def voyageur_commerce_glouton(distances, depart=0):
    """
    distances : matrice des distances entre villes
    depart : indice de la ville de départ
    """
    n = len(distances)
    visitees = [False] * n
    chemin = [depart]
    visitees[depart] = True
    distance_totale = 0

    ville_actuelle = depart

    for _ in range(n - 1):
        # Trouver la ville non visitée la plus proche
        plus_proche = None
        dist_min = float('inf')

        for ville in range(n):
            if not visitees[ville] and distances[ville_actuelle][ville] < dist_min:
                dist_min = distances[ville_actuelle][ville]
                plus_proche = ville

        # Se déplacer vers cette ville
        chemin.append(plus_proche)
        visitees[plus_proche] = True
        distance_totale += dist_min
        ville_actuelle = plus_proche

    # Retour au point de départ
    distance_totale += distances[ville_actuelle][depart]
    chemin.append(depart)

    return chemin, distance_totale

# Exemple d'utilisation
distances = [
    [0, 10, 15, 20],   # Distances depuis A
    [10, 0, 35, 25],   # Distances depuis B
    [15, 35, 0, 30],   # Distances depuis C
    [20, 25, 30, 0]    # Distances depuis D
]

chemin, distance = voyageur_commerce_glouton(distances, depart=0)
villes = ['A', 'B', 'C', 'D']
chemin_noms = [villes[i] for i in chemin]
print("Chemin :", ' -> '.join(chemin_noms))
print("Distance totale :", distance)
# Résultat : A -> B -> D -> C -> A avec distance = 80

Note : Le problème du voyageur de commerce est un problème NP-difficile. Pour un grand nombre de villes, trouver la solution optimale prend un temps exponentiel. L'approche gloutonne donne une solution acceptable rapidement, mais rarement optimale.

---

Auteur : Florian Mathieu

Licence CC BY NC

Ce cours est mis à disposition selon les termes de la Licence Creative Commons Attribution - Pas d’Utilisation Commerciale - Partage dans les Mêmes Conditions 4.0 International