From optimization to approximate approaches
Reading time10 minEn bref
Résumé de l’article
Cet article traite des problèmes d’optimisation et du problème de la monnaie, en montrant comment la programmation dynamique et les algorithmes gloutons peuvent être appliqués. Nous discutons également de la manière dont une heuristique gloutonne peut être utilisée pour approximer une solution à ce problème. L’article se termine par une comparaison de ces approches et de leurs compromis.
Principaux enseignements
-
Trouver des solutions exactes aux problèmes d’optimisation peut être très coûteux, même avec la programmation dynamique.
-
Les algorithmes gloutons peuvent fournir une solution proche de l’optimum en optimisant localement une fonction de manière itérative plutôt qu’une fois globalement.
-
Parfois, les algorithmes gloutons peuvent fournir des solutions exactes, mais pas toujours !
Contenu de l’article
1 — Problèmes d’optimisation
La programmation dynamique est souvent très utile lorsqu’on traite des problèmes d’optimisation (voir la note sur les problèmes). Le point est que les problèmes d’optimisation sont des variantes des problèmes de recherche avec de nombreuses solutions. Intuitivement, si le calcul naïf d’une solution engendre déjà beaucoup de recomputations, cela sera pire lorsqu’on cherche la meilleure solution.
Résoudre un problème d’optimisation en utilisant la programmation dynamique nécessite de suivre les mêmes étapes qu’auparavant, avec la contrainte que le problème d’optimisation doit présenter une propriété supplémentaire : il doit exhiber une sous-structure optimale.
Qu’est-ce que cela signifie ? Pour appliquer correctement une stratégie diviser-pour-régner, nous devons être capables de décomposer les problèmes en sous-problèmes et composer les solutions des sous-problèmes en une solution au problème. Comme nous voulons produire des solutions optimales, nous devons nous assurer qu’en composant les solutions optimales des sous-problèmes, nous obtenons la solution optimale du problème. De plus, puisqu’il y a un problème de recherche sous-jacent, il y a des choix. Un choix peut être vu comme un nouveau type de décomposition où le choix est divisé en ses différentes alternatives. Son coût est alors le minimum des coûts de ses alternatives.
Voyons comment cela fonctionne avec le problème de la monnaie.
2 — Le problème de la monnaie
Ce problème est une variante du problème de la monnaie que vous avez rencontré précédemment. Les paramètres d’entrée sont les mêmes :
- Une liste de valeurs entières donnant les dénominations des pièces et billets disponibles dans la monnaie, par exemple
[1, 2, 5, 10, 50]pour les euros. Nous supposons ici que ces valeurs $v_1$, …, $v_n$ sont ordonnées : $v_1 \lt ... \lt v_n$. - Un montant à changer.
Mais, alors que le problème de la monnaie cherche le nombre de façons de rendre la monnaie, le problème de la monnaie minimale cherche le nombre minimum de pièces nécessaires.
2.1 — Le problème de la monnaie
Voici un code possible pour le problème de la monnaie :
def count_coin_changes (amount: int, coins: list[int]) -> int:
"""
This function calculates the number of ways to make change for a given amount using a list of coins.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The number of ways to make change for the given amount.
"""
# Base cases
if amount == 0:
return 1
if amount < 0 or len(coins) == 0:
return 0
# Recursive calls
with_first_coin = count_coin_changes(amount - coins[0], coins)
without_it = count_coin_changes(amount, coins[1:])
return with_first_coin + without_it
print(count_coin_changes(4, [1, 2, 3])) # 4
print(count_coin_changes(10, [2, 5, 3, 6])) # 5
print(count_coin_changes(3, [2, 5])) # 0public class NbCountChanges {
public static int countCoinChanges(int amount, int[] coins) {
if (amount == 0) {
return 1;
}
if (amount < 0 || coins.length == 0) {
return 0;
}
int[] remainingCoins = new int[coins.length - 1];
System.arraycopy(coins, 1, remainingCoins, 0, coins.length - 1);
int withFirstCoin = countCoinChanges(amount - coins[0], coins);
int withoutFirstCoin = countCoinChanges(amount, remainingCoins);
return withFirstCoin + withoutFirstCoin;
}
public static void main(String[] args) {
System.out.println(countCoinChanges(4, new int[]{1, 2, 3})); // 4
System.out.println(countCoinChanges(10, new int[]{2, 5, 3, 6})); // 5
System.out.println(countCoinChanges(3, new int[]{2, 5})); // 0
}
}2.2 — Retour au problème de la monnaie minimale
Implémenter une définition récursive du problème de la monnaie minimale repose sur la même idée que dans le problème de la monnaie : on choisit une pièce et on l’utilise ou pas. Nous pourrions décider, comme dans le problème de la monnaie, d’utiliser la première pièce mais nous allons plutôt utiliser la dernière. Nous verrons pourquoi plus tard.
def change_making (amount, coins) -> int:
"""
This function calculates the minimum number of coins needed to make change for a given amount.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Inner function to initialize utilitary parameters
def __change_making (current_amount, i) -> int:
"""
This helper function calculates recursively the minimum number of coins needed to make change for a given amount.
In:
* current_amount: The amount for which change is to be made.
* i: The index of the coin to be used.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Base cases
if current_amount == 0:
return 0
if i == -1 or current_amount < 0:
return float('inf')
# There is the choice of using the ith coin or not
return min(__change_making(current_amount, i - 1), 1 + __change_making(current_amount - coins[i], i))
# Start with the coin of highest denomination
return __change_making(amount, len(coins) - 1)
# Test cases
euros = [1, 2, 5, 10, 50]
assert(change_making(49, euros) == 7) # [0, 2, 1, 4, 0]
assert(change_making(99, euros) == 8) # [0, 2, 1, 4, 1]
print(change_making(99, euros))
print(change_making(49, euros))
old_pounds = [1, 3, 6, 12, 24, 30]
# 49 = 1 + 2 * 24
assert(change_making(49, old_pounds) == 3) # [1, 0, 0, 0, 2, 0]
print(change_making(49, old_pounds))
foo = [2, 5]
assert(change_making(3, foo) == float('inf'))
print(change_making(3, foo))
print('All test cases passed!')public class ChangeMaking {
public static int changeMaking(int amount, int[] coins) {
return changeMakingAux(amount, coins, coins.length - 1);
}
private static int changeMakingAux(int currentAmount, int[] coins, int i) {
if (currentAmount == 0) {
return 0;
} else if (i == -1 || currentAmount < 0) {
return Integer.MAX_VALUE;
} else {
int exclude = changeMakingAux(currentAmount, coins, i - 1);
int include = changeMakingAux(currentAmount - coins[i], coins, i);
if (include != Integer.MAX_VALUE) {
include += 1;
}
return Math.min(exclude, include);
}
}
public static void main(String[] args) {
int[] euros = {1, 2, 5, 10, 50};
assert(changeMaking(49, euros) == 7);
assert(changeMaking(99, euros) == 8);
System.out.println(changeMaking(99, euros));
System.out.println(changeMaking(49, euros));
int[] oldPounds = {1, 3, 6, 12, 24, 30};
assert(changeMaking(49, oldPounds) == 3);
System.out.println(changeMaking(49, oldPounds));
int[] foo = {2, 5};
assert(changeMaking(3, foo) == Integer.MAX_VALUE);
System.out.println(changeMaking(3, foo));
System.out.println("All test cases passed!");
}
}Il est simple d’implémenter une version mémoïsée du problème, en utilisant soit un dictionnaire soit un tableau à deux dimensions. Cela est laissé en exercice au lecteur. Passons maintenant à la programmation dynamique.
2.3 — Une version en programmation dynamique du problème de la monnaie minimale
Implémenter la version en programmation dynamique de la monnaie minimale repose sur l’idée que le nombre minimum de pièces nécessaires pour rendre la monnaie d’un montant donné peut être calculé en considérant le nombre minimum de pièces nécessaires pour rendre la monnaie de montants plus petits. Le graphe du problème est une chaîne, où chaque sommet correspond à un montant donné et les arêtes correspondent au choix d’utiliser une pièce ou pas.
def change_making_dp (amount, coins) -> int:
"""
This function calculates, using dynamic programming, the minimum number of coins needed to make change for a given amount.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change.
Out:
* The minimum number of coins needed to make change for the given amount.
"""
# Initialize the table with infinity for all values except the first column
table = [float('inf')] * (amount + 1)
table[0] = 0
# For each amount greater than or equal to the coin value
for coin in coins:
for i in range(coin, amount + 1):
# check if using the current coin gives a better solution
# i.e., less coins for the amount - coin + 1
table[i] = min(table[i], table[i - coin] + 1)
return table[amount] if table[amount] != float('inf') else -1
# Test the function
print(change_making_dp(11, [1, 2, 5]))
print(change_making_dp(11, [1, 3, 4]))
print(change_making_dp(11, [1, 5, 6]))
print(change_making_dp(11, [1, 2, 5, 10]))public class ChangeMakingDP {
public static int changeMakingDP(int amount, int[] coins) {
// Initialize the table with infinity for all values except the first column
int[] table = new int[amount + 1];
for (int i = 1; i <= amount; i++) {
table[i] = Integer.MAX_VALUE;
}
table[0] = 0;
// for each coin
for (int coin : coins) {
// for each amount greater than or equal to the coin value
for (int i = coin; i <= amount; i++) {
// check if using the current coin gives a better solution (i.e. less coins for the amount - coin + 1)
if (table[i - coin] != Integer.MAX_VALUE) {
table[i] = Math.min(table[i], table[i - coin] + 1);
}
}
}
return table[amount] != Integer.MAX_VALUE ? table[amount] : -1;
}
public static void main(String[] args) {
System.out.println(changeMakingDP(11, new int[]{1, 2, 5}));
System.out.println(changeMakingDP(11, new int[]{1, 3, 4}));
System.out.println(changeMakingDP(11, new int[]{1, 5, 6}));
System.out.println(changeMakingDP(11, new int[]{1, 2, 5, 10}));
}
}3 — Algorithmes gloutons
Les algorithmes gloutons font des choix au lieu de considérer toutes les possibilités. Ils élaguent la recherche en prenant de bonnes décisions locales, calculant un optimum local avec le risque de manquer l’optimum global. Considérons le problème de la monnaie. Dans les versions précédentes, nous avons systématiquement considéré le choix d’utiliser ou non la pièce de la plus grande dénomination. Une stratégie gloutonne consiste à choisir la pièce de la plus grande dénomination tant que cela est possible. L’intuition est que, localement, cela semble plus efficace que de ne pas l’utiliser, en diminuant au maximum le montant à rendre avec une seule pièce. En conséquence, l’algorithme peut cependant ignorer de meilleures solutions qui auraient été obtenues en considérant de ne pas l’utiliser.
La partie déroutante est que la version gloutonne du problème de la monnaie minimale fournit des solutions optimales avec certains systèmes monétaires, elle est alors extrêmement efficace même par rapport à la programmation dynamique, mais ignore les solutions optimales avec d’autres (c’est-à-dire qu’elle est simplement incorrecte). Voir le programme ci-dessous.
Lorsqu’on vise l’efficacité, un risque général est de :
- Utiliser une stratégie de programmation dynamique alors qu’une stratégie gloutonne suffit.
- Utiliser une stratégie gloutonne alors qu’une stratégie de programmation dynamique est requise (la stratégie gloutonne manque des solutions optimales).
Malheureusement, alors qu’il est assez facile de montrer qu’un algorithme glouton ne fonctionne pas, en trouvant un contre-exemple, il n’est pas si facile de montrer qu’il n’y a pas de contre-exemple.
Cela nécessite d’être très prudent et idéalement de faire des preuves, qu’un problème présente une sous-structure optimale, qu’une stratégie gloutonne retourne des solutions optimales.
3.1 — Une version gloutonne du problème de la monnaie minimale
def greedy_change (amount, coins) -> list[int]:
"""
This function calculates the minimum number of coins needed to make change for a given amount using a greedy strategy.
In:
* amount: The amount for which change is to be made.
* coins: The list of coins available to make change, ordered in increasing order.
Out:
* A list of coin numbers i_1, i_2, ..., i_n such that i_1 * c_1 + i_2 * c_2 + ... = v.
"""
# For each coin from the highest to the lowest
solution = []
for coin in reversed(coins):
# Function divmod returns a tuple with the quotient and the remainder
count, amount = divmod(amount, coin)
solution.append(count)
#Reverse the solution to have the coins in the same order as the input
return solution[::-1]
# Test cases
euros = [1, 2, 5, 10, 50]
print(greedy_change(49, euros)) # [0, 2, 1, 4, 0]
print(greedy_change(99, euros)) # [0, 2, 1, 4, 1]
# The greedy algorithm does not always give the optimal solution
old_pounds = [1, 3, 6, 12, 24, 30]
# 49 = 1 + 6 + 12 + 30 = 1 + 2 * 24
print(greedy_change(49, old_pounds)) # [1, 0, 1, 1, 0, 1]import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class GreedyChange {
public static List<Integer> greedyChange(int amount, List<Integer> coins) {
List<Integer> solution = new ArrayList<>();
//for each coin from the highest to the lowest
for (int i = coins.size() - 1; i >= 0; i--) {
int coin = coins.get(i);
//divmod returns a tuple with the quotient and the remainder
int count = amount / coin;
amount %= coin;
solution.add(count);
}
//reverse the solution to have the coins in the same order as the input
Collections.reverse(solution);
return solution;
}
public static void main(String[] args) {
List<Integer> euros = List.of(1, 2, 5, 10, 50);
System.out.println(greedyChange(49, euros)); // [0, 2, 1, 4, 0]
System.out.println(greedyChange(99, euros)); // [0, 2, 1, 4, 1]
List<Integer> oldPounds = List.of(1, 3, 6, 12, 24, 30);
System.out.println(greedyChange(49, oldPounds)); // [1, 0, 1, 1, 0, 1]
}
}Pour aller plus loin
On dirait que cette section est vide !
Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !
Pour aller au-delà
On dirait que cette section est vide !
Y a-t-il quelque chose que vous auriez aimé voir ici ? Faites-le nous savoir sur le serveur Discord ! Peut-être pouvons-nous l’ajouter rapidement. Sinon, cela nous aidera à améliorer le cours pour l’année prochaine !