Problèmes de recherche
De nombreux problèmes algorithmiques peuvent être vus comme de problèmes de recherche d'une « solution » parmi
un espace de valeur potentiellement grand
- Placer N reines sur un échiquier
- Compléter une grille de sudoku
- Trouver tous les mots sur une grille de Boggle
- Résoudre le problème du « compte est bon »
- Résoudre un casse tête (comme Rush Hour™)
Trop de solutions ?
Pour tout ces problèmes, énumérer de façon exhaustive toutes les
configurations possibles, puis vérifier pour chaque configuration si
celle-ci est une solution est trop coûteux. Il y a deux
techniques complémentaires :
- Le retour arrière backtracking permet d'énumérer de
façon systématique toutes les solutions en éliminant
tôt les solutions impossibles
- La mémoization permet de se souvenir des résultats
déjà calculés (uniquement pour les problèmes qui s'y prêtent)
Retour arrière
Retour arrière
La technique de recherche avec retour arrière (backtracking)
consiste à partir d'un du problème initial et à s'en rapprocher
récursivement (en faisant diminuer une certaine mesure, ce qui va assurer
que l'on termine).
Pour se « rapprocher », on essaye toutes les façons d'avancer « en un coup » vers la solution
Pour chacune d'elle, si c'est un morceaux de solution valide, alors on s'appelle récursivement
sur la nouvelle configuration, sinon on passe à la suivante sans explorer plus ce début de solution.
Retour arrière (2)
La recherche avec retour arrière consiste à parcourir l'arbre de toutes
les configurations possibles en profondeur. Cependant, lorsque l'on détecte
que la configuration courante ne peut déjà pas mener à une solution, on
évite de parcourir le sous-arbre correspondant.
On illustre cette technique avec deux problèmes différents
Étude de cas 1 : problème des N reines
Étant donné un échiquier de taille N×N, comment placer dessus N reines
de façon à ce qu'aucune ne soit en prise.
Rappel: aux échecs, une reine peut capturer à n'importe quelle distance en ligne,
en colonne et en diagonale.
Méthode générale
On utilise l'approche récursive suivante. Pour placer N reines
- Si on a posé toutes les reines, alors l'échiquier est une solution
- Sinon, pour toute case libre c
- si c n'est pas une case capturée*:
- placer une reine sur c
- se rappeler récursivement avec (N-1) reine à placer
- sinon, considérer la case suivante**
La ligne ** effectue le retour arrière.
La ligne * est un endroit où on pourra mettre une optimisation spécifique
On écrit le code maintenant
On réfléchit ensemble à l'implémentation.
On finira en TP et on verra d'autres variations (compter les solutions, tirer aléatoirement une solution, …).
Comme toujours :
- On réfléchit aux types manipulé
- On essaye d'écrire la solution générale en pseudo-code (ou en OCaml avec des trous)
- Puis, on rafine jusqu'à obtention de la solution
Mémoization
Mémoization
Terme inventé en 1968 Donald Michie. En programmation, cela
consiste à optimiser des calculs en se souvenant de résultats
partiels.
Cette technique peut s'appliquer à toute fonction
- déterministe: les mêmes entrées donnent les même
sorties
- qui s'appelle plusieurs fois sur les mêmes entrées lors de
son calcul
Pas uniquement pour la résolution de problème, c'est une
technique générale
Fibonacci (encore)
let rec fib n =
if n <= 1 then n
else
fib (n-1) + fib (n-2)
- Temps de calcul exponentiel en n
- Répétitions :
fib 6 = fib 5 + fib 4
= (fib 4 + fib 3) + (fib 3 + fib 2)
= ((fib 3 + fib 2) + fib 3) + (fib 3 + fib 2)
Mémoization
La mémoization est une technique générale qui ne se soucie pas
de la fonction mémoizée. Pour une fonction f x , on
définit f_memo x munie d'un dictionnaire global:
- Si la paire x, r est dans le dictionnaire, renvoyer
r
- Sinon calculer r = f x
- Stocker (x, r) dans le dictionnaire
- Renvoyer r
Si on se débrouille bien, l'étape 1 coûte moins que
calculer f x. On va gagner si on rappelle
souvent f_memo sur le même argument (si tous les appels
sont uniques, on fait du travail pour rien et f_memo est
plus lente.
Par contre, on stocke des données: on gagne en temps de calcul mais
on perd en espace mémoire (souvent c'est un compromis acceptable).
Mémoization en OCaml
Une façon simple est d'utiliser le module Hashtbl
d'OCaml :
let f x =
... corps de f ...
devient
let f_memo =
let memo = Hashtbl.create 16 in (* table de hachage *)
let f x =
match Hashtbl.find_opt memo x with
Some r -> r
| None ->
let r = ... corps de f ... in
Hashtbl.add memo x r;
r
in f
f peut être récursive, ça ne change rien
Activité (2)
Exemples d'application:
- Fibonacci (juste pour avoir un exemple concret)
- Compter les chemins sur une grille
Compter les chemins d'une grille
- Entre le coin supérieur gauche et le coin inférieur
droit
- Un chemin ne peut aller que vers le bas où la droite
Le plus dur est de voir comment énumérer tous les chemins
