Exercices corrigés — Exploration exhaustive et retour sur trace (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Trois seuils, et ce qu'une machine mille fois plus rapide y change
- Le masque qui déborde
- La ligne qu'on oublie : combien de solutions produit-elle ?
- Ce que chaque test d'élagage rapporte
- Ordonner avant de parcourir : deux nombres de somme donnée
- Énumérer les permutations d'un mot à lettres répétées
- L'ordre des choix change tout
- Compter les chemins hamiltoniens, avec la grille complète
- Le même élagage, dix fois plus vite
- Le même sous-problème, vingt-deux millions de fois
- Probleme – Le sudoku : la même exploration, deux ordres de choix
- Probleme – Colorier un graphe, et casser les symétries
- Probleme – La droite de balayage
- Probleme – Les mots bien parenthésés, et pourquoi ils sont si peu nombreux
- Probleme – Le voyageur de commerce : quatre niveaux d'élagage