Algorithmes d'Optimisation

: Le Problème du Sac à Dos

[Link]
Le Problème du Sac à Dos 0/1

Votre mission : remplir le sac de manière à maximiser la valeur totale des objets
transportés, sans dépasser la capacité maximale du sac. La contrainte "0/1" signifie que
chaque objet doit être pris entièrement ou pas du tout – impossible de prendre une
fraction d'objet !

C'est un scénario simple mais qui cache une complexité algorithmique fascinante, que
l'on retrouve dans de nombreux domaines comme la gestion de projet, la logistique ou
l'allocation de ressources.

[Link]
Cas Pratique : Nos Objets et Notre Sac

Voici les objets que nous pourrions envisager d'emporter, avec leurs poids et leurs valeurs respectives, ainsi que la
capacité de notre sac.

Obj Poids Valeur

Objet 1 13 7

Objet 2 12 4

Objet 3 8 3

Objet 4 10 3

Capacité du Sac : 30 kg

[Link]
Algorithme 1 : L'Heuristique
Gloutonne (Ratio Valeur/Poids)
L'algorithme glouton est une approche intuitive qui fait le choix localement
optimal à chaque étape dans l'espoir de trouver une solution globale
optimale. Pour le sac à dos, cela signifie prioriser les objets offrant le
meilleur "rendement".

01 02

Calculer les Ratios Trier les Objets

Pour chaque objet, calculer son ratio Classer les objets par ordre
valeur/poids. décroissant de ce ratio.

03

Remplir le Sac
Parcourir la liste triée et ajouter les objets tant que la capacité du sac le
permet.
[Link]
Pseudo-code de l'Algorithme Glouton

Voici le pseudo-code qui détaille les étapes de l'approche gloutonne basée sur le ratio valeur/poids pour résoudre le problème du sac à dos.

Entrée : liste d’objets (poids[i], valeur[i]), capacité C

1. Pour chaque objet i :

ratio[i] = valeur[i] / poids[i]

2. Trier les objets par ratio décroissant

3. solution = ensemble vide

capacité_restante = C

4. Pour chaque objet trié :

si poids[i] ≤ capacité_restante :
ajouter i à solution
capacité_restante -= poids[i]

5. Retourner solution et sa valeur totale

[Link]
Utilité des paramètres

Pour une bonne compréhension de l'algorithme glouton, il est essentiel de maîtriser les paramètres clés utilisés dans son
pseudo-code et leur rôle fonctionnel.

poids[i] Permet de vérifier si l’objet peut entrer dans le sac en respectant la

capacité restante.

valeur[i] Indique l’intérêt ou le bénéfice associé à chaque objet, crucial pour

maximiser la valeur totale.

ratio = valeur/poids Critère de décision principal utilisé pour choisir les objets les plus
“rentables” à chaque étape.

C (capacité) Représente la limite de poids totale que le sac à dos peut supporter.

solution Ensemble final des objets sélectionnés par l’algorithme, formant la

solution gloutonne.
[Link]
Application de l'algorithme glouton

Appliquons l'heuristique gloutonne à notre cas pratique, en suivant les étapes clés pour remplir le sac à dos.

1. Calcul des Ratios Valeur/Poids 1

Nous calculons le ratio valeur/poids pour chaque objet, afin d'identifier les plus "rentables" :

• Objet 1: 7€ / 13kg ≈ 0.538

• Objet 2: 4€ / 12kg ≈ 0.333 2 2. Tri par Ordre Décroissant des Ratios
• Objet 3: 3€ / 8kg ≈ 0.375 Les objets sont ensuite classés du ratio le plus élevé au plus bas :

• Objet 4: 3€ / 10kg ≈ 0.300 • Objet 1 (0.538)

• Objet 3 (0.375)
3. Remplissage du Sac (Capacité: 30kg) 3 • Objet 2 (0.333)

1. Sélection de l'Objet 1: Avec un poids de 13kg, il est ajouté. Capacité restante: 30 - 13 = 17kg. • Objet 4 (0.300)

4 4. Poursuite du Remplissage
2. Sélection de l'Objet 3: Avec un poids de 8kg, il est ajouté. Capacité restante: 17 - 8 = 9kg.

5. Vérification des Objets Restants 5

3. Tentative Objet 2: Poids 12kg. La capacité restante de 9kg est insuffisante. Objet 2 non pris.

4. Tentative Objet 4: Poids 10kg. La capacité restante de 9kg est insuffisante. Objet 4 non pris.
6 6. Solution Gloutonne Finale
La solution gloutonne retient les Objets 1 et 3. La valeur totale est de 7€ + 3€ = 10€.

Bien que logique, cette solution n'est pas toujours optimale. Dans notre cas, la solution optimale
serait les objets 1 et 2 pour une valeur de 11€ (13kg+12kg=25kg, 7€+4€=11€).

[Link]
Complexité de l'Algorithme Glouton

Comprendre la complexité d'un algorithme est essentiel pour évaluer son efficacité, surtout lorsque l'on travaille avec de grands ensembles de
données. Voici une analyse de la complexité de l'approche gloutonne.

Calcul des Ratios 1

L'attribution d'un ratio valeur/poids pour chacun des n objets
nécessite un passage unique sur tous les éléments.

Complexité : O(n) 2 Tri des Objets

Le tri des objets selon leur ratio est l'étape la plus coûteuse en
temps pour la plupart des implémentations de tri efficaces.
Parcours des Objets 3
Complexité : O(n log n)
Une fois les objets triés, l'algorithme parcourt la liste une seule
fois pour remplir le sac à dos, jusqu'à ce que la capacité soit
atteinte. 4 Complexité Totale
Complexité : O(n) La complexité globale de l'algorithme glouton est déterminée
par l'étape de tri, qui est la plus dominante en termes de temps.

Complexité finale : O(n log n)

[Link]
Algorithme 2 : Recherche Aléatoire
(Random Search)
Contrairement à l'approche gloutonne qui suit une logique déterministe, la
recherche aléatoire explore l'espace des solutions en générant des combinaisons
au hasard. C'est une méta-heuristique souvent utilisée quand l'espace de
recherche est trop vaste pour une exploration exhaustive.

01 02

Initialisation Itérations
Définir la meilleure solution trouvée et Pour un nombre défini d'itérations (K),
sa valeur à zéro. générer une solution aléatoire (choix 0
ou 1 pour chaque objet).

03

Évaluation
Si la solution aléatoire est valide (poids ≤ C) et meilleure que la meilleure solution
actuelle, la mettre à jour.
[Link]
Pseudo-code de la Recherche Aléatoire

Voici le pseudo-code de l'algorithme de Recherche Aléatoire, détaillant comment des solutions candidates sont générées et évaluées
de manière non déterministe pour trouver une combinaison potentiellement meilleure.

Entrée : liste des objets, capacité C, nombre d’itérations K

1. meilleure_solution = vide
meilleure_valeur = 0

2. Pour t = 1 à K :
- Générer une solution aléatoire (choisir 0 ou 1 pour chaque objet)
- Calculer le poids total
- Si poids ≤ C alors
calculer la valeur totale
si valeur > meilleure_valeur :
mettre à jour meilleure_solution

3. Retourner meilleure_solution

[Link]
Random Search : Utilité des paramètres

Une compréhension claire des paramètres clés de la recherche aléatoire est fondamentale pour apprécier son fonctionnement et son
application dans la résolution du problème du sac à dos.

poids[i] Critère essentiel pour valider une solution. Il permet de vérifier si le sac n'est pas surchargé.

valeur[i] Sert à calculer la valeur totale d'une solution candidate, déterminant ainsi sa "qualité" par
rapport aux autres.

C (capacité) La contrainte physique du sac, limitant les combinaisons d'objets possibles et guidant
l'évaluation des solutions.

K (nombre d’itérations) Définit l'étendue de l'exploration aléatoire. Un K plus grand augmente la probabilité de
trouver une solution de meilleure qualité, mais aussi le temps de calcul.

solution aléatoire Chaque solution générée au hasard représente une tentative d'explorer une nouvelle
combinaison d'objets, exploitant la diversité pour potentiellement dénicher une meilleure
configuration.
[Link]
Comment appliquer Random Search au problème ?
Nous allons appliquer la Recherche Aléatoire à notre problème du sac à dos, en effectuant un nombre limité d'itérations pour découvrir des solutions potentielles.

1. Représentation Binaire 1
Chaque solution est un vecteur binaire (ex : 1 0 1 0), où chaque chiffre
correspond à un objet (1 = pris, 0 = non pris).

2 2. Génération des Itérations (K=10)

L'algorithme génère K solutions aléatoires, chacune étant une
combinaison différente d'objets. Pour chaque itération, nous vérifions la
3. Exemples d'Itérations Clés 3 validité (poids ≤ capacité) et calculons la valeur.

• Itération 1 (1 1 0 0): Poids = 25kg, Valeur = 11€.

• Itération 2 (0 0 1 1): Poids = 18kg, Valeur = 6€.

• Itération 3 (1 0 1 1): Poids = 31kg, Valeur = 13€. (poids > 30kg). 4 4. Identification de la Meilleure Solution
• Itération 4 (1 1 1 0): Poids = 33kg, Valeur = 14€. (poids > 30kg). Parmi les solutions valides générées, la meilleure trouvée est celle des
Objets 1 et 2 (représentée par 1 1 0 0).

Cela donne un poids total de 25kg et une valeur de 11€, ce qui est
supérieur à la solution gloutonne (10€).

[Link]
Complexité de la Recherche Aléatoire

La complexité de la recherche aléatoire dépend principalement du nombre d'objets à considérer et du nombre d'itérations effectuées.

Coût d'une Itération 1

Lors d'une seule itération, l'algorithme génère une solution
aléatoire et parcourt l'ensemble des n objets pour calculer son
poids et sa valeur. Cette opération est linéaire.
2 Complexité Totale sur K Itérations
Complexité : O(n)
Étant donné que l'algorithme répète ce processus K fois pour
générer et évaluer K solutions différentes, la complexité totale est

Scénario 1 : K est une constante 3 le produit du coût par itération et du nombre d'itérations.

Si le nombre d'itérations K est prédéfini et ne dépend pas de n (par Complexité : O(K * n)

exemple, K = 100 ou K = 1000), alors K est considéré comme
une constante dans l'analyse de complexité. L'algorithme est alors
linéaire par rapport au nombre d'objets. 4 Scénario 2 : K croît avec n
Si le nombre d'itérations K augmente avec le nombre d'objets n
Complexité : O(n)
(par exemple, K = n pour une exploration plus approfondie), la
complexité de l'algorithme devient quadratique.

Complexité : O(K * n) (peut devenir O(n²) si K=n)

[Link]
Complexité de la Recherche Aléatoire

La complexité de la recherche aléatoire dépend du nombre d'itérations effectuées.

Une Itération K Itérations

Vérifie tous les N objets : O(N) Coût total : O(K * N)

K Variable K Constant
Si K croit avec N, la complexité est Si K est une constante, la complexité
O(K * N). est O(N).

La recherche aléatoire est simple à implémenter, mais sa capacité à trouver la solution optimale est une question de chance et
du nombre d'itérations permises. [Link]
Glouton vs. Random Search

Comparons nos deux algorithmes pour mieux comprendre quand utiliser l'un ou l'autre.

Glouton Heuristique Très rapide, simple Pas toujours optimal O(N log N)

Random Search Méta-heuristique Peut trouver mieux que Aléatoire, sans garantie O(KN)
glouton d'optimum

Le choix entre ces méthodes dépend de vos priorités : avez-vous besoin d'une réponse rapide (Glouton) ou êtes-vous prêt à sacrifier du temps pour une
solution potentiellement meilleure (Random Search) ? Pour des solutions optimales garanties, d'autres algorithmes comme la programmation dynamique
seraient nécessaires.

CONCLUSION

Algorithme Valeur trouvée Optimal ?

Glouton 10€ Non

Random Search 11€ Oui (dans cet exemple)

Donc dans l'exemple : Random Search > Glouton

[Link]