Structures de données et algorithmes · Techniques

Retour sur trace (backtracking)

Essayer un choix, récurer, puis l'annuler s'il ne mène nulle part, pour explorer toutes les possibilités.

Commencer une leçon sur Retour sur trace (backtracking)

À apprendre d'abord

• Récursivité: Une fonction qui résout un problème en s'appelant elle-même sur une version plus petite du même problème.

Notions liées

• Parcours de graphes (BFS et DFS): Visiter chaque sommet accessible, soit niveau par niveau (BFS), soit en creusant en profondeur d'abord (DFS).
• Programmation dynamique: Résoudre un problème en mettant en cache les réponses à des sous-problèmes qui se chevauchent plutôt que de les recalculer.