La principale différence entre le retour en arrière et le branchement et la liaison est que le backtracking est un algorithme permettant de capturer certaines ou toutes les solutions à des problèmes de calcul donnés, en particulier pour les problèmes de satisfaction de contraintes, tandis que branch and bound est un algorithme permettant de trouver la solution optimale à de nombreux problèmes d'optimisation, en particulier en optimisation discrète et combinatoire.

Un algorithme est une séquence méthodique d'étapes pour résoudre un problème particulier. Il existe différents algorithmes, et deux d'entre eux sont le backtracking et le branch and bound.

Retour en arrière, Branchement et Liaison

Qu'est-ce que le retour en arrière

Le backtracking est un algorithme qui résout le problème de manière récursive. C'est une manière systématique d'essayer différentes séquences de décisions pour trouver la bonne décision. Il trouve la solution en recherchant méthodiquement l'espace de solution du problème donné.

Toutes les solutions de retour en arrière doivent satisfaire un ensemble complexe de contraintes explicites et implicites. La contrainte explicite limite chaque élément vectoriel à sélectionner dans l'ensemble donné. De plus, la contrainte implicite trouve les tuples dans l'espace des solutions qui peuvent satisfaire la fonction critère.

Qu'est-ce que Branch and Bound

Branch and bound est plus adapté aux situations où nous ne pouvons pas appliquer la méthode gloutonne et la programmation dynamique. Habituellement, cet algorithme est lent car il nécessite des complexités temporelles exponentielles dans le pire des cas, mais il fonctionne parfois avec une efficacité raisonnable. Cependant, cette méthode permet de déterminer l'optimisation globale dans les problèmes non convexes.

De plus, pour résoudre un problème, cette méthode divise le sous-problème donné en au moins deux nouveaux sous-problèmes restreints.

Différence entre le retour en arrière et la branche et la limite

Définition

Le backtracking est un algorithme pour trouver toutes les solutions à certains problèmes de calcul, notamment les problèmes de satisfaction de contraintes qui construit progressivement des candidats aux solutions. Branch and bound est un algorithme pour les problèmes d'optimisation discrète et combinatoire et l'optimisation mathématique. C'est donc la principale différence entre le retour en arrière et le branchement et la liaison.

Traiter

De plus, le retour en arrière trouve la solution au problème global en trouvant une solution au premier sous-problème et en résolvant récursivement d'autres sous-problèmes en fonction de la solution du premier problème. Cependant, branch and bound résout un problème donné en le divisant en au moins deux nouveaux sous-problèmes restreints. Par conséquent, il s'agit d'une autre différence entre le retour en arrière et le branchement et la liaison.

Efficacité

Conclusion

Le backtracking est un algorithme permettant de capturer certaines ou toutes les solutions à des problèmes de calcul donnés, en particulier pour les problèmes de satisfaction de contraintes. Branch and Bound, d'autre part, est un algorithme pour trouver des solutions optimales à de nombreux problèmes d'optimisation, en particulier dans l'optimisation discrète et combinatoire. C'est la principale différence entre Backtracking et Branch and Bound.

Référence:

1. "Techniques de conception d'algorithmes DAA - Javatpoint." Www.javatpoint.com, disponible ici.2. "Introduction au retour en arrière - Javatpoint." Www.javatpoint.com, disponible ici.3. « Retour en arrière ». Wikipédia, Wikimedia Foundation, 7 décembre 2018, disponible ici.4. "Branché et lié." Wikipédia, Wikimedia Foundation, 8 octobre 2018, disponible ici.5. « Qu'est-ce que le retour en arrière ? – Définition de Techopedia. Techopedia.com, disponible ici.

Image de courtoisie:

1. « Algorithmes vs. Langages de programmation »de Lubaochuan - Travail personnel (CC BY-SA 4.0) via Commons Wikimedia