DSA - 回溯算法

回溯算法是一种问题求解方法，它尝试所有可能的解决方案，并选择最佳或所需的解决方案。通常，它用于解决具有多个解决方案的问题。术语“回溯”表明，对于给定的问题，如果当前解决方案不合适，则将其消除，然后回溯以尝试其他解决方案。

什么时候使用回溯算法？

回溯算法可用于以下问题：

问题有多个解决方案或需要找到所有可能的解决方案。
当给定问题可以分解成与原始问题相似的较小子问题时。
如果问题有一些约束或规则必须由解决方案满足。

回溯算法如何工作？

回溯算法探索各种路径以找到将我们带到解决方案的序列路径。沿着这些路径，它建立一些小的检查点，如果找不到可行的解决方案，问题可以从这些检查点回溯。此过程持续到找到最佳解决方案。

在上图中，绿色是起点，蓝色是中间点，红色是没有可行解决方案的点，灰色是最终解决方案。

当回溯算法到达解决方案的结尾时，它会检查这条路径是否是解决方案。如果是解决方案路径，则返回该路径；否则，它会回溯到前一步以找到解决方案。

算法

以下是回溯算法：

1. Start
2. if current_position is goal, return success.
3. else
4. if current_position is an end point, return failed.
5. else-if current_position is not end point, explore and repeat above steps.
6. Stop

回溯算法的复杂度

通常，回溯算法的时间复杂度是指数级的 (O(kⁿ))。在某些情况下，观察到其时间复杂度是阶乘的 (O(N!))。

回溯问题的类型

回溯算法应用于某些特定类型的问题。如下所示：

判定问题 - 用于找到问题的可行解。
优化问题 - 用于找到可以应用的最佳解决方案。
枚举问题 - 用于找到问题的所有可行解的集合。

回溯算法的例子

以下列表显示了回溯算法的示例：

打印页面