Pour tous les exercices de cette session, on vous fournit un fichier squelette Session7.java.

Les objectifs sont, dans l’ordre, que le code soit correct, que le code soit efficace et que le code soit lisible. Des tests unitaires sont fournis dans Session7Test.java.

1 Le principe du backtracking

1.1 Méthode

• Le backtracking est une méthode générale pour chercher une solution à un problème de décision ^[1] ou d’optimisation^[2].
• L’idée est d’explorer les solutions (le plus souvent récursivement) en les construisant à partir de solutions partielles que l’on complète.
• À chaque étape, on complète la solution partielle d’un cran, de toutes les façons possibles (récursivement).

1.2 Exemple des sous-ensemble de [0..n[

La méthode allSubsets renvoie la liste de tous les sous-ensembles de [0..n[. C’est moins efficace que la technique vue dans la session précédente, mais c’est une illustration simple de la technique du backtracking.

public static List<BitSet> allSubsets(int n) {
    var result = new ArrayList<BitSet>();
    subsetsBacktrack(0, n, new BitSet(n), result);
    return result;
}

private static void subsetsBacktrack(int start, int n, BitSet current, List<BitSet> result) {
    if (start == n) {
        result.add((BitSet) current.clone());
        return;
    }

    subsetsBacktrack(start + 1, n, current, result);
    current.set(start);
    subsetsBacktrack(start + 1, n, current, result);
    current.clear(start);
}

Version alternative (légèrement optimisée) :

private static void subsetsBacktrack(int start, int n, BitSet current, List<BitSet> result) {
    result.add((BitSet) current.clone());

    for (var i = start; i < n; i++) {
        current.set(i);
        subsetsBacktrack(i + 1, n, current, result);
        current.clear(i);
    }
}

1.3 Exemple du problème du sac à dos

On considère le problème suivant :

• un entier target, représentant le poids maximal autorisé ;
• un tableau weights de taille n, où weights[i] est le poids de l’objet i.

On veut donner (s’il existe) un sous-ensemble d’objets dont la somme des poids est exactement égale à target. Remarquez qu’il peut y avoir plusieurs solutions.

1.3.1 Idée de l’algorithme

On traite les objets un par un. À l’étape k, on a déjà décidé, pour chaque objet d’indice strictement inférieur à k, s’il appartient ou non au sac. Cela constitue une solution partielle. Pour passer à l’étape suivante, on explore récursivement deux possibilités :

• prendre l’objet k.
• ne pas prendre l’objet k ;

On obtient donc un arbre binaire de recherche. On peut optimiser cette recherche en s’arrêtant dans deux cas :

• si une solution a déjà été trouvée ;
• si la somme courante dépasse target.

1.3.2 Exemple de parcours

Si les poids sont { 1, 4, 8, 3, 5 }, et target = 10, un arbre de recherche possible explore les sous-ensembles (d’indices) :

{}               --> 0
{0}              --> 1
{0, 1}           --> 1+4=5
{0, 1, 2}        --> 1+4+8=13 
{0, 1, 3}        --> 1+4+3=8   
{0, 1, 3, 4}     --> 1+4+3+5=13       
{0, 1, 4}        --> 1+4+5=10    

L’ordre exact dépend de la manière dont on parcourt l’arbre.

1.3.3 Code

public static List<Integer> knapsack(int[] weights, int target) {
    return knapsackBacktrack(0, weights, target, new ArrayList<Integer>(), 0);
}

private static List<Integer> knapsackBacktrack(int start, int[] weights, int target, List<Integer> current,
        int currentWeight) {
    if (currentWeight == target) {
        return current;
    }
    if (currentWeight > target) {
        return List.of();
    }
    for (var i = start; i < weights.length; i++) {
        current.add(weights[i]);
        var knapsack = knapsackBacktrack(i + 1, weights, target, current, currentWeight + weights[i]);
        if (!knapsack.isEmpty()) {
            return knapsack;
        }
        current.removeLast();
    }
    return List.of();
}

1.4 Résumé

• On construit la solution de proche en proche en développant une solution partielle.
• On a souvent des critères pour arrêter une branche qu’on sait ne pas pouvoir fonctionner.
• C’est une technique importante pour résoudre des problèmes complexes