Retour sur trace et séparation-évaluation

Exercice 1. Toutes les solutions de la somme de sous-ensemble ★

Application du cours · 15 min

un tableau a contient n entiers strictement positifs. Écrire en OCaml une fonction renvoyant tous les ensembles d'indices de somme s.

let solutions a s =
  let n = Array.length a in
  let r = Array.make (n + 1) 0 in
  for i = n - 1 downto 0 do r.(i) <- r.(i + 1) + a.(i) done;
  let rec explorer i t choix acc =
    if t > s || t + r.(i) < s then acc
    else if i = n then List.rev choix :: acc
    else
      explorer (i + 1) (t + a.(i)) (i :: choix)
        (explorer (i + 1) t choix acc)
  in
  explorer 0 0 [] []

Exercice 2. Taille de l'arbre des permutations ★

Application du cours · 10 min

on énumère les permutations de n éléments en choisissant successivement un élément non utilisé. Compter les nœuds de l'arbre.

Exercice 3. Les n reines avec un état mutable ★★

Classiques de khôlle et concours · 20 min

compter les solutions des n reines avec trois tableaux de booléens (colonnes, deux familles de diagonales) pour tester une case en temps constant.

Exercice 4. Coloriage en k couleurs ★★

Classiques de khôlle et concours · 20 min

un graphe non orienté de sommets $0$ à $n - 1$ est donné par listes d'adjacence voisins.

Décider s'il est coloriable avec $k$ couleurs.

Exercice 5. Séparation et évaluation sur un sac à dos ★★

Classiques de khôlle et concours · 25 min

$W = 10$, objets (poids, valeur) $$\begin{aligned} A &(3, 9), \\ B &(4, 10), \\ C &(5, 11), \\ D &(2, 3),\end{aligned}$$ de rapports $3$, $2{,}5$, $2{,}2$ et $1{,}5$.

Dérouler la méthode en profondeur, branche « avec » d'abord, borne fractionnaire arrondie à l'entier inférieur.

Exercice 6. Validité de la borne ★★

Classiques de khôlle et concours · 15 min

prouver que la séparation et évaluation renvoie l'optimum.

Montrer qu'elle reste correcte en élaguant quand borne $< M$, et qu'elle devient fausse en élaguant quand borne $< M + 1$ avec des valeurs réelles.

Exercice 7. Meilleur d'abord ★★

Classiques de khôlle et concours · 15 min

les nœuds en attente sont dans une file de priorité par borne décroissante.

On s'arrête dès que la plus grande borne en attente est au plus $M$.

Justifier l'arrêt et comparer la mémoire au parcours en profondeur.

Exercice 8. Clique maximale ★★

Classiques de khôlle et concours · 25 min

un graphe est donné par une matrice d'adjacence booléenne.

Calculer la taille d'une plus grande clique par séparation et évaluation, avec la borne $$|C| + |P|,$$ où $C$ est la clique courante et $P$ la liste des sommets adjacents à tous ceux de $C$.

Exercice 9. Voyageur de commerce, du 1-arbre à la borne exacte ★★★

Approfondissement · 30 min

quatre villes, avec $$d(1,2) = 1, \quad d(1,3) = 4, \quad d(1,4) = 3,$$ $$d(2,3) = 2, \quad d(2,4) = 5$$ et $d(3,4) = 1$.

Comparer la borne par arbre couvrant minimal à une borne plus fine :

arbre couvrant minimal sur $\{2, 3, 4\}$ plus les deux plus courtes arêtes issues de $1$.