11.1 Recherche en profondeur (DFS)

11.1.1 Concepts de base

Le DFS (Depth-First Search) est un algorithme récursif qui explore un chemin jusqu'au bout puis fait marche arrière.

Gabarit de base

void dfs(int etat) {
    // 1. Condition d'arrêt
    if (condition satisfaite) {
        traiter le résultat;
        return;
    }
    
    // 2. Élagage
    if (non conforme) {
        return;
    }
    
    // 3. Essayer tous les choix possibles
    for (chaque choix possible) {
        faire un choix;
        dfs(etat suivant);
        annuler le choix;  // Retour arrière
    }
}

11.1.2 Problème des permutations

Énoncé : Étant donné un entier positif n, afficher toutes les permutations des nombres de 1 à n.

Entrée : un entier positif n (1 ≤ n ≤ 8)
Sortie : toutes les permutations possibles, une par ligne

Exemple :

Entrée : 3
Sortie :
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

#include <iostream>
using namespace std;

int n;
int arr[10];
bool utilise[10];

void dfs(int profondeur) {
    // Condition d'arrêt : nous avons choisi n nombres
    if (profondeur == n) {
        for (int i = 0; i < n; i++) {
            cout << arr[i] << " ";
        }
        cout << endl;
        return;
    }
    
    // Essayer chaque nombre
    for (int i = 1; i <= n; i++) {
        if (!utilise[i]) {
            arr[profondeur] = i;     // Faire un choix
            utilise[i] = true;       // Marquer comme utilisé
            dfs(profondeur + 1);     // Appel récursif au niveau suivant
            utilise[i] = false;      // Annuler le choix (retour arrière)
        }
    }
}

int main() {
    cout << "Entrez n : ";
    cin >> n;
    cout << "Toutes les permutations :" << endl;
    dfs(0);
    return 0;
}

11.1.3 Problème des combinaisons

Énoncé : Choisir k nombres parmi les entiers de 1 à n, afficher toutes les combinaisons possibles.

Entrée : deux entiers positifs n et k (1 ≤ k ≤ n ≤ 20)
Sortie : toutes les combinaisons possibles, une par ligne

Exemple :

Entrée : 4 2
Sortie :
1 2
1 3
1 4
2 3
2 4
3 4

#include <iostream>
using namespace std;

int n, k;
int chemin[25];

void dfs(int depart, int profondeur) {
    // Condition d'arrêt : nous avons choisi k nombres
    if (profondeur == k) {
        for (int i = 0; i < k; i++) {
            cout << chemin[i] << " ";
        }
        cout << endl;
        return;
    }
    
    // Choisir à partir de 'depart' pour garantir l'ordre lexicographique
    for (int i = depart; i <= n; i++) {
        chemin[profondeur] = i;        // Choisir le nombre courant
        dfs(i + 1, profondeur + 1);    // Le suivant commence à i+1 pour éviter les répétitions
    }
}

int main() {
    cout << "Entrez n et k : ";
    cin >> n >> k;
    cout << "Toutes les combinaisons :" << endl;
    dfs(1, 0);
    return 0;
}

11.1.4 Problème du labyrinthe

Énoncé : Soit un labyrinthe de taille n×m, '.' représente un passage, '#' un mur. Déterminer s'il est possible d'aller du coin supérieur gauche (0,0) au coin inférieur droit (n-1,m-1).

Entrée :

• Première ligne : deux entiers n et m (1 ≤ n,m ≤ 100)
• Les n lignes suivantes : chaque ligne contient m caractères, '.' ou '#'

Sortie : "Chemin trouvé" si possible, sinon "Pas de chemin"

Exemple :

Entrée :
4 4
....
.##.
....
###.

Sortie : Chemin trouvé

#include <iostream>
using namespace std;

int n, m;
char labyrinthe[105][105];
bool visite[105][105];
int dx[] = {-1, 1, 0, 0};  // haut, bas, gauche, droite
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y) {
    // Arrivée à la destination
    if (x == n - 1 && y == m - 1) {
        return true;
    }
    
    visite[x][y] = true;  // Marquer la position courante visitée
    
    // Essayer les quatre directions
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        // Vérifier les limites, les obstacles et si déjà visité
        if (nx >= 0 && nx < n && ny >= 0 && ny < m 
            && labyrinthe[nx][ny] != '#' && !visite[nx][ny]) {
            if (dfs(nx, ny)) {
                return true;
            }
        }
    }
    
    return false;
}

int main() {
    cout << "Entrez la taille du labyrinthe n m : ";
    cin >> n >> m;
    cout << "Entrez le labyrinthe ('.' pour passage, '#' pour mur) :" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> labyrinthe[i][j];
        }
    }
    
    if (dfs(0, 0)) {
        cout << "Chemin trouvé" << endl;
    } else {
        cout << "Pas de chemin" << endl;
    }
    
    return 0;
}

11.1.5 Problème des N reines

Énoncé : Placer N reines sur un échiquier n×n de sorte qu'aucune deux ne s'attaquent mutuellement (pas sur la même ligne, colonne ni diagonale).

Entrée : un entier positif n (1 ≤ n ≤ 10)
Sortie : toutes les solutions possibles et leur nombre total

Exemple :

Entrée : 4
Sortie :
.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

Nombre total de solutions : 2

#include <iostream>
using namespace std;

int n;
int plateau[20];  // plateau[i] = colonne où se trouve la reine sur la ligne i
int compteur = 0;

bool estValide(int ligne, int colonne) {
    for (int i = 0; i < ligne; i++) {
        // Vérifier la même colonne ou la même diagonale
        if (plateau[i] == colonne || 
            abs(plateau[i] - colonne) == abs(i - ligne)) {
            return false;
        }
    }
    return true;
}

void dfs(int ligne) {
    if (ligne == n) {
        compteur++;
        // Afficher la solution courante
        cout << "Solution " << compteur << " :" << endl;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << (plateau[i] == j ? "Q" : ".");
            }
            cout << endl;
        }
        cout << endl;
        return;
    }
    
    // Essayer chaque colonne de la ligne courante
    for (int col = 0; col < n; col++) {
        if (estValide(ligne, col)) {
            plateau[ligne] = col;    // Placer la reine
            dfs(ligne + 1);          // Appel récursif à la ligne suivante
        }
    }
}

int main() {
    cout << "Entrez la taille de l'échiquier n : ";
    cin >> n;
    cout << "Toutes les solutions du problème des N reines :" << endl;
    dfs(0);
    cout << "Nombre total de solutions : " << compteur << endl;
    return 0;
}

11.2 Recherche en largeur (BFS)

11.2.1 Concepts de base

Le BFS (Breadth-First Search) utilise une file d'attente, explore niveau par niveau, et convient pour trouver le plus court chemin.

Gabarit de base

#include <queue>
void bfs(int depart) {
    queue<int> q;
    q.push(depart);
    visite[depart] = true;
    
    while (!q.empty()) {
        int courant = q.front();
        q.pop();
        
        // Traiter le nœud courant
        
        // Étendre aux nœuds voisins
        for (chaque voisin suivant) {
            if (!visite[suivant]) {
                visite[suivant] = true;
                q.push(suivant);
            }
        }
    }
}

11.2.2 Plus court chemin dans un labyrinthe

Énoncé : Soit un labyrinthe de taille n×m, trouver la longueur du plus court chemin du coin supérieur gauche (0,0) au coin inférieur droit (n-1,m-1).

Entrée :

• Première ligne : deux entiers n et m (1 ≤ n,m ≤ 100)
• Les n lignes suivantes : chaque ligne contient m caractères, '.' pour passage, '#' pour mur

Sortie : la longueur du plus court chemin, ou -1 si impossible

Exemple :

Entrée :
4 4
....
.##.
....
###.

Sortie : Longueur du plus court chemin : 6

#include <iostream>
#include <queue>
using namespace std;

struct Point {
    int x, y, dist;
};

int n, m;
char labyrinthe[105][105];
bool visite[105][105];
int dx[] = {-1, 1, 0, 0};  // haut, bas, gauche, droite
int dy[] = {0, 0, -1, 1};

int bfs() {
    queue<Point> q;
    q.push({0, 0, 0});        // point de départ et distance
    visite[0][0] = true;
    
    while (!q.empty()) {
        Point courant = q.front();
        q.pop();
        
        // Arrivée à la destination
        if (courant.x == n - 1 && courant.y == m - 1) {
            return courant.dist;
        }
        
        // Essayer les quatre directions
        for (int i = 0; i < 4; i++) {
            int nx = courant.x + dx[i];
            int ny = courant.y + dy[i];
            
            // Vérifier les limites, les obstacles et si visité
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && labyrinthe[nx][ny] != '#' && !visite[nx][ny]) {
                visite[nx][ny] = true;
                q.push({nx, ny, courant.dist + 1});
            }
        }
    }
    
    return -1;  // Aucun chemin trouvé
}

int main() {
    cout << "Entrez la taille du labyrinthe n m : ";
    cin >> n >> m;
    cout << "Entrez le labyrinthe ('.' pour passage, '#' pour mur) :" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> labyrinthe[i][j];
        }
    }
    
    int resultat = bfs();
    if (resultat != -1) {
        cout << "Longueur du plus court chemin : " << resultat << endl;
    } else {
        cout << "Aucun chemin trouvé" << endl;
    }
    
    return 0;
}

11.2.3 Parcours BFS d'un graphe

Énoncé : Soit un graphe non orienté, effectuer un parcours en largeur à partir d'un sommet donné et afficher l'ordre de parcours.

Entrée :

• Première ligne : deux entiers n et m, nombre de sommets et d'arêtes (1 ≤ n ≤ 1000, 0 ≤ m ≤ 10000)
• Les m lignes suivantes : deux entiers u et v, indiquant une arête entre u et v

Sortie : la séquence BFS à partir du sommet 1

Exemple :

Entrée :
5 6
1 2
1 3
2 4
2 5
3 4
4 5

Sortie : 1 2 3 4 5

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> graphe[1005];
bool visite[1005];

void bfs(int depart) {
    queue<int> q;
    q.push(depart);
    visite[depart] = true;
    
    cout << "Séquence BFS : ";
    while (!q.empty()) {
        int courant = q.front();
        q.pop();
        cout << courant << " ";
        
        // Parcourir tous les voisins du sommet courant
        for (int suivant : graphe[courant]) {
            if (!visite[suivant]) {
                visite[suivant] = true;
                q.push(suivant);
            }
        }
    }
    cout << endl;
}

int main() {
    int n, m;
    cout << "Entrez le nombre de sommets n et d'arêtes m : ";
    cin >> n >> m;
    
    cout << "Entrez les " << m << " arêtes :" << endl;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graphe[u].push_back(v);  // Graphe non orienté, ajouter dans les deux directions
        graphe[v].push_back(u);
    }
    
    bfs(1);  // Démarrer le parcours depuis le sommet 1
    return 0;
}

11.2.4 Nombre d'îles

Énoncé : Étant donné une grille 2D composée de '1' (terre) et '0' (eau), calculer le nombre d'îles. Une île est entourée d'eau et formée par des terres adjacentes horizontalement ou verticalement.

Entrée :

• Première ligne : deux entiers n et m (1 ≤ n,m ≤ 100)
• Les n lignes suivantes : chaque ligne contient m caractères, '1' pour terre, '0' pour eau

Sortie : le nombre d'îles

Exemple :

Entrée :
4 5
11110
11010
11000
00000

Sortie : Nombre d'îles : 1

Entrée :
4 5
11000
11000
00100
00011

Sortie : Nombre d'îles : 3

#include <iostream>
#include <queue>
using namespace std;

int n, m;
char grille[105][105];
bool visite[105][105];
int dx[] = {-1, 1, 0, 0};  // haut, bas, gauche, droite
int dy[] = {0, 0, -1, 1};

void bfs(int x, int y) {
    queue<pair<int, int>> q;
    q.push({x, y});
    visite[x][y] = true;
    
    while (!q.empty()) {
        auto [cx, cy] = q.front();
        q.pop();
        
        // Vérifier les quatre directions
        for (int i = 0; i < 4; i++) {
            int nx = cx + dx[i];
            int ny = cy + dy[i];
            
            // Si c'est une terre adjacente non visitée
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && grille[nx][ny] == '1' && !visite[nx][ny]) {
                visite[nx][ny] = true;
                q.push({nx, ny});
            }
        }
    }
}

int compterIles() {
    int compte = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            // Découvrir une nouvelle terre non visitée, lancer BFS
            if (grille[i][j] == '1' && !visite[i][j]) {
                bfs(i, j);  // Marquer toute l'île
                compte++;    // Incrémenter le nombre d'îles
            }
        }
    }
    return compte;
}

int main() {
    cout << "Entrez la taille de la grille n m : ";
    cin >> n >> m;
    cout << "Entrez la grille (1 pour terre, 0 pour eau) :" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grille[i][j];
        }
    }
    
    cout << "Nombre d'îles : " << compterIles() << endl;
    return 0;
}

11.3 Comparaison DFS vs BFS

Caractéristique	DFS	BFS
Structure de données	Pile (récursion)	File
Complexité spatiale	O(h) hauteur	O(w) largeur
Plus court chemin	Non garanti	Garanti
Cas d'usage	Permutations, combinaisons	Plus court chemin
Implémentation	Récursive simple	Itérative

11.4 Optimisations par élagage

11.4.1 Élagage par faisabilité

Énoncé : Étant donné un tableau, déterminer s'il est possible de choisir certains éléments pour que leur somme soit égale à une valeur cible target.

Exemple de code :

#include <iostream>
using namespace std;

int n, cible;
int tab[20];
bool trouve = false;

void dfs(int profondeur, int somme) {
    // Élagage : somme déjà supérieure à la cible, inutile de continuer
    if (somme > cible) return;
    
    // Élagage : si déjà trouvé, inutile de continuer
    if (trouve) return;
    
    if (profondeur == n) {
        if (somme == cible) {
            trouve = true;
            cout << "Somme cible " << cible << " trouvée" << endl;
        }
        return;
    }
    
    // Choisir l'élément courant
    dfs(profondeur + 1, somme + tab[profondeur]);
    // Ne pas choisir l'élément courant
    dfs(profondeur + 1, somme);
}

int main() {
    cout << "Entrez la taille du tableau n : ";
    cin >> n;
    cout << "Entrez les éléments du tableau : ";
    for (int i = 0; i < n; i++) {
        cin >> tab[i];
    }
    cout << "Entrez la somme cible : ";
    cin >> cible;
    
    dfs(0, 0);
    
    if (!trouve) {
        cout << "Impossible d'atteindre la somme cible " << cible << endl;
    }
    
    return 0;
}

11.4.2 Élagage par optimalité

Énoncé : Version simplifiée du problème du voyageur de commerce : partir de la ville de départ, visiter toutes les villes et revenir au départ, minimiser le coût total du trajet.

Exemple de code :

#include <iostream>
#include <climits>
using namespace std;

int n;
int dist[10][10];  // Matrice des distances
bool visite[10];
int meilleur = INT_MAX;
int cheminActuel[10];
int meilleurChemin[10];

void dfs(int profondeur, int cout, int villeCourante) {
    // Élagage : coût déjà supérieur ou égal à la meilleure solution
    if (cout >= meilleur) return;
    
    if (profondeur == n) {
        // Coût pour revenir à la ville de départ
        int total = cout + dist[villeCourante][0];
        if (total < meilleur) {
            meilleur = total;
            // Sauvegarder le meilleur chemin
            for (int i = 0; i < n; i++) {
                meilleurChemin[i] = cheminActuel[i];
            }
        }
        return;
    }
    
    // Essayer de visiter chaque ville non encore visitée
    for (int i = 1; i < n; i++) {
        if (!visite[i]) {
            visite[i] = true;
            cheminActuel[profondeur] = i;
            dfs(profondeur + 1, cout + dist[villeCourante][i], i);
            visite[i] = false;  // Retour arrière
        }
    }
}

int main() {
    cout << "Entrez le nombre de villes n : ";
    cin >> n;
    cout << "Entrez la matrice des distances :" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> dist[i][j];
        }
    }
    
    cheminActuel[0] = 0;  // Commencer par la ville 0
    dfs(1, 0, 0);
    
    cout << "Coût minimal : " << meilleur << endl;
    cout << "Meilleur chemin : ";
    for (int i = 0; i < n; i++) {
        cout << meilleurChemin[i] << " ";
    }
    cout << "0" << endl;  // Retour à la ville de départ
    
    return 0;
}

11.4.3 Recherche mémorisée

Énoncé : Calculer le nombre de chemins du coin supérieur gauche (0,0) au coin inférieur droit (m,n) d'une grille, en se déplaçant uniquement vers la droite ou vers le bas.

Exemple de code :

#include <iostream>
#include <cstring>
using namespace std;

int memo[1005][1005];

int dfs(int i, int j) {
    // Résultat déjà calculé, retour direct
    if (memo[i][j] != -1) {
        return memo[i][j];
    }
    
    // Condition aux limites : lorsqu'on arrive sur un bord, un seul chemin
    if (i == 0 || j == 0) {
        return memo[i][j] = 1;
    }
    
    // Calcul récursif : venant du dessus + venant de la gauche
    memo[i][j] = dfs(i - 1, j) + dfs(i, j - 1);
    return memo[i][j];
}

int main() {
    int m, n;
    cout << "Entrez la taille de la grille m n : ";
    cin >> m >> n;
    
    // Initialiser le tableau de mémorisation
    memset(memo, -1, sizeof(memo));
    
    int resultat = dfs(m, n);
    cout << "Nombre de chemins de (0,0) à (" << m << "," << n << ") : " << resultat << endl;
    
    return 0;
}

Avantages de la recherche mémorisée :

• Évite les calculs redondants
• Réduit la complexité temporelle d'exponentielle à polynomiale
• Conserve la clarté de l'approche récursive

11.5 Exercices complets

11.5.1 Résolution de Sudoku

Énoncé : Soit une grille de Sudoku 9×9 où 0 représente une case vide, 1-9 les chiffres déjà placés. Remplir les cases vides de sorte que chaque ligne, chaque colonne et chaque bloc 3×3 contienne les chiffres de 1 à 9 sans répétition.

Entrée : 9 lignes, chaque ligne contient 9 chiffres, 0 pour les cases vides
Sortie : la grille complète, ou "Pas de solution" si impossible

Exemple :

Entrée :
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

Sortie :
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 9

#include <iostream>
using namespace std;

int grille[9][9];

bool estValide(int ligne, int colonne, int num) {
    // Vérifier la ligne : pas de doublon
    for (int j = 0; j < 9; j++) {
        if (grille[ligne][j] == num) return false;
    }
    
    // Vérifier la colonne : pas de doublon
    for (int i = 0; i < 9; i++) {
        if (grille[i][colonne] == num) return false;
    }
    
    // Vérifier le bloc 3x3 : pas de doublon
    int debutLigne = (ligne / 3) * 3;
    int debutColonne = (colonne / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grille[debutLigne + i][debutColonne + j] == num) {
                return false;
            }
        }
    }
    
    return true;
}

bool resoudreSudoku() {
    // Chercher la première case vide
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (grille[i][j] == 0) {
                // Essayer les chiffres de 1 à 9
                for (int num = 1; num <= 9; num++) {
                    if (estValide(i, j, num)) {
                        grille[i][j] = num;      // Placer le chiffre
                        if (resoudreSudoku()) {   // Résolution récursive
                            return true;
                        }
                        grille[i][j] = 0;        // Retour arrière
                    }
                }
                return false;  // Aucun chiffre ne convient, pas de solution
            }
        }
    }
    return true;  // Toutes les cases sont remplies, solution trouvée
}

int main() {
    cout << "Entrez la grille de Sudoku 9x9 (0 pour case vide) :" << endl;
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            cin >> grille[i][j];
        }
    }
    
    cout << "Résolution en cours..." << endl;
    if (resoudreSudoku()) {
        cout << "Solution du Sudoku :" << endl;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << grille[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "Pas de solution" << endl;
    }
    
    return 0;
}

11.5.2 Recherche de mot

Énoncé : Soit une grille de caractères 2D et un mot, déterminer si le mot existe dans la grille. Le mot doit être formé par des lettres adjacentes horizontalement ou verticalement, sans réutiliser une même cellule.

Entrée :

• Première ligne : deux entiers n et m, taille de la grille (1 ≤ n,m ≤ 10)
• Les n lignes suivantes : chaque ligne contient m caractères, représentant la grille
• Dernière ligne : le mot à rechercher

Sortie : "Mot trouvé" si présent, sinon "Mot non trouvé"

Exemple :

Entrée :
3 4
ABCE
SFCS
ADEE
ABCCED

Sortie : Mot trouvé

Entrée :
3 4
ABCE
SFCS
ADEE
SEE

Sortie : Mot trouvé

Entrée :
3 4
ABCE
SFCS
ADEE
ABCB

Sortie : Mot non trouvé

#include <iostream>
#include <string>
using namespace std;

char grille[10][10];
bool visite[10][10];
int n, m;
string mot;
int dx[] = {-1, 1, 0, 0};  // haut, bas, gauche, droite
int dy[] = {0, 0, -1, 1};

bool dfs(int x, int y, int index) {
    // Mot entièrement trouvé
    if (index == mot.length()) {
        return true;
    }
    
    // Vérification des limites, déjà visité, correspondance du caractère
    if (x < 0 || x >= n || y < 0 || y >= m 
        || visite[x][y] || grille[x][y] != mot[index]) {
        return false;
    }
    
    visite[x][y] = true;  // Marquer la cellule courante visitée
    
    // Essayer les quatre directions
    for (int i = 0; i < 4; i++) {
        if (dfs(x + dx[i], y + dy[i], index + 1)) {
            return true;
        }
    }
    
    visite[x][y] = false;  // Retour arrière
    return false;
}

bool existe() {
    // Essayer chaque position de départ
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (dfs(i, j, 0)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    cout << "Entrez la taille de la grille n m : ";
    cin >> n >> m;
    cout << "Entrez la grille :" << endl;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> grille[i][j];
        }
    }
    cout << "Entrez le mot à rechercher : ";
    cin >> mot;
    
    if (existe()) {
        cout << "Mot trouvé" << endl;
    } else {
        cout << "Mot non trouvé" << endl;
    }
    
    return 0;
}

11.6 Résumé des algorithmes de recherche

Cas d'usage de DFS :

• Problèmes de permutations et combinaisons
• Problèmes de connectivité
• Problèmes de chemins (pas nécessairement les plus courts)
• Problèmes de retour arrière

Cas d'usage de BFS :

• Problèmes de plus court chemin
• Parcours par niveau
• Nombre minimal d'étapes pour une transition d'état

Techniques d'optimisation :

1. Élagage : réduire les recherches inutiles
2. Mémorisation : éviter les calculs redondants
3. Recherche bidirectionnelle : chercher depuis les deux extrémités
4. Recherche heuristique : algorithme A*

Résumé

Ce tutoriel a couvert des concepts avancés importants du C++ :

1. Boucle do while : une boucle qui s'exécute au moins une fois
2. Instruction switch : structure de sélection multiple
3. Digarammes de flux : outil de visualisation d'algorithmes
4. String (chaîne de caractères) : traitement puissant de chaînes
5. Références : passage de paramètres efficace
6. Unions : structure de données économes en mémoire
7. Redirection de fichiers : entrées/sorties vers des fichiers
8. Techniques de débogage : débogage par affichage et GDB
9. Assertions : vérification des hypothèses du programme
10. Recherche par dihcotomie : optimisation des problèmes de recherche
11. Algorithmes de recherche : DFS et BFS

La maîtrise de ces concepts améliorera considérablement votre compétence en programmation C++ !

Conseils pratiques :

1. Mettez en pratique chaque concept
2. Résolvez de nombreux exercices pour consolider votre compréhension
3. Apprenez à déboguer et à optimiser votre code
4. Comprenez les idées algorithmiques, ne les mémorisez pas bêtement