\( \def\N{{\mathbb{N}}} \def\R{{\mathbb{R}}} \def\D{{\mathbb{D}}} \def\C{{\mathbb{C}}} \def\Z{{\mathbb{Z}}} \def\Q{{\mathbb{Q}}} \def\K{{\mathbb{K}}} \def\KX{{\mathbb{K}}[X]} \def\U{{\mathbb{U}}} \def\B{{\mathcal{B}}} \newcommand\ensfonctions[2]{\mathcal{F}(#1,#2)} \newcommand\ensfonctionszero[3]{\mathcal{F}_{#3,0}(#1,#2)} \newcommand\continues[2]{\mathcal{C}(#1,#2)} \newcommand\lineaires[2]{\mathcal{L}(#1,#2)} \newcommand\nlineaires[3]{\mathcal{L}_{#1}(#2,#3)} \newcommand\ensendo[1]{\mathcal{L}(#1)} \newcommand\derivables[2]{\mathcal{D}(#1,#2)} \newcommand\segment[2]{[#1,#2]} \newcommand\intouvert[2]{]#1,#2[} \newcommand\intouvertgauche[2]{]#1,#2]} \newcommand\intouvertdroite[2]{[#1,#2[} \newcommand\classeck[3]{\mathcal{C}^{#1}(#2,#3)} \newcommand\range[2]{[| #1,#2 |]} \newcommand\mod[0]{\mathop{mod}} \newcommand\land[0]{\mathop{land}} \newcommand\voisinages[2]{\mathcal{V}_{#1}(#2)} \newcommand\matrices[3]{\mathcal{M}_{#1,#2}(#3)} \newcommand\matricescarres[2]{\mathcal{M}_{#1}(#2)} \newcommand\gln[2]{\mbox{GL}_{#1}(#2)} \newcommand\Vect[1]{\mbox{Vect}(#1)} \newcommand\Support[1]{\mbox{Supp}(#1)} \newcommand\rang[1]{\mbox{rg}(#1)} \newcommand\trace[1]{\mbox{tr}(#1)} \newcommand\gl[1]{\mbox{GL}(#1)} \newcommand\dom[0]{\mbox{dom}} \newcommand\codim[0]{\mbox{codim}} \newcommand\tr{\mbox{tr}} \newcommand\uniondisjointe{\sqcup} \def\Rbar{\overline\R} \def\lt{<} \def\rR{\mathcal{R}} \newcommand\parties[1]{\mathcal{P}(#1)} \newcommand\entiere[1]{\left\lfloor #1 \right\rfloor} \newcommand\congru[3]{#1 = #2\ [#3]} \newcommand\enscomp[2]{\left\{\left.\ #1\ \right|\ #2\ \right\}} \newcommand\classe[1]{\overline{#1}} \newcommand\classemod[2]{\overline{#1}^{[#2]}} \newcommand\quotient[2]{#1 / #2} \newcommand\ZnZ[1]{\quotient{\Z}{#1 \Z}} \newcommand\card[1]{\text{Card}\ #1} \newcommand\Det{\mbox{Det}} \newcommand\indic{\mathbbm{1}} \newcommand\groupeengendre[1]{\langle #1 \rangle} \renewcommand\Im{\mathfrak{I}} \newcommand\id{\mbox{id}} \newcommand\Bary[1]{\mbox{Bary}\{#1\}} \newcommand\Ker{\mbox{Ker}~} \newcommand\Ima{\mbox{Im}~} \newcommand\Perm[1]{\mathfrak{S}_#1} \newcommand\comb[2]{\binom{#1}{#2}} \newcommand\tend[2]{\xrightarrow[#1 \rightarrow #2]{}} \newcommand\limite[2]{\lim_{#1 \rightarrow #2}} \newcommand\sh{\mbox{sh}} \newcommand\ch{\mbox{ch}} \renewcommand\tanh{\mbox{th}} \newcommand\Arcsin{\mbox{Arcsin}~} \newcommand\Arccos{\mbox{Arccos}~} \newcommand\Arctan{\mbox{Arctan}~} \newcommand\Argsh{\mbox{Argsh}} \newcommand\Argch{\mbox{Argch}} \newcommand\Argth{\mbox{Argth}} \newcommand\argu{\mbox{arg}} \newcommand\dron[2]{\frac{\partial #1}{\partial #2}} \newcommand\conj[1]{\overline{#1}} \newcommand\ei[1]{e^{i #1}} \newcommand\eii[2]{e^{#1 i #2}} \newcommand\crochet[1]{\left[ #1 \right]} \newcommand\application[5]{\begin{array}{rcccc} #1 & : & #2 & \mapsto & #3 \\ & & #4 & \mapsto & #5 \end{array}} \newcommand{\diff}{\mathop{}\mathopen{}\mathrm{d}} \newcommand{\cc}{{\cal C}} \)

Algorithmique exacte

Source image : https://www.flickr.com/photos/x6e38/3440634940/

Remarque
Dans ce chapitre, on étudie des problèmes pour lesquels on va exprimer des algorithmes permettant d’obtenir des solutions exactes. C’est à contraster avec le chapitre sur l’algorithmique approchée.

Une grande partie des stratégies de résolution est basée sur la résolution de sous-problèmes. On verra ainsi trois types de stratégies résumées dans le schéma suivant :

1 Recherche par force brute

1.1 Principe

Considérons un problème du type trouver un \(x \in V\) vérifiant une propriété \(P(x)\). Par exemple, \(V\) est l’ensemble des chaînes de caractère et \(P\) vérifie si une chaîne est un mot de passe qu’on cherche. Dans certains problèmes, un tel \(x\) n’est pas unique et on cherche à tous les énumérer.

Une recherche par force brute, ou recherche exhaustive, consiste à parcourir l’ensemble \(V\) jusqu’à obtenir une solution. Pour la recherche du mot de passe, on pourrait commencer par énumérer les chaînes de longueur 1, puis de longueur 2, et ainsi de suite.

Le plus souvent, l’ensemble \(V\) est fini (pour les mots de passe, cela peut consister à limiter la longueur maximale du mot de passe). Ainsi, une recherche par force brute effectue \(O(|V|)\) itérations.

Considérons le problème PlusProchePaire qui, étant donné un ensemble de \(n\) points (\(n \ge 2\)), détermine la paire constituée des deux points les plus proches.

Une implémentation naïve de la recherche par force brute consiste à énumérer les \(\frac{n(n-1)}{2}\) paires et donc à effectuer \(O(n^2)\) itérations.

let plus_proche_paire points =
    let n = Array.length points in
    let min_paire = ref (distance points.(0) points.(1), (0, 1)) in
    for i = 0 to n - 1 do
        for j = i+1 to n - 1 do
            let d = distance points.(i) points.(j) in
            if d < fst !min_paire
            then min_paire := (d, (i, j))
        done
    done;
    snd !min_paire

1.2 Raffinement : droite de balayage

Il est parfois possible d’accélérer la recherche par force brute en ordonnant le parcours des candidats pour pouvoir éviter de tester certains d’entres eux.

En géométrie algorithmique, une approche classique consiste à ordonner les objets selon leur abscisse et à parcourir les objets par abscisse croissante. On parle alors de droite de balayage (en anglais, sweep line) car cela revient à balayer le plan par une droite verticale en ne traitant que les objets avant cette ligne.

Reprenons le problème précédent, on considère que les points sont triés par abscisse croissante : \((x_0,y_0), \dots, (x_{n-1}, y_{n-1})\). On va parcourir les points dans cet ordre en maintenant un ensemble de points à gauche du point courant, appelés points actifs, et en ne calculant que les intersections avec les points actifs.

Si on a parcouru les \(N\) premiers points et qu’on a obtenu que la plus petite distance était \(d\), lorsqu’on considère le point \((x_N,y_N)\), il est inutile de tester les points qui sont forcément à distance \(> d\) de celui-ci. C’est-à-dire qu’on peut éliminer les points qui ne sont pas dans le rectangle \([x_N-d,x_N]\times [y_N-d,y_N+d]\) du test. Les points dont l’abscisse est \(< x_N -d\) peuvent être éliminés définitivement vu que l’on raisonne par abscisse croissante, par contre, les points d’ordonnées invalides doivent être conservés pour les points ultérieurs.

Ce rectangle est représenté sur le schéma suivant ainsi qu’une ligne imaginaire qui correspond à l’abscisse du point courant et qu’on peut imaginer parcourant le plan de gauche à droite pour traiter les points au fur et à mesure.

Afin de déterminer la complexité de cet algorithme, il est nécessaire de connaitre le nombre maximal de points dans le rectangle. Comme ces points ont été pris en compte précédemment, ils sont forcément à distance au moins \(d\) les uns des autres. Il s’agit donc de déterminer le nombre maximum de points qu’on peut placer dans ce rectangle à distance au moins \(d\). On remarque tout d’abord qu’on peut placer six points ainsi :

Si jamais on avait au moins sept points, on peut voir qu’il y a forcément un des six sous-rectangles suivants qui contiendrait au moins deux points :

Or, ces sous-rectangles sont de longueur \(\frac{1}{2}d\) et de hauteur \(\frac{2}{3}d\), donc la distance maximale entre deux de leurs points correspond à la longueur des diagonales : \(\sqrt{\frac{1}{4} + \frac{4}{9}}d = \frac{5}{6}d < d\).

Comme un de ces six points est le point courant, il y a toujours au plus 5 points dans l’ensemble des points actifs.

Voici le principe de l’algorithme que l’on va implémenter :

  • On trie le tableau points par ordre croissant. Complexité : \(O(n \log n)\)

  • On initialise la plus petite distance d courante à la distance entre les deux premiers points

  • On crée un ensemble actifs, ordonné par les ordonnées, de points contenant initialement les deux premiers points

  • Pour chaque point \((x,y)\) en partant du deuxième :

    • On supprime les points \((x',y')\) tels que \(x' < x - d\) de actifs. Complexité : sur l’ensemble des itérations on ne pourra jamais supprimer deux fois un point, donc on effectue au maximum \(n\) suppressions chacune en \(O(\log n)\) donc \(O(n \log n)\).
    • On parcourt les points de actifs dont les ordonnées sont comprises entre \(y-d\) et \(y+d\). Complexité : pour récupérer le premier point de l’ensemble, il faut \(O(\log n)\) en pire cas (tous les points actifs) et ensuite on effectue au plus 5 itérations comme on vient de le prouver.

L’animation suivante présente le déroulement de cet algorihtme. La bande active est indiquée en gris et le rectangle autour du point courant en gris foncé :

On remarque ainsi que la complexité en temps et en pire cas de cet algorithme est de \(O(n \log n)\). Ici, le fait d’avoir la structure actifs ordonnée par les ordonnées est crucial pour garantir la complexité. Pour la réalisation d’une structure d’ensemble ordonnée ayant ces complexité, voir le chapitre FIXME.

Ici, on utilise le module Set d’OCaml pour réaliser la structure d’ensemble, pour cela on commence par créer le module PointSet pour les ensembles de points :

module Point = struct
    type t = float * float
    let compare (x1,y1) (x2,y2) = Stdlib.compare y1 y2
end

module PointSet = Set.Make(Point)

Puis on définit une fonction permettant de parcourir les points entre deux ordonnées :

let set_iter_entre f set bas haut =
    try
        let e = PointSet.find_first (fun p -> snd p >= bas) set in
        let seq = PointSet.to_seq_from e set in
        let rec aux seq =
            match seq () with
            | Seq.Nil -> ()
            | Seq.Cons (p, seq_suite) -> 
                    if snd p <= haut
                    then begin
                        f p;
                        aux seq_suite
                    end
        in aux seq
    with Not_found -> ()

On implémente alors assez directement l’algorithme décrit précédemment :

let plus_proche_paire_balayage points =
    let compare (x1,y1) (x2,y2) =
        if x1 = x2
        then if y1 < y2 then -1 else 1
        else if x1 < x2 then -1 else 1
    in
    Array.sort compare points;
    let n = Array.length points in
    let d = ref (distance points.(0) points.(1)) in
    let couple = ref (points.(0), points.(1)) in
    let actifs = ref (PointSet.empty 
            |> PointSet.add points.(0) |> PointSet.add points.(1)) in

    let gauche = ref 0 in

    for i = 2 to n-1 do
        let xi, yi = points.(i) in
        
        while fst points.(!gauche) < xi -. !d do
            actifs := PointSet.remove points.(!gauche) !actifs;
            incr gauche
        done;

        set_iter_entre (fun pj -> 
            let dip = distance points.(i) pj in
            if dip < !d
            then begin
                couple := (points.(i), pj);
                d := dip
            end) !actifs (yi -. !d) (yi +. !d);

        actifs := PointSet.add points.(i) !actifs
    done;
    !d

1.2.1 Problème : test d’intersection pour un ensemble de segments

Considérons le problème suivant IntersectionEnsemble : étant donné \(n\) segments dans le plan, il s’agit de déterminer si au moins deux des segments s’intersectent.

Remarque
On peut considérer ici que l’on dispose d’une fonction

intersecte : (float * float) * (float * float) 
    -> (float * float) * (float * float) -> bool 

qui teste l’intersection entre deux segments.

Cependant, il est possible d’écrire une telle fonction avec un peu de géométrie élémentaire.

Si on considère que les deux segments sont \([A_1B_1]\) et \([A_2B_2]\), avec \(A_1 \neq B_1\) et \(A_2 \neq B_2\), alors chaque point du segment \([A_1B_1]\) est de la forme \(A_1 + t \overrightarrow{A_1B_1}\)\(t \in [0,1]\). De même les points du segments \([A_2B_2]\) sont de la forme \(A_2 + u \overrightarrow{A_2B_2}\)\(u \in [0,1]\).

S’il y a une intersection, c’est qu’il existe \((t,u) \in [0,1]^2\) tel que

\[ A_1 + t \overrightarrow{A_1B_1} = A_2 + u \overrightarrow{A_2B_2} \iff \overrightarrow{A_2 A_1} + t \overrightarrow{A_1B_1} = u \overrightarrow{A_2 B_2} \]

L’idée est alors d’utiliser une opération appelée produit vectoriel sur les vecteurs. Comme ici, tout est plan, le produit vectoriel est uniquement déterminé par sa troisième coordonnée, celle qui sort du plan, et on peut se contenter de calculer celle-ci. On note ainsi \((x,y) \times (x',y') = x y' - y x'\) cette coordonnée. On a donc \(u \times u = 0\).

On peut alors composer l’égalité par \(\times \overrightarrow{A_2B_2}\) :

\[ \overrightarrow{A_2 A_1} \times \overrightarrow{A_2 B_2} + t \left( \overrightarrow{A_1 B_1} \times \overrightarrow{A_2 B_2} \right) = 0 \]

Notons \(\Delta = \overrightarrow{A_1 B_1} \times \overrightarrow{A_2 B_2}\), si \(\Delta \neq 0\), alors

\[ t = - \frac{\overrightarrow{A_2 A_1} \times \overrightarrow{A_2 B_2}}{\Delta} = \frac{\overrightarrow{A_1 A_2} \times \overrightarrow{A_2 B_2}}{\Delta} \]

On procède de même avec \(\times \overrightarrow{A_1 B_1}\) pour obtenir une expression de \(u\) : \(\overrightarrow{A_2 A_1} \times \overrightarrow{A_1 B_1} = u \left ( \overrightarrow{A_2 B_2} \times \overrightarrow{A_1 B_1} \right) = - u \Delta\) et donc

\[ u = - \frac{\overrightarrow{A_2 A_1} \times \overrightarrow{A_1 B_1}}{\Delta} = \frac{\overrightarrow{A_1 A_2} \times \overrightarrow{A_1 B_1}}{\Delta} \]

Si \(\Delta \neq 0\), on peut donc alors exprimer \(u\) et \(t\) et vérifier qu’ils sont dans \([0,1]\).

Si \(\Delta = 0\) c’est que les deux segments sont de directions parallèles ou confondues.

  • Si \(\overrightarrow{A_1 A_2} \times \overrightarrow{A_1 B_1} \neq 0\) alors \(\overrightarrow{A_1 A_2}\) et \(\overrightarrow{A_1 B_1}\) sont non colinéaires donc les deux segments sont sur des droites parallèles distinctes et ne peuvent s’intersecter.
  • Sinon, les segments reposent sur une même droite et il s’agit de vérifier leurs positions sur la droite. Pour cela, on exprime \(A_2 = A_1 + t_A \overrightarrow{A_1B_1}\) de même pour \(B_2 = A_1 + t_B \overrightarrow{A_1 B_1}\). Plus précisement, on calcule \(\overrightarrow{A_1 A_2} \cdot \overrightarrow{A_1 B_1} = t_A ||\overrightarrow{A_1 B_1}||^2\) à l’aide du produit scalaire et on a \(t_A = \frac{\overrightarrow{A_1 A_2} \cdot \overrightarrow{A_1 B_1}}{||\overrightarrow{A_1 B_1}||^2}\). De même, \(t_B = \frac{\overrightarrow{A_1 B_2} \cdot \overrightarrow{A_1 B_1}}{||\overrightarrow{A_1 B_1}||^2}\). On doit alors vérifier si l’intervalle \([t_A,t_B]\) (ou \([t_B,t_A]\) selon leur position) intersecte \([0,1]\).

Voici une fonction OCaml qui correspond à ce raisonnement

let intersecte (a1,b1) (a2,b2) =
    let vec (x1,y1) (x2,y2) = (x2-.x1,y2-.y1) in
    let cross (x1,y1) (x2,y2) = x1 *. y2 -. y1 *. x2 in
    let dot (x1,y1) (x2,y2) = x1 *. x2 +. y1 *. y2 in
    let proche0 x = let eps = 1e-20 in 
        if x < 0. then -.x < eps else x < eps in
    let a1b1 = vec a1 b1 in let a2b2 = vec a2 b2 in
    let a1a2 = vec a1 a2 in let a1b2 = vec a1 b2 in

    let delta = cross a1b1 a2b2 in

    if proche0 delta
    then
         if proche0 (cross a1a2 a1b1)
         then let na1b1 = dot a1b1 a1b1 in (* colinéaires *)
              let tA = (dot a1a2 a1b1) /. na1b1 in
              let tB = (dot a1b2 a1b1) /. na1b1 in
              if tA < tB
              then not (tB < 0. || tA > 1.)
              else not (tA < 0. || tB > 1.)
         else false (* parallèles *)
    else let t = (cross a1a2 a2b2) /. delta in (* se croisent *)
         let u = (cross a1a2 a1b1) /. delta in
         t >= 0. && t <= 1. && u >= 0. && u <= 1.

Note
réécrire cela avec le déterminant de deux vecteurs du plan qui est au programme de mathématiques de seconde.

La recherche par force brute va alors énumérer l’ensemble des paires de segments distincts et tester deux à deux les intersections. On peut ainsi écrire le programme suivant qui est assez simple et effectuera effectivement \(O(|v|^2)\) itérations dans le pire cas, i.e. lorsqu’il n’y a pas d’intersections.

exception Trouve

let intersection_ensemble (v: ((float * float) * (float * float)) array) : bool =
    let n = Array.length v in
    try
        for i = 0 to n - 1 do
            for j = i+1 to n-1 do
                if intersecte v.(i) v.(j)
                then raise Trouve
            done
        done;
        false
    with Trouve -> true

TODO approche par droite de balayage : algorithme de Shamos et Hoey (1976)

1.3 Recherche par retour sur trace (backtracking)

Dans des problèmes admettant des solutions partielles, on peut construire une solution par essai de toutes les possibilités en complétant tant qu’on a bien une solution partielle. La recherche par retour sur trace repose sur ce constat pour énumérer l’ensemble des solutions en utilisant la récursivité (d’où la notion de retour sur trace) pour les essais.

L’exemble classique de ce problème est celui des huit reines : étant donné un échiquier, peut-on placer huit reines de sorte qu’aucune reine ne puisse prendre une autre reine ? Plus précisément : sur un plateau de 8x8 cases, peut-on placer huit pions tels que deux pions quelconques ne soient jamais sur la même ligne ou la même diagonale ?

Exemple de solution :

Ce problème admet effectivement des solutions partielles en ne considérant que \(k\) reines à placer. Pour énumérer les solutions, on peut même se contenter de solutions partielles où les \(k\) reines sont placées sur les \(k\) premières rangées.

Voici ainsi un algorithme pour énumérer les solutions :

  • Supposons que \(k\) reines aient été placées et qu’on dispose d’une solution partielle.

    • Si \(k = 8\) alors toutes les reines sont placées et la solution est complète, on la comptabilise
    • Sinon, on continue la recherche pour chaque position de la \(k+1\) reine sur la \(k+1\) rangée qui préserve le fait d’être une solution partielle.

Ici, quand on dit qu’on continue la recherche, ce qu’on signifie c’est qu’on effectue un appel récursif.

Pour programmer cette méthode, on va définir une fonction récursive de signature :

val resout_reines : (int * int) list -> (int * int) list list

Un appel à resout_reines part va ainsi renvoyer la liste des solutions complètes construites à partir de la solution partielle part. Les solutions sont représentées par des listes de couples de coordonnées sur l’échiquier, donc dans \([|0;7|]^2\)

Voici une implémentation où on explore les solutions à l’aide d’une boucle impérative dans l’appel récursif. La fonction valide permet de tester si le placement d’une reine est possible avant d’effectuer un appel.

let rec valide (x1,y1) l =
    match l with
    | [] -> true
    | (x2,y2)::q ->
        x1 <> x2 && abs (x2-x1) <> abs(y2-y1) && valide (x1,y1) q

let rec resout_reines part =
    let k = List.length part in
    if k = 8 
    then [ part ]
    else begin
        let resultats = ref [] in
        for x = 0 to 7 do
            let essai = (x,k) :: part in
            if valide (x,k) part
            then begin
                resultats := (resout_reines essai) @ !resultats;
            end
        done;
        !resultats
    end

et, ici, une autre implémentation purement récursive à l’aide d’une fonction récursive.

let rec resout_reines part =
    let k = List.length part in
    if k = 8 
    then [ part ]
    else 
        let rec aux x acc =
            if x < 0
            then acc
            else let essai = (x,k) :: part in
                 let nacc = if valide (x,k) part
                           then (resout_reines essai) @ acc
                           else acc in
                    aux (x-1) nacc
        in
        aux 7 [] 

Une partie de l’arbre de recherche est présenté sur l’image suivante :

Arbre de recherche pour les huit reines

L’arbre complet comporte 2057 noeuds dont 92 feuilles correspondant aux solutions du problème. A titre de comparaison, l’arbre exhaustif correspondant à faire tous les choix de placement à raison d’une reine par ligne compterait \(8^8 = 16777216\) noeuds. On voit bien que le backtracking est plus économe en exploration.

1.3.1 Problème : résolution de Sudoku

La recherche par retour sur trace se prête très bien à la résolution de problèmes comme le Sudoku. On va ici tout simplement tenter de remplir chaque case du haut vers le bas tant qu’on satisfait les contraintes du Sudoku. Le programme sera ainsi très proche de la résolution des huit reines.

Commençons par rappeler le principe du Sudoku :

  • On part d’une grille de 81 cases réparties en une grille de 3x3 sous-grilles de 3x3 cases et comportant des chiffres de 1 à 9 dans certaines cases.

  • L’objectif est de remplir chaque case avec un chiffre de 1 à 9 de sorte que chaque ligne, chaque colonne et chaque sous-grille 3x3 comporte une et une seule fois chaque chiffre.

  • Un sudoku admet une unique solution.

Pour représenter une grille de Sudoku en OCaml on utilise un (int option) array array, la valeur None signifiant que la case est vide et la valeur Some x qu’elle est remplie avec la valeur \(x\).

type grille = (int option) array array

On fait le choix de représenté la grille par un tableau de lignes, ce qui signiie que pour accèder à la case de coordonnée \((x,y)\) dans g il faut écrire g.(y).(x).

Le problème donnée précédemment est alors représenté par la valeur suivante :

let probleme = [|
    [| Some 1; None; None;    None; None; None;   None; None; Some 6 |];
    [| None; None; Some 6;    None; Some 2; None;   Some 7; None; None |];
    [| Some 7; Some 8; Some 9;    Some 4; Some 5; None;   Some 1; None; Some 3 |];

    [| None; None; None;    Some 8; None; Some 7;   None; None; Some 4 |];
    [| None; None; None;    None; Some 3; None;   None; None; None |];
    [| None; Some 9; None;    None; None; Some 4;   Some 2; None; Some 1 |];

    [| Some 3; Some 1; Some 2;    Some 9; Some 7; None;   None; Some 4; None |];
    [| None; Some 4; None;    None; Some 1; Some 2;   None; Some 7; Some 8 |];
    [| Some 9; None; Some 8;    None; None; None;   None; None; None |];
    |]

Afin de définir la fonction de résolution, on définit une première fonction suivant de signature :

val suivant : grille -> (int * int) -> (int * int) option

telle que l’appel à suivant g (x,y) renvoie Some (xi,yi) quand \((x_i,y_i)\) sont les coordonnées de la prochaine case libre, dans l’ordre gauche à droite puis haut vers bas, après \((x,y)\) ou None quand il n’existe pas de telle case libre. Cela signifie alors que la grille est entièrement remplie.

let rec suivant g (x,y) =
    if y > 8
    then None
    else if g.(y).(x) = None
    then Some (x,y)
    else if x < 8 then suivant g (x+1, y)
    else suivant g (0, y+1)

On définit également une fonction valide de signature

val valide : grille -> int -> int -> bool

telle que l’appel à valide g x y renvoie true si et seulement si la valeur placée en coordonnée \((x,y)\) n’invalide pas la grille. Ne pas prendre cette valeur en paramètre permettant d’écrire un peu plus simplement cette fonction. La fonction est assez directe, étant donné \((x,y)\) on va parcourir sa ligne, sa colonne et sa sous-grille pour vérifier qu’un nombre n’a pas été placé deux fois à l’aide d’un tableau de drapeaux :

let valide g x y =
    let v = ref true in
    let vus_colonne = Array.make 9 false in
    for y0 = 0 to 8 do
        match g.(y0).(x) with
        | None -> ()
        | Some k -> 
                if vus_colonne.(k-1)
                then v := false;
                vus_colonne.(k-1) <- true
    done;
    let vus_ligne = Array.make 9 false in
    for x0 = 0 to 8 do
        match g.(y).(x0) with
        | None -> ()
        | Some k -> 
                if vus_ligne.(k-1)
                then v := false;
                vus_ligne.(k-1) <- true
    done;
    let vus_grille = Array.make 9 false in
    let xb = (x / 3) * 3 in
    let yb = (y / 3) * 3 in
    for xd = 0 to 2 do
        for yd = 0 to 2 do
            match g.(yb+yd).(xb+xd) with
            | None -> ()
            | Some k -> 
                    if vus_grille.(k-1)
                    then v := false;
                    vus_grille.(k-1) <- true
        done
    done;
    !v

On peut alors définir la fonction resout qui va résoudre le Sudoku en effectuant tous les remplissages tant qu’on a une grille valide. Dès qu’une solution est trouvé, on s’arrête. Pour cela, on utilise le mécanisme des exceptions pour permettre une sortie prématurée. On a fait le choix de travailler en place dans la grille, ainsi à la fin de l’exécution de la fonction, la grille correspond à la solution.

exception Solution

let resout g =
    let rec aux xi yi = match suivant g (xi, yi) with
        | None -> raise Solution
        | Some (x,y) ->
            for i = 1 to 9 do
                g.(y).(x) <- Some i;
                if valide g x y
                then begin
                    aux x y
                end
            done;
            g.(y).(x) <- None
    in 
    try 
        aux 0 0
    with Solution -> ()

La résolution du Sudoku donnée précédemment par ce programme est présenté dans la vidéo suivante :

2 Algorithmes gloutons

2.1 Principe

On considère ici un problème d’énumération comme dans la section précédente muni d’une fonction d’objectifs qui attribue une valeur numérique aux solutions et aux solutions partielles.

Soit \(f : P \rightarrow \R\) une telle fonction, où \(S \cup P\) est l’ensemble des solutions du problème d’énumération et \(P\) l’ensemble des solutions partielles, on se pose maintenant le problème de l’optimalité vis-à-vis de \(f\) : déterminer \(x \in S\) tel que \(f(x) = \max_{y \in S} f(y)\) on note souvent \(x = \text{argmax}_{y\in S} f(y)\). On parle alors de problème d’optimisation combinatoire.

Remarque

  • En considérant \(g : y \mapsto -f(y)\), on transforme un problème de maximisation en un problème de minimisation.
  • Il y a une ambiguïté sur \(\text{argmax}_{y \in S} f(y)\) quand plusieurs éléments de \(S\) réalisent ce maximum. Dans la plupart des algorithmes gloutons qu’on va considérer, on commence par donner un ordre sur \(S\) et on considère le plus petit \(y\) pour cet ordre réalisant le maximum. L’ordre choisi est alors crucial dans la preuve de correction. C’est aussi une des raisons pour lesquelles les algorithmes gloutons sont souvent de complexité temporelle \(O(n \log_2 n)\).

Une première stratégie très élémentaire consiste alors à énumérer \(S\), de manière exhaustive ou avec une stratégie plus fine comme le retour sur trace, puis à déterminer un élément maximal de manière directe.

Cela revient donc à déterminer l’arbre des solutions puis à trouver une feuille maximisant l’objectif :

Un algorithme glouton va suivre une approche beaucoup plus efficace : à chaque étape de construction de la solution, on choisit la branche qui maximise la fonction d’objectif. C’est-à-dire que si en partant d’une solution partielle \(x \in P\) il est possible de l’étendre en d’autres solutions partielles \(p_x = \{ y_1, ..., y_n \}\), on va choisir \(y = \text{argmax}_{t \in p_x} f(t)\) la solution qui maximise localement \(f\).

Sur l’arbre précédent, cela reviendrait à n’emprunter qu’une seule branche :

Cela a l’air très efficace mais il y a un problème majeur : il n’y a aucune garantie qu’on aboutisse ainsi à une solution, encore moins à une solution optimale. En effet, on aurait très bien pu faire les choix suivants :

et ne pas aboutir à une solution.

Considérons par exemple le problème du rendu de monnaie : étant donné, une liste de valeurs faciales de pièces \(P = (v_1,\dots,v_p) \in (\N^*)^p\) avec \(1 = v_1 < \dots < v_p\) et une somme \(n \in \N^*\), on cherche la manière d’exprimer cette somme avec le plus petit nombre de pièces possible.

Plus précisément, l’ensemble des solutions \(S = \{ (k_1,\dots,k_p) \in N^p ~|~ k_1 v_1 + \dots + k_p v_p = n \}\) et la fonction d’objectif est \(f : (k_1,\dots,k_p) \mapsto k_1 + \dots + k_p\). Les solutions partielles ici sont les réalisations de valeur \(< n\). On cherche alors \(x = argmin_{y \in S} f(y)\).

Comme \(1 = v_1\), \(S \neq \emptyset\) car \((n,0,\dots,0) \in S\) et ainsi \(f(x) \le n\).

L’algorithme glouton va utiliser la plus grande pièce possible à chaque étape puis on applique l’algorithme glouton sur la somme restante sauf si elle est nulle, ce qui constitue la condition d’arrêt.

Exemple 1

  • \(P = (1, 2, 5, 10)\)
  • \(n = 14\)
  • On utilise la plus grande pièce possible \(10 \le 14\) puis on exprime \(4 = 14 - 10\)
  • Ici, la plus grande pièce est \(2\) et on continue avec \(2 = 4 - 2\)
  • La plus grande pièce est encore \(2\) et on s’arrête car \(0 = 2 - 2\).
  • En conclusion, on a obtenu \(x = (0,2,0,1)\).
  • Une exploration exhuastive permet de s’assurer qu’on a effectivement obtenu une décomposition minimale. En effet, ici l’ensemble des décompositions est : { (14,0,0,0), (12,1,0,0), (8,3,0,0), (6,4,0,0), (4,5,0,0), (2,6,0,0), (0,7,0,0), (9,0,1,0), (7,1,1,0), (5,2,1,0), (3,3,1,0), (1,4,1,0), (4,0,2,0), (2,1,2,0), (0,2,2,0), (4,0,0,1), (2,1,0,1), (0,2,0,1) }.

Exemple 2

  • \(P = (1, 2, 7, 10)\)
  • \(n = 14\)
  • L’algorithme glouton va ici procéder comme dans l’exemple 1 et on va obtenir \(x = (0,2,0,1)\).
  • Mais on remarque que ce n’est pas un minimum car \(x' = (0,0,2,0)\) convient avec \(f(x') = 2 < 3 = f(x)\).

Conclusion l’algorithme glouton n’a effectivement pas de raisons d’être optimal.

On peut se poser la question des algorithmes pour lesquels l’algorithme glouton aboutit nécessairement à une solution optimale.

Note
TODO - Ajouter un paragraphe simple sur les matroïdes qui puisse se décliner sous la forme d’un problème.

2.2 Algorithme d’Huffman - Compression

On va étudier ici un principe de compression parfaite (sans perte d’information à la décompression) de données appelé l’algorithme de Huffman et qui repose sur ce principe simple : coder sur moins de bits les caractères les plus fréquents.

Par exemple si on considère le mot abaabc, en le codant avec un nombre de bits fixes, par exemple 2 avec le code a=00,b=01,c=10, on aurait besoin de 12 bits pour représenter le mot. Mais si on choisit le code suivant : a=0,b=10,c=11, il suffit de 9 bits. On a donc gagné 3 bits soit un facteur de compression de 75%.

On remarque que pour pouvoir décompreser, il n’aurait pas été possible de faire commencer le code de b ou c par un 0, sinon on aurait eu une ambiguité avec la lecture d’un a. On parle alors de code préfixe :

Définition
Soit \(X \subset \{0,1\}^*\), on dit que \(X\) est un code préfixe lorsque pour tous \(x, y \in X\), \(x\) n’est pas un préfixe de \(y\) et \(y\) n’est pas un préfixe de \(x\).

On se pose alors la question du code préfixe optimal pour un texte donné.

Plus précisément, étant donné un alphabet fini \(\Sigma\) et une application \(f : \Sigma \rightarrow [0,1]\) associant à chaque lettre sa fréquence dans le texte considéré, c’est-à-dire \(f(x) = \frac{\text{occurences}(x)}{\text{longueur}}\) et donc \(\sum_{x \in \Sigma} f(x) = 1\), on cherche un code préfixe \(X\) et une application \(c : \Sigma \rightarrow X\) telle que \(\sum_{x \in \Sigma} f(x) |c(x)|\) soit minimale.

En effet, si le texte considéré est de longueur \(n\), il y a exactement \(f(x) n\) occurences de \(x\) dans le texte et \(f(x) n |c(x)|\) bits après codage. La longueur du texte codé est donc \(n \sum_{x \in \Sigma} f(x) |c(x)|\).

L’application de codage \(c\) peut être représenté par un arbre binaire où les arêtes gauches correspondent à 0, les arêtes droites à 1 et les feuilles aux éléments de \(\Sigma\) dont les étiquettes des chemins y menant depuis la racine de l’arbre correspondent à leur image par \(c\).

Par exemple, pour le code \(a=0,b=10,c=11\) on aurait l’arbre :

Avec un tel arbre, il est très simple de décoder le texte codé car il suffit de suivre un chemin dans l’arbre jusqu’à tomber sur une feuille, produire la lettre correspondante, puis repartir de la racine de l’arbre. La longueur du code associé à une lettre est alors égale à la profondeur de la feuille correspondante. L’optimalité du codage préfixe est ainsi équivalente à la minimalité de l’arbre vis-à-vis de la fonction d’objectif \(\varphi(t) = \sum_{x \in \Sigma} f(x) p(t,x)\)\(p(t,x)\) est la profondeur de la feuille d’étiquette \(x\) dans l’arbre \(t\) ou \(0\) si \(x\) n’est pas une des étiquettes, cet extension permettant d’étendre la fonction d’objectif aux solutions partielles.

L’algorithme d’Huffman va construire un arbre correspondant à un codage optimal à l’aide d’une file de priorité d’arbres. On étend pour cela l’application \(f\) à de tels arbres en définissant que si \(t\) est un arbre de feuilles \(x_1,\dots,x_n\) alors \(f(t) = f(x_1) + \dots + f(x_n)\).

  • Au départ, on place dans la file des arbres réduits à une feuille pour chaque élément \(x \in \Sigma\) et dont la priorité est \(f(x)\).

  • Tant que la file contient au moins deux éléments

    • on retire les deux plus petits éléments \(x\) et \(y\) de la file de priorité \(f(x)\) et \(f(y)\)
    • on ajoute un arbre \(z = Noeud(x,y)\) de priorité \(f(z) = f(x) + f(y)\).
  • On renvoie l’unique élément restant dans la file.

L’implémentation de cet algorithme est alors assez directe avec une file de priorité.

Note
FIXME: utiliser un module file de priorité fait dans un chapitre précédent plutôt

module Heap = Core_kernel.Heap

let compare_pair f a b = Stdlib.compare (f a) (f b)

type arbre = Feuille of char | Noeud of arbre * arbre

let huffman freq =
    let arbres = Heap.create ~cmp:(compare_pair fst) () in
    let compte = ref (Array.length freq) in
    for i = 0 to Array.length freq - 1 do
        let c, f = freq.(i) in
        Heap.add arbres (f, Feuille c)
    done;
    while !compte > 1 do
        let fx, x = Heap.pop_exn arbres in
        let fy, y = Heap.pop_exn arbres in
        Heap.add arbres (fx+.fy, Noeud(x,y));
        compte := !compte - 1
    done;
    snd (Heap.pop_exn arbres)

Remarque
FIXME: Rajouter la compression/décompression

L’algorithme de Huffman est un algorithme glouton car si on considère pour solution partielle la fôret présente dans la file et pour objectif la fonction \(\varphi\) étendue aux fôrets en sommant la valeur de \(\varphi\) sur chaque arbre, alors fusionner dans la fôret \(F\) deux arbres \(x\) et \(y\) en la transformant en une fôret \(F'\) va avoir l’impact suivant sur la fonction d’objectif :

\[ \varphi(F') = \varphi(F) + f(x) + f(y) \]

car, en effet, on va rajouter 1 à la profondeur de chaque feuille et donc on passe pour la contribution de \(x\) de \(\varphi(x) = \sum_{c \in \Sigma} f(c) p(x,c)\) à \(\sum_{c \in \Sigma} f(c) (p(x,c)+1) = \varphi(x) + \sum_{c \in \Sigma} f(c) = \varphi(x) + f(x)\).

On remarque ainsi que la fusion qui minimise localement \(\varphi\) est celle qui fusionne les deux arbres de plus petite valeur pour \(f\).

Pour montrer que l’algorithme glouton produit ici un codage minimal, on va utiliser une technique classique qui consiste à montrer qu’étant donné une solution optimale, on peut toujours la transformer sans augmenter sa valeur pour obtenir, de proche en proche, la solution renvoyée par le glouton.

Théorème

Supposons que les lettres les moins fréquentes soient \(a\) et \(b\), il existe un arbre optimal dont les deux feuilles étiquettées par \(a\) et \(b\) descendent du même noeud et sont de profondeur maximale.

Preuve

Considérons un arbre optimal \(t\) et soient \(c\) l’étiquette d’une feuille de profondeur maximale. On remarque qu’elle a forcément une feuille sœur car sinon, on pourrait omettre le noeud et l’arbre obtenu serait de plus petite valeur par \(\varphi\).

FIXME: dessin

Soit \(d\) l’étiquette de cette feuille sœur. Sans perte de généralités, on suppose que \(f(c) \le f(d)\) et \(f(a) \le f(b)\). Comme \(a\) a la plus petite fréquence, on a \(f(a) \le f(c)\) et comme \(b\) est la deuxième, on a \(f(b) \le f(d)\). De plus, \(p(t,a) \ge p(t,c)\) et \(p(t,b) \ge p(t,d)\).

Si on échange les étiquettes \(a\) et \(c\), seule les termes associées à ces lettres changent dans l’évaluation de \(\varphi\). Si on note \(t'\) le nouvel arbre obtenu après cet échange, on a \[ \varphi(t') = \varphi(t) - f(a) p(t,a) - f(c) p(t,c) + f(a) p(t,c) + f(c) p(t,a) \] Or, \(f(c) \ge f(a)\) et \(p(t,a) \ge p(t,c)\) donc \[\varphi(t') = \varphi(t) + (f(c) - f(a))(p(t,a)-p(t,c)) \le \varphi(t)\] L’échange préserve le caractère optimal. En fait, ici, on a nécessairement une égalité pour ne pas aboutir à une contradiction, donc soit les feuilles étaient à même profondeur, soit les lettres avaient la même fréquence.

Comme on a les mêmes relations entre \(b\) et \(d\), on peut effectuer le même argument et échanger les étiquettes en préservant le caractère optimal.

Le théorème suivant permet de raisonner par récurrence en diminuant le nombre de lettres.

Théorème

Soit \(t\) un arbre ayant \(x\) et \(y\) comme feuilles soeurs et \(t'\) l’arbre obtenu en remplaçant le noeud liant \(x\) et \(y\) par une feuille étiquettée par \(z\)\(z\) est une nouvelle lettre telle que \(f(z) = f(x) + f(y)\).

On a alors \(\varphi(t) = \varphi(t') + f(z)\).

Preuve

Seule les termes portant sur \(x, y\) et \(z\) sont influencés par le changement et on a : \[ \begin{array}{rl} \varphi(t) & = \varphi(t') + f(x) p(t,x) + f(y) p(t,y) - f(z) p(t',z) \\ & = \varphi(t') + f(z) (p(t',z) + 1) - f(z) p(t',z) \\ & = \varphi(t') + f(z) \end{array} \]

Théorème

L’algorithme de Huffman renvoie un arbre optimal.

Preuve

Par récurrence sur \(|\Sigma|\).

Initialisation : si \(\Sigma\) ne contient qu’une lettre, il n’y a qu’un arbre qui est nécessairement optimal.

Hérédité : si la propriété est vraie pour un alphabet de \(n-1 \ge 1\) lettres, alors soit \(\Sigma\) contenant \(n\) lettres et \(x\) et \(y\) les deux lettres les moins fréquentes.

On pose \(\Sigma'\) obtenue en remplaçant \(x\) et \(y\) par une nouvelle lettre \(z\) et on suppose que \(f(z) = f(x) + f(y)\). L’hypothèse de récurrence assure qu’on obtient un arbre optimal \(t'\) en appliquant l’algorithme d’Huffman sur \(\Sigma'\). Comme la première étape d’Huffman va fusionner les feuilles \(x\) et \(y\), on sait que l’arbre \(t\) obtenu en partant de \(\Sigma\) se déduit de \(t'\) en remplaçant \(z\) par \(Noeud(x,y)\). Le théorème précédent assure alors que \(\varphi(t) = \varphi(t') + f(z)\).

Soit \(t_o\) un arbre optimal pour \(\Sigma\) dans lequel \(x\) et \(y\) sont soeurs, possible en vertu du premier théorème, et soit \(t_o'\) l’arbre obtenue en remplaçant dans \(t_o\) le noeud liant \(x\) et \(y\) par une feuille étiquettée par \(z\). On a ici encore \(\varphi(t_o) = \varphi(t_o') + f(z) \ge \varphi(t') + f(z) \ge \varphi(t)\) car \(t'\) est optimal.

Ainsi, on a bien l’égalité \(\varphi(t_o) = \varphi(t)\) et \(t\) est optimal.

2.3 Preuve d’optimalité

Dans le paragraphe précédent, on retrouve un schéma de preuve classique pour les preuves d’optimalité des algorithmes gloutons :

  • Montrer qu’à partir d’une solution optimale, il est possible de déterminer une solution optimale ayant fait le même choix que l’algorithme glouton. Pour Huffman c’était le fait d’avoir un arbre optimal ayant les deux lettres les moins fréquentes comme sœurs à profondeur maximale.
  • Montrer qu’une solution optimale se comportant comme le résultat de l’algorithme glouton à une étape ne peut être meilleure que le résultat de l’algorithme glouton.

2.4 Sélection d’activités

2.4.1 Description

Étant donné un ensemble d’activités données par leur temps de début et leur temps de fin (on considère les temps comme des entiers pour simplifier), on se pose la question du nombre maximal d’activité que l’on puisse sélectionner sans que deux activités soient en conflits. Cela correspond par exemple à l’organisation du planning d’un employé.

On dit que deux activités \((d_1,f_1)\) et \((d_2,f_2)\) sont en conflits quand \([d_1,f_1[ \cap [d_2,f_2[ \neq \emptyset\).

Ici, \(t_1\) et \(t_2\) sont en conflits avec \(t_3\). Mais \(t_1\) et \(t_2\) ne sont pas en conflit. On considère que deux activités peuvent se succéder directement : \(f_1 = d_2\).

On considère donc en entrée de ce problème une suite finie \(( (d_1,f_1), \dots, (d_n,f_n) )\) et on cherche un sous-ensemble \(I \subset \range{1}{n}\) de plus grand cardinal tel que pour tous \(i, j \in I\), si \(i \neq j\) alors \((d_i,f_i)\) et \((d_j,f_j)\) ne sont pas en conflits. On dit que \(I\) est un ensemble indépendant.

2.4.2 Algorithme glouton et implémentation

Pour résoudre ce problème, on considère l’algorithme glouton associé à la fonction d’objectif cardinal et en triant les activités ordre croissant de temps de fin.

Cet algorithme est implémenté dans le programme suivant :

#include <stdio.h>
#include <stdlib.h>

typedef struct {
    unsigned int id;
    unsigned int debut;
    unsigned int fin;
    unsigned char selectionnee;
} activite;

int compare_activites(const void *t1, const void *t2)
{
    return ((activite *)t1)->fin - ((activite *)t2)->fin;
}

void selectionne(activite *activites, size_t nb_activites)
{
    size_t derniere_activite = 0;
    /* on commmence par trier en O(n log2 n) les activites
     * selon le temps de fin */
    qsort(activites, nb_activites,
        sizeof(activite), compare_activites);
    activites[0].selectionnee = 1;
    for (size_t i = 1; i < nb_activites; i++)
    {
        if (activites[i].debut >= activites[derniere_activite].fin)
        {
            activites[i].selectionnee = 1;
            derniere_activite = i;
        }
    }
}

int main()
{
    activite activites[] = {
        { 0, 1, 3, 0 }, { 1, 3, 4, 0 }, { 2, 2, 5, 0 },
        { 3, 5, 9, 0 }, { 4, 11, 12, 0 }, { 5, 8, 10, 0 },
        { 6, 0, 7, 0 }
    };

    size_t nb_activites = sizeof(activites) / sizeof(activite);

    selectionne(activites, nb_activites);

    for (size_t i = 0; i < nb_activites; i++)
    {
        printf("Activité %d (%d,%d) : %d\n",
                activites[i].id, activites[i].debut,
                activites[i].fin, activites[i].selectionnee);
    }

    return 0;
}

Ce programme produit alors la sortie :

Activité 0 (1,3) : 1
Activité 1 (3,4) : 1
Activité 2 (2,5) : 0
Activité 6 (0,7) : 0
Activité 3 (5,9) : 1
Activité 5 (8,10) : 0
Activité 4 (11,12) : 1

Remarque
Comme l’algorithme commence par effectuer un tri, on a rajouté dans la structure activite un champ permettant d’identifier une activité autrement que par son indice.

2.4.3 Preuve d’optimalité

On va prouver que l’algorithme glouton renvoie un ensemble indépendant optimal. Le fait que l’ensemble soit indépendant étant direct, on se concentre sur la preuve d’optimalité en présentant un schéma de preuve qui correspond à celui identifié dans le paragraphe précédent.

Théorème

Si \(a_1,\dots,a_n\) sont des activités énumérées dans l’ordre croissant de leur temps de fin, alors il existe un ensemble indépendant optimal contenant \(a_1\).

Remarque
Cela signifie qu’il fait le même choix que l’algorithme glouton à la première étape.

Preuve

Soit \(I\) un ensemble indépendant optimal ne contenant pas \(a_1 = (d_1,f_1)\) (sinon c’est direct). Si \(a_k = (d_k,f_k)\) est l’activité de plus petit indice dans \(I\), alors \(f_k \ge f_1\) donc pour tout \(a_i = (d_i,f_i)\) dans \(I' = I \backslash \{ a_k \}\) on a \(d_i \ge f_k \ge f_1\) et ainsi \(a_1\) et \(a_i\) ne sont pas en conflit. Ainsi \(I' \cup \{ a_1\}\) est un ensemble indépendant contenant \(a_1\) de même cardinal que \(I\) donc optimal.

Théorème

Soit \(A = \{ a_1,\dots,a_n \}\) des activités ordonnées par ordre croissant de temps de fin et \(I\) un ensemble indépendant optimal contenant \(a_1 = (d_1,f_1)\) (ce qui est possible selon le théorème précédent).

\(I' = I \backslash \{a_1\}\) est optimal pour \(A' = \enscomp{ (d,f) \in A}{d \ge f_1}\).

Preuve

Si, par l’absurde, \(I'\) est pas optimal pour \(A'\) alors \(J \subset A'\) est un ensemble indépendant de cardinal strictement plus grand que celui de \(I'\). Or, \(A' \cup \{ a_1 \}\) est indépendant pour l’ensemble des activités et est de cardinal strictement plus grand que \(I\). Contradiction.

Théorème

L’algorithme glouton renvoie un ensemble indépendant optimal.

Preuve

Par récurrence forte sur le nombre d’activités.

  • Initialisation : Pour une activité \(a_1\), le glouton renvoie \(\{ a_1 \}\) qui est directement optimal.

  • Hérédité : Si la propriété est vérifiée pour \(k \le n\) activités, soit \(A = \{ a_1, \dots, a_{n}\}\) des activités ordonnées par temps de fin. Soit \(I\) un ensemble indépendant optimal contenant \(a_1\) et \(I' = I \cap \{ a_1 \}\). Le théorème précédent assure que \(I'\) est optimal sur \(A' = \enscomp{ (d,f) \in }{d \ge f_1}\).

    Par hypothèse de récurrence, l’algorithme glouton sur \(A'\) produit un ensemble indépendant optimal \(G'\), donc tel que \(|G'| = |I'|\). Par construction l’algorithme glouton sur \(A\) renvoie \(G = G' \cup \{ a_1\}\) de même cardinal que \(I\), donc optimal.

2.5 Points les plus proches

2.6 Sous-ensemble de somme donnée

2.7 Recherche dichotomique

2.8 Couverture par des segments égaux

3 Programmation dynamique

3.1 Principe

3.2 Somme de sous-ensembles

3.3 Ordonnancement de tâches

3.4 Plus longue sous-suite commune

3.5 Distance d’édition