Session 7 - Backtracking

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.

Cette séance est adaptée d’un cours d’optimisation combinatoire de Cyril Nicaud pour les étudiants de BUT3.

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

2 Exercices

2.1 Génération des k-combinaisons de [0..n[

On appelle k-combinaison de [0..n[ tout sous-ensemble de cardinal k de l’ensemble {0,1,,n-1}. Par exemple, pour n = 4 et k = 3, les 3-combinaisons sont : {0,1,2}, {0,1,3}, {0,2,3} et {1,2,3}.

L’objectif est d’implémenter en Java deux méthodes permettant de produire toutes les k-combinaisons de [0..n[.

2.1.1 Version récursive simple

la méthode doit être récursive ;
elle doit construire le résultat de manière fonctionnelle, c’est-à-dire sans modifier une liste déjà construite ;
chaque combinaison sera représentée par un BitSet ;

Indication : On pourra utiliser la décomposition classique suivante.

si k = 0, il y a une seule combinaison : l’ensemble vide ;
si k > n, il n’y a aucune combinaison ;
les k-combinaisons de [0..n[ qui ne contiennent pas n − 1 sont exactement les k-combinaisons de [0..n − 1[ ;
les k-combinaisons de [0..n[ qui contiennent n − 1 s’obtiennent en ajoutant n − 1 à chaque (k−1)-combinaison de [0..n − 1[.

public static List<BitSet> slowCombinations(int k, int n)

2.1.2 Version par backtracking

la méthode doit explorer progressivement les choix possibles ;
une structure mutable temporaire peut être utilisée pour construire la combinaison courante ;
lorsqu’une combinaison complète est trouvée, une copie doit être ajoutée au résultat ;

public static List<BitSet> combinations(int k, int n)

2.2 Le problème de 3-coloriage

On considère des graphes non orientés sans boucle, encodés par leur matrice d’adjacence. Les sommets sont numérotés de 0 à n − 1 et on dispose d’une matrice graph (tableau à deux dimensions) telle que graph[i][j] est vrai s’il existe une arête entre les sommets i et j, et faux sinon. Comme le graphe est non orienté, on a graph[i][j] = graph[j][i] pour tous les sommets i et j.

Un 3-coloriage du graphe consiste à associer à chaque sommet une couleur parmi trois couleurs. Dans la suite, on représentera les couleurs par les entiers [1, 2, 3]. Un 3-coloriage est valide si deux sommets reliés par une arête n’ont jamais la même couleur. Ce n’est pas toujours possible, voir l’exemple ci-contre.

On représente un 3-coloriage par un tableau colors de taille n, où colors[i] désigne la couleur du sommet i. Un coloriage est partiel peut contenir des couleurs non affectées (valeur 0).

2.2.1 Test de validité d’une solution partielle

Écrire une fonction suivante qui retourne true si le 3-coloriage partiel colors est valide pour le graphe représenté par graph, et false sinon. Attention, les sommets qui n’ont pas de couleur n’influencent pas la validité du coloriage.

public static boolean isValid3Coloring(boolean[][] graph, int[] colors)

2.2.2 Version brute force

Écrire une fonction suivante qui retourne un coloriage valide du graphe, s’il en existe au moins un, en utilisant une méthode brute force.

public static Optional<int[]> threeColorsBruteForce(boolean[][] graph)

Énumérer les coloriages de taille n revient à énumérer les mots ternaires de longueur n… donc les décomposition en base 3 des entiers de 0 à 3ⁿ − 1

2.2.3 Version bactracking

Écrire une fonction suivante qui retourne un coloriage valide du graphe, s’il en existe au moins un, en utilisant une méthode par backtracking.

public static Optional<int[]> threeColors(boolean[][] graph)

Caractéristiques des fichiers de test :

La taille maximale d’un graphe est 20.

Exemples :

Les coloriages possibles sont :

[1, 3, 2, 1]
[1, 2, 3, 1]
[2, 3, 1, 2]
[2, 1, 3, 2]
[3, 2, 1, 3]
[3, 1, 2, 3]
[1, 2, 3, 1]

2.3 Le problème des n-reines

Le problème des n-reines est un problème classique d’optimisation. Il s’agit de placer n jetons (les reines) sur les cases d’une grille n × n de façon à ce qu’il n’y ait pas deux reines sur la même ligne, ni sur la même colonne, ni sur la même diagonale.

Comme il ne peut y avoir qu’une reine par ligne, on encode une solution au problème comme une liste d’entier queens de taille n où queens.get(i) est le numéro de la colonne où se trouve la reine de la ligne i. Pour simplifier le code, on numérote les lignes et les colonnes de 0 à n − 1. Une solution est nécessairement une permutations, c’est à dire que la liste contient exactement une fois chaque entier de [0..n−1]. Une solution partielle de taille k est une liste qui contient des numéros de colonnes (entre 0 et n − 1) pour les k premières lignes. Il peut manquer des numéros de colonne, mais il n’y a pas de doublons dans la liste.

2.3.1 Test de validité d’une solution partielle

Écrire une fonction isValidQueensPermutation suivante qui vérifie si la solution partielle queens est valide pour le problème à n reines.

private static boolean isValidQueensPermutation(int n, List<Integer> queens)

2.3.2 Version brute force

On veut écrire une fonction qui retourne une liste de toutes les solutions valides pour le problème à n reines, en utilisant une méthode brute force. Pour cela, il faut pouvoir énumérer les solution candidates. Vous pouvez implémenter une des deux méthodes suivantes : soit énumérer tous les k-uplets de [0..n−1] (méthodes facile), soit directement les permutations de [0..n−1] (par backtracking).

public static List<List<Integer>> allTuples(int k, int n)
public static List<List<Integer>> allPermutations(int n)

Énumérer les k-uplets de [0..n−1] revient à énumérer les mots n-aires de longueur k… donc les décomposition en base n des entiers de 0 à n^k − 1

Écrire la fonction suivante qui retourne une liste de toutes les solutions valides pour le problème à n reines, en utilisant une méthode brute force.

public static List<List<Integer>> nQueensBruteForce(int n)

2.3.3 Version bactracking

Écrire la fonction suivante qui retourne une liste de toutes les solutions valides pour le problème à n reines, en utilisant une méthode par backtracking.

public static List<List<Integer>> nQueens(int n)

Caractéristiques des fichiers de test :

Le nombre maximal de reines est 15.

Exemples :

Les solutions valides pour n = 4 sont les suivantes

[1, 3, 0, 2]
[2, 0, 3, 1]

Les solutions valides pour n = 5 sont les suivantes

[0, 2, 4, 1, 3]
[0, 3, 1, 4, 2]
[1, 3, 0, 2, 4]
[1, 4, 2, 0, 3]
[2, 0, 3, 1, 4]
[2, 4, 1, 3, 0]
[3, 0, 2, 4, 1]
[3, 1, 4, 2, 0]
[4, 1, 3, 0, 2]
[4, 2, 0, 3, 1]