I. Retour sur trace

a) Principe

Beaucoup de problèmes consistent à trouver une solution parmi un très grand nombre de possibilités (placer des pièces, remplir une grille...). L'algorithme de retour sur trace (backtracking) construit une solution pas à pas :

• à chaque étape, on essaie chacun des choix possibles ;
• dès qu'un choix mène à une impasse (une contrainte n'est plus respectée), on l'abandonne et on revient en arrière pour essayer le choix suivant.

On explore ainsi un arbre des choix possibles, en profondeur, mais en coupant les branches qui ne peuvent pas mener à une solution : c'est beaucoup plus efficace que d'essayer toutes les combinaisons.

b) Un exemple : rendre la monnaie

On veut rendre une somme avec des pièces de 5 et de 4 (en nombre illimité, mais sans pièce de 1). Par exemple, pour :

• l'algorithme glouton prend d'abord une pièce de 5... et reste bloqué, avec 3 à rendre ;
• le retour sur trace, face à cette impasse, revient en arrière, et essaie la pièce de 4 à la place : .

Voici l'arbre des choix explorés : en rouge, les impasses ; en vert, la solution.

Depuis 3, aucune pièce ne convient : c'est une impasse, et on revient en 8 pour essayer la pièce suivante.

(* renvoie Some (liste de pièces de somme s), ou None s'il n'y en a pas ;
   les pièces sont essayées dans l'ordre de la liste *)
let rec rendre (pieces : int list) (s : int) : int list option =
  if s = 0 then Some []
  else
    let rec essayer (l : int list) : int list option = match l with
      | [] -> None                          (* plus aucun choix : impasse *)
      | p :: q ->
        if p > s then essayer q
        else match rendre pieces (s - p) with
          | Some solution -> Some (p :: solution)
          | None -> essayer q               (* retour en arrière : pièce suivante *)
    in
    essayer pieces;;

rendre [5; 4] 8;;
rendre [5; 4] 13;;
rendre [5; 4] 11;;

La fonction essayer parcourt les choix possibles (les pièces) ; si l'appel récursif échoue, on passe au choix suivant.

c) Lien avec min-max

L'algorithme min-max (vu en ITC) explore lui aussi un arbre de choix en profondeur : celui des coups possibles des deux joueurs. La différence est qu'on ne cherche pas une solution, mais le meilleur coup, en supposant que l'adversaire joue au mieux.

II. Files de priorité

a) Interface

Une file de priorité est une structure qui stocke des éléments associés à des priorités (ici, des entiers), avec les opérations :

• ajouter f x p : ajoute l'élément x avec la priorité p ;
• extraire_min f : retire et renvoie le couple (priorité, élément) de plus petite priorité ;
• est_vide f.

On l'implémente par un tas min stocké dans un tableau : la case 0 contient la racine, et les fils de la case i sont les cases 2i + 1 et 2i + 2. Le tableau a une taille fixée à la création : la file est bornée, et mutable.

• Pour ajouter un élément, on le place dans la première case libre, puis on le fait remonter en l'échangeant avec son père tant qu'il est plus petit.
• Pour extraire le minimum (la racine), on met le dernier élément à sa place, puis on le fait descendre en l'échangeant avec son plus petit fils tant qu'il est plus grand.

Essayez ces opérations ci-dessous :

b) Utilisation

L'implémentation en OCaml est l'objet du TP 4.1 (partie III). La cellule suivante la contient : exécutez-la pour pouvoir utiliser les fonctions creer, ajouter, extraire_min et est_vide dans la suite.

Par exemple :

let f = creer 10 "";;
List.iter (fun (x, p) -> ajouter f x p) [("réviser", 3); ("manger", 1); ("dormir", 2); ("jouer", 5)];;
while not (est_vide f) do
  let (p, x) = extraire_min f in
  Printf.printf "%s (priorité %d)\n" x p
done;;

III. Applications

a) Tri par tas

On ajoute tous les éléments dans une file de priorité, puis on les extrait dans l'ordre :

let tri_tas (l : int list) : int list =
  let f = creer (List.length l) 0 in
  List.iter (fun x -> ajouter f x x) l;
  List.init (List.length l) (fun _ -> snd (extraire_min f));;

tri_tas [5; 2; 9; 1; 5; 6; 3];;

La complexité est , comme le tri fusion.

b) Algorithme de Dijkstra

Dans l'algorithme de Dijkstra, on extrait à chaque étape le sommet non visité le plus proche. Avec une file de priorité, on ajoute un sommet à chaque fois qu'on améliore sa distance ; quand on extrait un sommet déjà visité, on l'ignore.

Un sommet peut être ajouté plusieurs fois dans la file (une fois par amélioration de sa distance) : seule la première extraction compte, avec la plus petite distance.

Par exemple, sur le graphe orienté suivant, depuis le sommet 0, on obtient les distances :

L'implémentation en OCaml (avec la file de priorité de la partie II) :

Chaque arête ajoute au plus un élément dans la file : avec sommets et arêtes, la complexité est .

c) Algorithme de Kruskal

Pour construire un arbre couvrant de poids minimal d'un graphe non orienté pondéré, l'algorithme de Kruskal considère les arêtes par poids croissant, et garde une arête si elle ne crée pas de cycle (voir le chapitre suivant, sur les graphes). Une file de priorité donne les arêtes dans l'ordre :

Pour savoir si deux sommets sont dans la même composante, chaque composante a un représentant : chaque sommet connaît un "parent" dans sa composante, et on remonte les parents jusqu'au représentant. Pour fusionner deux composantes, le représentant de l'une devient le parent du représentant de l'autre.

Par exemple, sur le graphe de 5 sommets dont les arêtes sont (poids 4), (1), (2), (5), (8), (3) et (9), on garde les arêtes , , et , pour un poids total de 11.

L'implémentation en OCaml :

Exercices

let k_plus_petits (l : int list) (k : int) : int list =
  let f = creer (List.length l) 0 in
  List.iter (fun x -> ajouter f x x) l;
  List.init (min k (List.length l)) (fun _ -> snd (extraire_min f));;