回溯与分支定界有什么区别

什么是回溯

回溯是一种以递归方式解决问题的算法。它是一种尝试不同决策序列以找到正确决策的系统方法。它通过有条不紊地搜索给定问题的解空间来找出解。

所有回溯解决方案都需要满足一组复杂的显式和隐式约束。显式约束限制要从给定集合中选择的每个向量元素。此外，隐式约束在解空间中找到满足准则函数的元组。

什么是分支定界

分支定界更适用于我们不能应用贪心方法和动态规划的情况。通常，这个算法很慢，因为它在最坏的情况下需要指数时间复杂度，但有时它会以合理的效率工作。然而，这种方法有助于确定非凸问题中的全局优化。

此外，为了解决问题，该方法将给定的子问题划分为至少两个新的受限子问题。

回溯与分支定界的区别

定义

回溯是一种算法，用于寻找一些计算问题的所有解决方案，特别是约束满足问题，它逐步构建解决方案的候选者。分支定界是一种用于离散和组合优化问题以及数学优化的算法。因此，这是回溯与分支定界之间的主要区别。

过程

此外，回溯通过找到第一个子问题的解决方案来找到整个问题的解决方案，然后根据第一个问题的解决方案递归解决其他子问题。然而，分支定界通过将给定的问题分成至少两个新的受限子问题来解决给定的问题。因此，这是回溯与分支定界之间的另一个区别。

效率

结论

回溯是一种算法，用于捕获给定计算问题的部分或全部解决方案，尤其是约束满足问题。另一方面，Branch and Bound 是一种为许多优化问题寻找最优解的算法，尤其是在离散和组合优化中。这是回溯与分支和绑定之间的主要区别。

参考：

1. “DAA 算法设计技术——Javatpoint”。 Www.javatpoint.com，可在此处获得。2。 “回溯介绍——Javatpoint。” Www.javatpoint.com，可在此处.3。 “回溯。”维基百科，维基媒体基金会，2018 年 12 月 7 日，可在此处获取。4。 “分支和绑定。”维基百科，维基媒体基金会，2018 年 10 月 8 日，可在此处获取。5。 “什么是回溯？ – 来自 Techopedia 的定义。” Techopedia.com，可在此处获得。