Scribd
Importer
16 vues2 pages

Introduction au Backtracking en Algorithmique

Le backtracking est une technique de recherche qui organise l'espace de recherche en arbre, permettant d'éliminer rapidement des candidats non valides. Il est appliqué à des problèmes comme le placement des dames et le problème de la somme de sous-ensembles. L'implémentation utilise des structures de données mutables et repose sur la récursivité pour explorer les solutions possibles.

Transféré par

gaspardobert70
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
16 vues2 pages

Introduction au Backtracking en Algorithmique

Le backtracking est une technique de recherche qui organise l'espace de recherche en arbre, permettant d'éliminer rapidement des candidats non valides. Il est appliqué à des problèmes comme le placement des dames et le problème de la somme de sous-ensembles. L'implémentation utilise des structures de données mutables et repose sur la récursivité pour explorer les solutions possibles.

Transféré par

gaspardobert70
Copyright
© All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Back Tracking (Retour sur trace)

March 13, 2025

1 Définition générale
Remarque 1 Le backtracking s’applique plutôt sur les problèmes de recherche.
Pour les problèmes d’optimisation, cela s’appelle plutôt le "branch and bound" (séparer et évaluer).

Définition 1 Le backtracking consiste à organiser l’espace de recherche E de manière arborescente, en


groupant des candidats qui ont un point commun en un "candidat partiel".
L’espace de recherche devient alors un arbre tel que

• chaque nœud interne est un candidat partiel

• chaque feuille est un candidat

• Tous les éléments de E apparaissent bien sur au moins une feuille (généralement exactement une)

Cette technique a un intérêt s’il est parfois possible d’établir qu’un candidat partiel n’est pas solution, ce qui
implique qu’aucun candidat "issu" de ce candidat partiel n’est solution. =⇒ on évacue plusieurs candidats
d’un seul coup.
La recherche de solution s’effectue par un parcours en profondeur de cet arbre sans jamais le construire
explicitement : c’est la récursivité qui fait tout.

Remarque 2 On peut écrire des algorithmes de backtracking en impératif.

2 Problème des N dames


Un candidat partiel est un placement des i premières dames (celles des colonnes J0; i − 1K).
Exemple 1 • Avec N = 5. [0; 3; 1] est un candidat partiel.
Les candidats "issus" de ce candidat partiel sont les permutations σ ∈ S5 tq σ(0) = 0, σ(1) =
3, σ(2) = 1
=⇒ il y en a 2.
• Avec N = 18. [0; 2; 1] est un candidat partiel problématique. Donc tous les candidats issus de ce
candidat partiel ne sont pas solution : il y en a 15!.
Remarque 3 Bien sûr, on s’arrête de parcourir l’arbre dès qu’une solution est trouvée.

3 Problème subset somme


Entrées : un ensemble E ⊆ N de
P cardinal n et T ∈ N.
Question : Trouver S ⊆ E tq x=T
x∈S

1
4 Implémentation
Remarque 4 Les structures manipulées sont souvent mutables.
Code :

code (données)
def des objets mutables
let rec aux candidat partiel =
candidat partiel = solution ?
-> Si oui : on arrête tout
candidat partiel impossible
-> Répondre faux
Pour chaque choix possible :
modifier le candidat partiel pour refléter ce choix
aux candidat partiel
effacer ses traces (remodifier l’objet mutable)

5 Notion de sous-problème
Un problème est la description :

• Entrée : type d’entrées possibles

• Sortie : question à résoudre

Exemple 2 • Entrée : E est un ensemble d’entiers ≥ 0 et T ∈ N

• Sortie :

Définition 2 On appelle instance d’un problème une entrée donnée. Ici, une instance de subset_sum
est de la forme e, t

La notion de sous-problème aurait dû s’appeler à mon sens "sous-instance". Comme dans squelette 2
de cours
[Link], une façon de résoudre le problème subset_sum sur une instance e, t est de récursivement
résoudre les "sous-instances" e\x0 , t − x0 et e\x0 , t où e = {x0 , x1 , x2 , . . . }

Vous aimerez peut-être aussi